public class CascadedPolygonUnion
extends java.lang.Object
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.
Modifier and Type | Field and 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 and Description |
---|
CascadedPolygonUnion(java.util.Collection polys)
Creates a new instance to union
the given collection of
Geometry s. |
Modifier and Type | Method and 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(Geometry g0,
Geometry g1) |
private Geometry |
bufferUnion(java.util.List geoms) |
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.
|
private java.util.Collection inputPolys
private GeometryFactory geomFactory
private static final int STRTREE_NODE_CAPACITY
public static Geometry union(java.util.Collection polys)
public Geometry union()
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.
java.lang.IllegalStateException
- if this method is called more than onceprivate Geometry unionTree(java.util.List geomTree)
private Geometry repeatedUnion(java.util.List geoms)
private Geometry bufferUnion(java.util.List geoms)
private Geometry binaryUnion(java.util.List geoms)
private Geometry binaryUnion(java.util.List geoms, int start, int end)
geoms
- the list of geometries containing the section to unionstart
- the start index of the sectionend
- the index after the end of the sectionprivate static Geometry getGeometry(java.util.List list, int index)
list
- index
- private java.util.List reduceToGeometries(java.util.List geomTree)
geomTree
- a tree-structured list of geometriesprivate Geometry unionSafe(Geometry g0, Geometry g1)
g0
- a Geometryg1
- a Geometryprivate Geometry unionUsingEnvelopeIntersection(Geometry g0, Geometry g1, Envelope common)
g0
- a polygonal geometryg1
- a polygonal geometrycommon
- the intersection of the envelopes of the inputsprivate Geometry extractByEnvelope(Envelope env, Geometry geom, java.util.List disjointGeoms)
private Geometry unionActual(Geometry g0, Geometry g1)
g0
- g1
- private static Geometry restrictToPolygons(Geometry g)
Geometry
containing only Polygonal
components.
Extracts the Polygon
s from the input
and returns them as an appropriate Polygonal
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.
g
- the geometry to filter