This page covers some of what the JTS Topology is made up of, and how you can use this information to optimize a bit.

This page has as little math as possible, quickly moving on to a normal String which we can do regular expression on. This page gives you enough information to optimize your own spatial relationship tests.

Related:

• Spatial Validation Academic References

Definition of a Geometry

Point Set Theory includes concepts of lines and points in addition to regions. These constructs are defined as the set of points contained in their Interior, Boundary and Exterior.

• a Region h is define as a set of interior points h ⁰, boundary _d h and exterior is everything not part of h.
• a Point p is defined by an interior point p ⁰, there is no boundary and the exterior is everything except the point p.
• a Line l is defined by an set of interior points l ⁰ along its length, a boundary of the two end points and an exterior of everything not part of l

The other thing about geometry is they have a number of dimensions:

• dim( Region ) is 2
• dim( Point ) is 0
• dim( Line ) is 1

We are going to leave 3D stuff out of this so my mind does not hurt so much when we get to Geometry Relationships.

Definition of Geometry in Point Set Theory

Intersection of Two Geometries

Relationships between Regions are described as a matrix produced by comparing the intersection of the Interior, Boundary and Exterior properties of both regions. This comparison referred to as the Dimensionally Extended 9-Intersection Matrix or DE-9IM.

The relationship between two geometries x and y (point line or region) as defined by their Interior, Boundary and Exterior results in a matrix based on: x INTERSECTION y.

9-Intersection Matrix

To start with here is what a matrix x INTERSECTION y looks like. Rather than explain this one in English I am going to skip straight to the picture.

x

y

GeometryFactory geometryFactory = FactoryFinder.getGeometryFactory( null );

WKTReader reader = new WKTReader( geometryFactory );
Polygon x = (Polygon) reader.read("POLYGON ((10 10, 15 0, 25 0, 30 10, 25 20, 15 20, 10 10))");
Polygon x = (Polygon) reader.read("POLYGON ((20 10, 30 0, 40 10, 30 20, 20 10))");

	Interior	Boundary	Exterior
Interior
Boundary
Exterior

Intersection of Two Geometries in point set Theory

Dimensionally Extended 9-Intersection Matrix

The next step is to count the dimensions of the shapes in your intersection matrix.

Depending on the geometry involves; and their arrangement you will get different numbers here. The above numbers are taken by looking at what kind of shapes are displayed in the above pictures and writing down their dimension.

And if you were writing this in code it would be:

String relationship = "212101212";

You can also generate this from two live geometry instances:

IntersectionMatrix matrix = geometry.relate( geometry2 );
String relationship = matrix.toString();

This is something so normal we can start to use regular expressions to perform pattern matching on the result! Indeed that is just how Geospatial Relationships are defined.

DE-9IM Matrix

In math speak that is dim( x INTERSECTION Y ).

Geospatial Relationships

Now that we have boiled how two Geomery instances are interacting to a String we can define our Geospatial relationships can be described in terms of a wild card expression.

Consider the following definition of Area/Area overlap.

Or in code:

String overlaps = "T*T***T**";

Where:

• T: value is not equal to zero
• F: value is equal to zero
• *: Don't care what the value is
• 0: value is exactly zero
• 1: value is exactly one
• 2: value is exactly two

You can use these strings with the Geometry relate method:

boolean isRelated = geometry.relate( geometry2, "T*T***T**" );

You can now start to make sense of the JTS javadocs here they define what the operations mean in terms of the relate function.

1. x.Disjoint(y) FF*FF****

2. x.Touches(y) FT******* Area/Area, Line/Line, Line/Area, Point/Area
                F**T***** Not Point/Point
                F***T****

3 x.Crosses(y)  T*T****** Point/Line, Point/Area, Line/Area
  x.Crosses(y)  0******** Line/Line

4 x.Within(y)   TF*F*****

5 x.Overlaps(y) T*T***T** Point/Point, Area/Area
  x.Overlaps(y) 1*T***T** Line/Line

To complete our example lets see what relationships our "212101212" string represents.

The only one that is not really intuitive here is "touches", yes x and y touch in the english sense of the word; but since x and y overlap they are not considered to be only touching. The relationship touches only works when the contact between geometries is limited to the border.

Combing Relationship Tests

Since calculating this stuff is expensive you should take some care not to work too hard; don't call multiple relationship test functions if you can get away with it.

// alternative A
if( geometry.disjoint( geometry2 ) || geometry.touches( geometry2 ) ){
   // these two geometries hardly know each other
}

One thing you can do is calculate the full matrix once and then test out what it can tell you:

// Alternative B
IntersectionMatrix matrix = geometry.relate( geometry2 );
if( matrix.isDisjoint() || matrix.isTouches(2,2) ){
   // these two geometries hardly know each other
}

Of course you can see that with the pattern matching often the full matrix is not needed (since a lot of interactions are marked as don't care). If you think about what you are testing you can come up with your own string and do the test in one step.

We can set up the relate function to test against this pattern:

// Alternative C
if( geometry.relate( geometry2, "F********" ) ){
  // these two geometries hardly know each other
}

So it ends up the relationship we are testing is that the interiors do not overlap.

Benchmark of Alternatives

Out of all of these options - what performs faster?

The resolution of the system clock is no better than 15 mills, so the results are the same for B and C, and alternative A comes in a bit faster!

My guess would be that the explicit relationship methods on the JTS geometry objects are optimized and do not compute the full matrix; all other options cost about the same as they are based on computing the complete matrix and then asking questions about the result.

Here is how I measured:

for( Geometry geometry : geoms ){
         alternative[0]=0;
         for( Geometry geometry2 : geoms ){                
             if( geometry.disjoint( geometry2 ) || geometry.touches( geometry2 ) ){
                 alternative[0]++;
             }
         }
     }

Use of PreparedGeometry

The amove code made use of an inner loop to perform a whole whack of tests against a single geometry; JTS 1.9 includes the idea of a PreparedGeometry for just this situation. The interface has the same sorts of methods as Geometry; but behind the scenes a lot more caching can take place since you have indicated you are going to reuse this geometry a lot.

for( Geometry geometry : geoms ){
        PreparedGeometry prep = new PreparedPolygon( (Polygon) geometry );                    
        alternative[0]=0;
        for( Geometry geometry2 : geoms ){                
            if( prep.disjoint( geometry2 ) || prep.touches( geometry2 ) ){
                alternative[0]++;
            }
        }
    }

There is no PreparedGeometry.relate methods at the time of writing so we can only test against alternative A.

This is not a massive improvement; perhaps squares are too simple? Lets try using unit circle with 32 sides each.

This only goes to show that you should always profile your code with real data. So there is a cross over point where the data is too simple to benefit from a PreparedPolygon.

Recomendation

Your code should actually make use of a factory so that JTS can make you the best implementation for the job.

for( Geometry geometry : circles ){
    PreparedGeometry prep = PreparedGeometryFactory.prepare( geometry );
    alternative[0]=0;
    for( Geometry geometry2 : circles ){                
        if( prep.disjoint( geometry2 ) || prep.touches( geometry2 ) ){
            alternative[0]++;
        }
    }
}