Because the shortest distance between two thoughts is a straight line
My previous blog post reviewed the concept of the Hausdorff distance (which more descriptively could be called farthest distance .) Despite its usefulness in matching geometric data, there are surprisingly few open-source implementations, and seemingly no efficient ones for linear and polygonal data. This even includes CGAL and GRASS, which are usually reliable for provising a wide spectrum of…
The Hausdorff Distance is a useful spatial function which can appear slightly mysterious. Partly this is due to the name. It honours Felix Hausdorff , one of the founding fathers of topology, and a polymath who was creative in music and literature as well as mathematics. Felix Hausdorff (1868-1942) But the name conveys nothing about why this function is useful, or how it is different to the more…
Some spatial use cases require identifying "narrow" or "skinny" polygons. A classic example is the process of cleaning polygonal coverages. Coverages (even clean ones) may contain narrow gaps between polygons which are unwanted. But they may also contain larger gaps which are valid. A geometric test is required to distinguish narrow polygons which are gaps (that can be merged) from wider ones…
The JTS Topology Suite has been rolling out the capability to manage polygonal coverages . It supports modelling polygonal coverages as arrays of discrete polygonal geometries. This is simple to work with and allows using all of the wide variety of JTS algorithms. Coverage topology allows operations such as CoverageSimplifier and CoverageUnion to be highly performant and effective. The key…
A previous post introduced a new algorithm in the JTS Topology Suite called RelateNG . It computes topological relationships between geometries using the Dimensionally-Extended 9 Intersection Model (DE-9IM) model. This algorithm is fundamental to a large proportion of spatial queries executed in numerous geospatial environments. It would not be surprising to learn that the Relate algorithm is…
The most fundamental and widely-used operations in the JTS Topology Suite are the ones that evaluate topological relationships between geometries. JTS implements the Dimensionally-Extended 9 Intersection Model (DE-9IM), as defined in the OGC Simple Features specification , in the RelateOp API. DE-9IM matrix for overlapping polygons The RelateOp algorithm was the very first one implemented during…
A new capability for the JTS Topology Suite is operations to process Simple Polygonal Coverages . A Simple Polygon Coverage is a set of edge-matched, non-overlapping polygonal geometries (which may be non-contiguous, and have holes). Typically this is used to model an area in which every point has a value from some domain. A classic example of a polygonal coverage is a set of administrative…
The next operation delivered in the build-out of Simple Polygonal Coverages in the JTS Topology Suite is Coverage Union . This is simply the topological union of a set of polygons in a polygonal coverage, producing one or more polygons as the result. (This is sometimes called "dissolve" in the context of polygonal coverages.) Union of polygons has long been available in JTS, most recently (and…
Recently JTS gained the ability to compute Concave Hulls of point sets. The algorithm used is based the Chi-shapes approach described by Duckham et al . It works by eroding border triangles from the Delaunay Triangulation of the input points, in order of longest triangle edge length, down to a threshold length provided as a parameter value. Concave Hull of Ukraine (Edge-length = 10) Alpha-Shapes…
There is an elegant mathematical theory of binary relations . Homogeneous relations are an important subclass of binary relations in which both domains are the same. A homogeneous relation R is a subset of all ordered pairs (x,y) with x and y elements of the domain. This can be thought of as a boolean-valued function R(x,y) , which is true if the pair has the relationship and false if not. The…
The previous post discussed polygonal coverages and outlined the plan to support them in the JTS Topology Suite . This post presents the first step of the plan: algorithms to validate polygonal coverages. This capability is essential, since coverage algorithms rely on valid input to provide correct results. And as will be seen below, coverage validity is usually not obvious, and cannot be taken…
An important concept in spatial data modelling is that of a coverage . A coverage models a two-dimensional region in which every point has a value out of a range (which may be defined over one or a set of attributes). Coverages can be represented in both of the main physical spatial data models: raster and vector . In the raster data model a coverage is represented by a grid of cells with varying…
JTS 1.19 has just been released! There is a great deal of new, improved and fixed functionality in this release - see the GitHub release page or the Version History for full details. This blog has several posts describing new functionality in JTS 1.19: New Functionality Concave Hull of Polygons Algorithm for Concave Hull of Polygons Outer and Inner Concave Polygon Hulls Using Outer Hulls for…
The previous post introduced the new ConcaveHullOfPolygons class in the JTS Topology Suite . This allows computing a concave hull which is constrained by a set of polygonal geometries . This supports use cases including: generalization of groups of polygon joining polygons filling gaps between polygons A concave hull of complex polygons The algorithm developed for ConcaveHullOfPolygons is a novel…
A common spatial need is to compute a polygon which contains another set of polygons. There are numerous use cases for this; for example: Generalizing groups of building outlines (questions: 1 , 2 ) Creating "district" polygons around block polygons (questions: 1 ) Removing gaps between sets of polygons (questions: 1 , 2 , 3 , 4 ) Joining two polygons by filling the space between them (questions:…
The electrons were hardly dry on the JTS Outer and Inner Polygon Hull post when another interesting use case popped up on GIS StackExchange . The question was how to remove aliasing artifacts (AKA " jaggies ") from polygons created by vectorizing raster data, with the condition that the result should contain the original polygon . A polygon for Vancouver Island vectorized from a coarse raster…
The JTS Topology Suite recently gained the ability to compute concave hulls . The Concave Hull algorithm computes a polygon enclosing a set of points using a parameter to determine the "tightness". However, for polygonal inputs the computed concave hull is built only using the polygon vertices, and so does not always respect the polygon boundaries. This means the concave hull may not contain the…
As the title of this blog indicates, I'm a fan of linearity. But sometimes a little non-linearity makes things more interesting. A convenient way to generate non-linear curved lines is to use Bezier Curves . Bezier Curves are curves defined by polynomials. Bezier curves can be defined for polynomials of any degree, but a popular choice is to use cubic Bezier curves defined by polynomials of degree…
A common spatial need is to find a polygon that accurately represents a set of points. The convex hull of the points often does not provide this, since it can enclose large areas which contain no points. What is required is a non-convex hull, often termed the concave hull. The Convex Hull and a Concave Hull of a point set A concave hull is generally considered to have some or all of the following…
Offset curves (also known as parallel curves ) are an oft-requested feature in JTS. They are a natural extension to the concept of buffering, and are useful for things like placing labels along rivers. As far as I know there is no hard-and-fast definition for how an offset curve should be constructed, but a reasonable semantic would seem to be "a line lying on one side of another line at a given…
Every so often I produce an image in the JTS TestBuilder which strikes me as worthy of capture. Here's one that seems pretty seasonal: It is generated like this: Produce two sets of 1000 random points roughly aligned with a grid Compute their fully-eroded Convex Hulls Compute the intersection of the two hulls Theme the intersection with random fill
A (long) while ago I posted about "soon-to-be-released" JTS code for polygon triangulation using Ear Clipping . It turned out it was actually in the category of "never-to-be-released". However, later I worked with a student, Dan Tong, on a coding exercise sponsored by Facebook. We decided to tackle polygon triangulation. By the end of the project he implemented a functional algorithm, including…
Recently a GEOS patch was contributed to change the KdTree query implementation to use an explicit stack rather than recursion. This has been ported to JTS as PR #779 (along with some refactoring). The change was motivated by a QGIS issue in which a union of some large polygons caused a stack overflow during a KdTree query. The reason is that the poor vertex alignment of the input polygons causes…
In a previous post I described how the JTS Topology Suite operation IsSimpleOp has been completely rewritten to reduce code dependencies, improve performance, and provide a simpler, more understandable implementation. The post points out that the IsValidOp implementation would benefit from the same treatment. This work has now been carried out, with similar benefits achieved. The original…
Hard to believe that the JTS Topology Suite is almost 20 years old. That's 140 in dog years! Despite what they say about old dogs, one of the benefits of longevity is that you have the opportunity to learn a trick or two along the way. One of the key lessons learned after the initial release of JTS is that intersection (node) detection is a fundamental part of many spatial algorithms, and critical…