Optimised intersection of geometry collections

[micycle1]

Just to check, is there anything like UnaryUnionOp.union() for the intersection of many geometries?

Anything that's likely better than geoms.parallelStream().reduce((g1, g2) -> g1.intersection(g2))?

[dr-jts]

The closest is the functions for polygon overlay in PolygonOverlayFunctions

At some point the hope is to provide this as a supported API.

Note that this computes the full "flattened" overlay of a set of overlapping polygons, which is doing more than the pairwise intersections in your code.

[micycle1]

Are you suggesting to take that code, but switch out UNION for INTERSECTION?

[dr-jts]

Before we discuss this further, you'd better confirm what semantics you are looking for. I can think of at least 3 different semantics for "the intersection of many geometries".

Can you provide a diagram or example of explanatory case(s)?

[micycle1]

Sure, the polygonal boolean AND operation on a collection of geometries (to find the area they all have in common).

[dr-jts]

For a boolean AND of a set of polygons, the following pseudo-code is probably a good compromise between simplicity and performance:

result = geom[0[
for i = 1 to N {
  result = OverlayNG.intersection(result, geom[i]
  if result.isEmpty
    break
}

Note that OverlayNG has optimizations for intersection, so it's best to use it,.

I'm curious to know what your use case is?

[micycle1]

Multiplicatively weighted voronoi.
To compute cell for a site, you compute the apollonian circles with all other sites.
Some of these circles with enclose the site (green), others will bend away and enclose the neighbour site (red).
The cell for a site is: intersection(green) - union(red).

The greens necessarily all intersect, so early exit with a break wouldn't help in this case.

[dr-jts]

For that use case it might be faster to use the union-lines-polygonize approach, along with computing the intersection of all the envelopes of the input ovals. Then discard all polygonize results which don't lie with the intersection envelope.

But this is a lot more code, of course.

[micycle1]

Your suggestion does work, but it's somewhat slower. Is UnaryUnionOp.union() the fastest way to node a collection of LineStrings? (that's the bottleneck)

Polygonizer pz = new Polygonizer(false);
pz.setCheckRingsValid(false);
pz.add(UnaryUnionOp.union(inCircles));
List<Polygon> polygons = (List<Polygon>) pz.getPolygons();
var point = geometryFactory.createPoint(site);
Polygon localDominance = polygons.stream().filter(p -> p.contains(point)).findFirst().get();

[dr-jts]

Is UnaryUnionOp.union() the fastest way to node a collection of LineStrings?

Essentially, yes. There might be some overhead that you could avoid with code targetted directly at that task. You could look at building something using MCIndexNoder directly.

Note that your use case will have a lot of intersections which don't appear in the final result. That might indicate that it's possible to to pre-process the input to avoid computing them. Perhaps by discarding sections of of the circles which lie outside the intersection envelope?

[micycle1]

discarding sections of of the circles which lie outside the intersection envelope

Indeed, I discovered the RingClipper class which provides a net increase in performance.