Class CascadedPolygonUnion
- java.lang.Object
-
- org.locationtech.jts.operation.union.CascadedPolygonUnion
-
public class CascadedPolygonUnion extends java.lang.Object
Provides an efficient method of unioning a collection ofPolygonal
geometries. The geometries are indexed using a spatial index, and unioned recursively in index order. For geometries with a high degree of overlap, this has the effect of reducing the number of vertices early in the process, which increases speed and robustness.This algorithm is faster and more robust than the simple iterated approach of repeatedly unioning each polygon to a result geometry.
The buffer(0) trick is sometimes faster, but can be less robust and can sometimes take a long time to complete. This is particularly the case where there is a high degree of overlap between the polygons. In this case, buffer(0) is forced to compute with all line segments from the outset, whereas cascading can eliminate many segments at each stage of processing. The best situation for using buffer(0) is the trivial case where there is no overlap between the input geometries. However, this case is likely rare in practice.
-
-
Field Summary
Fields Modifier and Type Field Description private GeometryFactory
geomFactory
private java.util.Collection
inputPolys
private static int
STRTREE_NODE_CAPACITY
The effectiveness of the index is somewhat sensitive to the node capacity.
-
Constructor Summary
Constructors Constructor Description CascadedPolygonUnion(java.util.Collection polys)
Creates a new instance to union the given collection ofGeometry
s.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private Geometry
binaryUnion(java.util.List geoms)
Unions a list of geometries by treating the list as a flattened binary tree, and performing a cascaded union on the tree.private Geometry
binaryUnion(java.util.List geoms, int start, int end)
Unions a section of a list using a recursive binary union on each half of the section.private Geometry
bufferUnion(java.util.List geoms)
private Geometry
bufferUnion(Geometry g0, Geometry g1)
private Geometry
extractByEnvelope(Envelope env, Geometry geom, java.util.List disjointGeoms)
private static Geometry
getGeometry(java.util.List list, int index)
Gets the element at a given list index, or null if the index is out of range.private java.util.List
reduceToGeometries(java.util.List geomTree)
Reduces a tree of geometries to a list of geometries by recursively unioning the subtrees in the list.private Geometry
repeatedUnion(java.util.List geoms)
private static Geometry
restrictToPolygons(Geometry g)
Geometry
union()
Computes the union of the input geometries.static Geometry
union(java.util.Collection polys)
private Geometry
unionActual(Geometry g0, Geometry g1)
Encapsulates the actual unioning of two polygonal geometries.private Geometry
unionOptimized(Geometry g0, Geometry g1)
private Geometry
unionSafe(Geometry g0, Geometry g1)
Computes the union of two geometries, either or both of which may be null.private Geometry
unionTree(java.util.List geomTree)
private Geometry
unionUsingEnvelopeIntersection(Geometry g0, Geometry g1, Envelope common)
Unions two polygonal geometries, restricting computation to the envelope intersection where possible.
-
-
-
Field Detail
-
inputPolys
private java.util.Collection inputPolys
-
geomFactory
private GeometryFactory geomFactory
-
STRTREE_NODE_CAPACITY
private static final int STRTREE_NODE_CAPACITY
The effectiveness of the index is somewhat sensitive to the node capacity. Testing indicates that a smaller capacity is better. For an STRtree, 4 is probably a good number (since this produces 2x2 "squares").- See Also:
- Constant Field Values
-
-
Method Detail
-
union
public static Geometry union(java.util.Collection polys)
-
union
public Geometry union()
Computes the union of the input geometries.This method discards the input geometries as they are processed. In many input cases this reduces the memory retained as the operation proceeds. Optimal memory usage is achieved by disposing of the original input collection before calling this method.
- Returns:
- the union of the input geometries or null if no input geometries were provided
- Throws:
java.lang.IllegalStateException
- if this method is called more than once
-
unionTree
private Geometry unionTree(java.util.List geomTree)
-
repeatedUnion
private Geometry repeatedUnion(java.util.List geoms)
-
bufferUnion
private Geometry bufferUnion(java.util.List geoms)
-
binaryUnion
private Geometry binaryUnion(java.util.List geoms)
Unions a list of geometries by treating the list as a flattened binary tree, and performing a cascaded union on the tree.
-
binaryUnion
private Geometry binaryUnion(java.util.List geoms, int start, int end)
Unions a section of a list using a recursive binary union on each half of the section.- Parameters:
geoms
- the list of geometries containing the section to unionstart
- the start index of the sectionend
- the index after the end of the section- Returns:
- the union of the list section
-
getGeometry
private static Geometry getGeometry(java.util.List list, int index)
Gets the element at a given list index, or null if the index is out of range.- Parameters:
list
-index
-- Returns:
- the geometry at the given index or null if the index is out of range
-
reduceToGeometries
private java.util.List reduceToGeometries(java.util.List geomTree)
Reduces a tree of geometries to a list of geometries by recursively unioning the subtrees in the list.- Parameters:
geomTree
- a tree-structured list of geometries- Returns:
- a list of Geometrys
-
unionSafe
private Geometry unionSafe(Geometry g0, Geometry g1)
Computes the union of two geometries, either or both of which may be null.- Parameters:
g0
- a Geometryg1
- a Geometry- Returns:
- the union of the input(s) or null if both inputs are null
-
unionUsingEnvelopeIntersection
private Geometry unionUsingEnvelopeIntersection(Geometry g0, Geometry g1, Envelope common)
Unions two polygonal geometries, restricting computation to the envelope intersection where possible. The case of MultiPolygons is optimized to union only the polygons which lie in the intersection of the two geometry's envelopes. Polygons outside this region can simply be combined with the union result, which is potentially much faster. This case is likely to occur often during cascaded union, and may also occur in real world data (such as unioning data for parcels on different street blocks).- Parameters:
g0
- a polygonal geometryg1
- a polygonal geometrycommon
- the intersection of the envelopes of the inputs- Returns:
- the union of the inputs
-
extractByEnvelope
private Geometry extractByEnvelope(Envelope env, Geometry geom, java.util.List disjointGeoms)
-
unionActual
private Geometry unionActual(Geometry g0, Geometry g1)
Encapsulates the actual unioning of two polygonal geometries.- Parameters:
g0
-g1
-- Returns:
-
restrictToPolygons
private static Geometry restrictToPolygons(Geometry g)
Computes aGeometry
containing onlyPolygonal
components. Extracts thePolygon
s from the input and returns them as an appropriatePolygonal
geometry.If the input is already Polygonal, it is returned unchanged.
A particular use case is to filter out non-polygonal components returned from an overlay operation.
- Parameters:
g
- the geometry to filter- Returns:
- a Polygonal geometry
-
-