Package org.locationtech.jts.operation.union

Class CascadedPolygonUnion

java.lang.Object
org.locationtech.jts.operation.union.CascadedPolygonUnion
public class CascadedPolygonUnion extends 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 Details

    • inputPolys

      private 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:

  • Constructor Details

    • CascadedPolygonUnion

      public CascadedPolygonUnion(Collection polys)
      Creates a new instance to union the given collection of Geometrys.
      Parameters:
      polys - a collection of Polygonal Geometrys

  • Method Details

    • union

      public static Geometry union(Collection polys)
      Computes the union of a collection of Polygonal Geometrys.
      Parameters:
      polys - a collection of Polygonal Geometrys

    • 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:
      IllegalStateException - if this method is called more than once

    • unionTree

      private Geometry unionTree(List geomTree)

    • repeatedUnion

      private Geometry repeatedUnion(List geoms)

    • bufferUnion

      private Geometry bufferUnion(List geoms)

    • bufferUnion

      private Geometry bufferUnion(Geometry g0, Geometry g1)

    • binaryUnion

      private 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.

    • binaryUnion

      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.
      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(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 List reduceToGeometries(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

    • unionOptimized

      private Geometry unionOptimized(Geometry g0, Geometry g1)

    • 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, 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