GEOS  3.8.0dev
operation/polygonize/EdgeRing.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2006 Refractions Research Inc.
7  * Copyright (C) 2001-2002 Vivid Solutions 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/polygonize/EdgeRing.java 0b3c7e3eb0d3e
17  *
18  **********************************************************************/
19 
20 
21 #ifndef GEOS_OP_POLYGONIZE_EDGERING_H
22 #define GEOS_OP_POLYGONIZE_EDGERING_H
23 
24 #include <geos/export.h>
25 #include <geos/algorithm/locate/IndexedPointInAreaLocator.h>
26 #include <geos/operation/polygonize/PolygonizeDirectedEdge.h>
27 #include <geos/geom/Geometry.h>
28 #include <geos/geom/LinearRing.h>
29 #include <geos/geom/Polygon.h>
30 
31 #include <memory>
32 #include <vector>
33 #include <geos/geom/Location.h>
34 
35 #ifdef _MSC_VER
36 #pragma warning(push)
37 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
38 #endif
39 
40 // Forward declarations
41 namespace geos {
42 namespace geom {
43 class LineString;
44 class CoordinateSequence;
45 class GeometryFactory;
46 class Coordinate;
47 }
48 namespace planargraph {
49 class DirectedEdge;
50 }
51 namespace index {
52 namespace strtree {
53 class STRtree;
54 }
55 }
56 }
57 
58 namespace geos {
59 namespace operation { // geos::operation
60 namespace polygonize { // geos::operation::polygonize
61 
66 class GEOS_DLL EdgeRing {
67 private:
68  const geom::GeometryFactory* factory;
69 
70  typedef std::vector<const PolygonizeDirectedEdge*> DeList;
71  DeList deList;
72 
73  // cache the following data for efficiency
74  std::unique_ptr<geom::LinearRing> ring;
75  std::unique_ptr<geom::CoordinateArraySequence> ringPts;
76  std::unique_ptr<algorithm::locate::PointOnGeometryLocator> ringLocator;
77 
78  std::unique_ptr<std::vector<geom::LinearRing*>> holes;
79 
80  EdgeRing* shell = nullptr;
81  bool is_hole;
82  bool is_processed = false;
83  bool is_included_set = false;
84  bool is_included = false;
85  bool visitedByUpdateIncludedRecursive = false;
86 
93  const geom::CoordinateSequence* getCoordinates();
94 
95  static void addEdge(const geom::CoordinateSequence* coords,
96  bool isForward,
98 
100  if (ringLocator == nullptr) {
101  ringLocator.reset(new algorithm::locate::IndexedPointInAreaLocator(*getRingInternal()));
102  }
103  return ringLocator.get();
104  }
105 
106 public:
112  void add(const PolygonizeDirectedEdge* de);
113 
132  EdgeRing* findEdgeRingContaining(const std::vector<EdgeRing*> & erList);
133 
144  static std::vector<PolygonizeDirectedEdge*> findDirEdgesInRing(PolygonizeDirectedEdge* startDE);
145 
156  static const geom::Coordinate& ptNotInList(
157  const geom::CoordinateSequence* testPts,
158  const geom::CoordinateSequence* pts);
159 
168  static bool isInList(const geom::Coordinate& pt,
169  const geom::CoordinateSequence* pts);
170 
171  explicit EdgeRing(const geom::GeometryFactory* newFactory);
172 
173  ~EdgeRing();
174 
175  void build(PolygonizeDirectedEdge* startDE);
176 
177  void computeHole();
178 
186  bool isHole() const {
187  return is_hole;
188  }
189 
190  /* Indicates whether we know if the ring should be included in a polygonizer
191  * output of only polygons.
192  */
193  bool isIncludedSet() const {
194  return is_included_set;
195  }
196 
197  /* Indicates whether the ring should be included in a polygonizer output of
198  * only polygons.
199  */
200  bool isIncluded() const {
201  return is_included;
202  }
203 
204  void setIncluded(bool included) {
205  is_included = included;
206  is_included_set = true;
207  }
208 
209  bool isProcessed() const {
210  return is_processed;
211  }
212 
213  void setProcessed(bool processed) {
214  is_processed = processed;
215  }
216 
222  void setShell(EdgeRing* shellRing) {
223  shell = shellRing;
224  }
225 
231  bool hasShell() const {
232  return shell != nullptr;
233  }
234 
242  return isHole() ? shell : this;
243  }
244 
251  bool isOuterHole() const {
252  if (!isHole()) {
253  return false;
254  }
255 
256  return !hasShell();
257  }
258 
264  bool isOuterShell() const {
265  return getOuterHole() != nullptr;
266  }
267 
277  EdgeRing* getOuterHole() const;
278 
283  void updateIncludedRecursive();
284 
290  void addHole(geom::LinearRing* hole);
291 
292  void addHole(EdgeRing* holeER);
293 
302  std::unique_ptr<geom::Polygon> getPolygon();
303 
308  bool isValid();
309 
318  std::unique_ptr<geom::LineString> getLineString();
319 
327  geom::LinearRing* getRingInternal();
328 
336  std::unique_ptr<geom::LinearRing> getRingOwnership();
337 
338  bool isInRing(const geom::Coordinate & pt) {
339  return geom::Location::EXTERIOR != getLocator()->locate(&pt);
340  }
341 };
342 
343 } // namespace geos::operation::polygonize
344 } // namespace geos::operation
345 } // namespace geos
346 
347 #ifdef _MSC_VER
348 #pragma warning(pop)
349 #endif
350 
351 #endif // GEOS_OP_POLYGONIZE_EDGERING_H
Determines the location of Coordinates relative to an areal geometry, using indexing for efficiency...
Definition: IndexedPointInAreaLocator.h:52
The default implementation of CoordinateSequence.
Definition: CoordinateArraySequence.h:37
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:60
bool hasShell() const
Tests whether this ring has a shell assigned to it.
Definition: operation/polygonize/EdgeRing.h:231
An interface for classes which determine the Location of points in Polygon or MultiPolygon geometries...
Definition: PointOnGeometryLocator.h:37
A DirectedEdge of a PolygonizeGraph, which represents an edge of a polygon formed by the graph...
Definition: PolygonizeDirectedEdge.h:54
void setShell(EdgeRing *shellRing)
Sets the containing shell ring of a ring that has been determined to be a hole.
Definition: operation/polygonize/EdgeRing.h:222
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition: GeometryFactory.h:66
bool isOuterHole() const
Tests whether this ring is an outer hole. A hole is an outer hole if it is not contained by any shell...
Definition: operation/polygonize/EdgeRing.h:251
EdgeRing * getShell()
Gets the shell for this ring. The shell is the ring itself if it is not a hole, otherwise it is the p...
Definition: operation/polygonize/EdgeRing.h:241
Represents a ring of PolygonizeDirectedEdge which form a ring of a polygon. The ring may be either an...
Definition: operation/polygonize/EdgeRing.h:66
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:25
Models an OGC SFS LinearRing. A LinearRing is a LineString which is both closed and simple...
Definition: LinearRing.h:54
The internal representation of a list of coordinates inside a Geometry.
Definition: CoordinateSequence.h:58
bool isOuterShell() const
Tests whether this ring is an outer shell.
Definition: operation/polygonize/EdgeRing.h:264
bool isHole() const
Tests whether this ring is a hole.
Definition: operation/polygonize/EdgeRing.h:186