Class CascadedPolygonUnion


  • public class CascadedPolygonUnion
    extends java.lang.Object
    Provides an efficient method of unioning a collection of 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 Detail

      • inputPolys

        private java.util.Collection inputPolys
      • 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
    • Constructor Detail

      • CascadedPolygonUnion

        public CascadedPolygonUnion​(java.util.Collection polys)
        Creates a new instance to union the given collection of Geometrys.
        Parameters:
        polys - a collection of Polygonal Geometrys
    • Method Detail

      • 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 union
        start - the start index of the section
        end - 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 Geometry
        g1 - 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 geometry
        g1 - a polygonal geometry
        common - 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 a Geometry containing only Polygonal components. Extracts the Polygons 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.

        Parameters:
        g - the geometry to filter
        Returns:
        a Polygonal geometry