Class CascadedPolygonUnion
Polygonal
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
FieldsModifier and TypeFieldDescriptionprivate GeometryFactory
private Collection
private static final int
The effectiveness of the index is somewhat sensitive to the node capacity. -
Constructor Summary
ConstructorsConstructorDescriptionCascadedPolygonUnion
(Collection polys) Creates a new instance to union the given collection ofGeometry
s. -
Method Summary
Modifier and TypeMethodDescriptionprivate Geometry
binaryUnion
(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
(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
(List geoms) private Geometry
bufferUnion
(Geometry g0, Geometry g1) private Geometry
extractByEnvelope
(Envelope env, Geometry geom, List disjointGeoms) private static Geometry
getGeometry
(List list, int index) Gets the element at a given list index, or null if the index is out of range.private List
reduceToGeometries
(List geomTree) Reduces a tree of geometries to a list of geometries by recursively unioning the subtrees in the list.private Geometry
repeatedUnion
(List geoms) private static Geometry
union()
Computes the union of the input geometries.static Geometry
union
(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
Computes the union of two geometries, either or both of which may be null.private Geometry
private Geometry
unionUsingEnvelopeIntersection
(Geometry g0, Geometry g1, Envelope common) Unions two polygonal geometries, restricting computation to the envelope intersection where possible.
-
Field Details
-
inputPolys
-
geomFactory
-
STRTREE_NODE_CAPACITY
private static final int STRTREE_NODE_CAPACITYThe 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:
-
-
Constructor Details
-
Method Details
-
union
-
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:
IllegalStateException
- if this method is called more than once
-
unionTree
-
repeatedUnion
-
bufferUnion
-
bufferUnion
-
binaryUnion
Unions a list of geometries by treating the list as a flattened binary tree, and performing a cascaded union on the tree. -
binaryUnion
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
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
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
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
-
unionOptimized
-
unionUsingEnvelopeIntersection
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
-
unionActual
Encapsulates the actual unioning of two polygonal geometries.- Parameters:
g0
-g1
-- Returns:
-
restrictToPolygons
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
-