GEOS  3.8.0dev
CascadedPolygonUnion.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2011 Sandro Santilli <strk@kbt.io>
7  * Copyright (C) 2006 Refractions Research Inc.
8  *
9  * This is free software; you can redistribute and/or modify it under
10  * the terms of the GNU Lesser General Public Licence as published
11  * by the Free Software Foundation.
12  * See the COPYING file for more information.
13  *
14  **********************************************************************
15  *
16  * Last port: operation/union/CascadedPolygonUnion.java r487 (JTS-1.12+)
17  * Includes custom code to deal with https://trac.osgeo.org/geos/ticket/837
18  *
19  **********************************************************************/
20 
21 #ifndef GEOS_OP_UNION_CASCADEDPOLYGONUNION_H
22 #define GEOS_OP_UNION_CASCADEDPOLYGONUNION_H
23 
24 #include <geos/export.h>
25 
26 #include <vector>
27 #include <algorithm>
28 #include <memory>
29 
30 #include "GeometryListHolder.h"
31 
32 // Forward declarations
33 namespace geos {
34 namespace geom {
35 class GeometryFactory;
36 class Geometry;
37 class Polygon;
38 class MultiPolygon;
39 class Envelope;
40 }
41 namespace index {
42 namespace strtree {
43 class ItemsList;
44 }
45 }
46 }
47 
48 namespace geos {
49 namespace operation { // geos::operation
50 namespace geounion { // geos::operation::geounion
51 
68 class GEOS_DLL CascadedPolygonUnion {
69 private:
70  std::vector<geom::Polygon*>* inputPolys;
71  geom::GeometryFactory const* geomFactory;
72 
80  static int const STRTREE_NODE_CAPACITY = 4;
81 
96  static std::unique_ptr<geom::Geometry> restrictToPolygons(std::unique_ptr<geom::Geometry> g);
97 
98 public:
100 
107  static geom::Geometry* Union(std::vector<geom::Polygon*>* polys);
108 
116  template <class T>
117  static geom::Geometry*
118  Union(T start, T end)
119  {
120  std::vector<geom::Polygon*> polys;
121  for(T i = start; i != end; ++i) {
122  const geom::Polygon* p = dynamic_cast<const geom::Polygon*>(*i);
123  polys.push_back(const_cast<geom::Polygon*>(p));
124  }
125  return Union(&polys);
126  }
127 
134  static geom::Geometry* Union(const geom::MultiPolygon* polys);
135 
143  CascadedPolygonUnion(std::vector<geom::Polygon*>* polys)
144  : inputPolys(polys),
145  geomFactory(nullptr)
146  {}
147 
154  geom::Geometry* Union();
155 
156 private:
157  geom::Geometry* unionTree(index::strtree::ItemsList* geomTree);
158 
164  geom::Geometry* binaryUnion(GeometryListHolder* geoms);
165 
175  geom::Geometry* binaryUnion(GeometryListHolder* geoms, std::size_t start,
176  std::size_t end);
177 
185  GeometryListHolder* reduceToGeometries(index::strtree::ItemsList* geomTree);
186 
196  geom::Geometry* unionSafe(geom::Geometry* g0, geom::Geometry* g1);
197 
198  geom::Geometry* unionOptimized(geom::Geometry* g0, geom::Geometry* g1);
199 
219  geom::Geometry* unionUsingEnvelopeIntersection(geom::Geometry* g0,
220  geom::Geometry* g1, geom::Envelope const& common);
221 
222  geom::Geometry* extractByEnvelope(geom::Envelope const& env,
223  geom::Geometry* geom, std::vector<geom::Geometry*>& disjointGeoms);
224 
225  void extractByEnvelope(geom::Envelope const& env,
226  geom::Geometry* geom,
227  std::vector<geom::Geometry*>& intersectingGeoms,
228  std::vector<geom::Geometry*>& disjointGeoms);
229 
230  void extractByEnvelope(geom::Envelope const& env,
231  std::vector<geom::Geometry*>& sourceGeoms,
232  std::vector<geom::Geometry*>& intersectingGeoms,
233  std::vector<geom::Geometry*>& disjointGeoms);
234 
242  static geom::Geometry* unionActual(geom::Geometry* g0, geom::Geometry* g1);
243 };
244 
245 } // namespace geos::operation::union
246 } // namespace geos::operation
247 } // namespace geos
248 
249 #endif
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
CascadedPolygonUnion(std::vector< geom::Polygon * > *polys)
Creates a new instance to union the given collection of Geometrys.
Definition: CascadedPolygonUnion.h:143
Models a collection of Polygons.
Definition: MultiPolygon.h:59
Basic implementation of Geometry, constructed and destructed by GeometryFactory.
Definition: Geometry.h:188
Represents a linear polygon, which may include holes.
Definition: Polygon.h:64
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition: GeometryFactory.h:66
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:25
static geom::Geometry * Union(T start, T end)
Computes the union of a set of polygonal Geometrys.
Definition: CascadedPolygonUnion.h:118
Provides an efficient method of unioning a collection of polygonal geometries.
Definition: CascadedPolygonUnion.h:68
Helper class holding Geometries, part of which are held by reference others are held exclusively...
Definition: GeometryListHolder.h:34