GEOS  3.13.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 #pragma once
21 
22 #include <geos/export.h>
23 #include <geos/algorithm/locate/IndexedPointInAreaLocator.h>
24 #include <geos/operation/polygonize/PolygonizeDirectedEdge.h>
25 #include <geos/geom/Geometry.h>
26 #include <geos/geom/LinearRing.h>
27 #include <geos/geom/Polygon.h>
28 
29 #include <memory>
30 #include <vector>
31 #include <geos/geom/Location.h>
32 
33 #ifdef _MSC_VER
34 #pragma warning(push)
35 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
36 #endif
37 
38 // Forward declarations
39 namespace geos {
40 namespace geom {
41 class LineString;
42 class CoordinateSequence;
43 class GeometryFactory;
44 class Coordinate;
45 }
46 namespace planargraph {
47 class DirectedEdge;
48 }
49 }
50 
51 namespace geos {
52 namespace operation { // geos::operation
53 namespace polygonize { // geos::operation::polygonize
54 
59 class GEOS_DLL EdgeRing {
60 private:
61  const geom::GeometryFactory* factory;
62 
63  typedef std::vector<const PolygonizeDirectedEdge*> DeList;
64  DeList deList;
65 
66  // cache the following data for efficiency
67  std::unique_ptr<geom::LinearRing> ring;
68  std::unique_ptr<geom::CoordinateSequence> ringPts;
69  std::unique_ptr<algorithm::locate::PointOnGeometryLocator> ringLocator;
70 
71  std::unique_ptr<std::vector<std::unique_ptr<geom::LinearRing>>> holes;
72 
73  EdgeRing* shell = nullptr;
74  bool is_hole;
75  bool is_valid = false;
76  bool is_processed = false;
77  bool is_included_set = false;
78  bool is_included = false;
79  bool visitedByUpdateIncludedRecursive = false;
80 
87  const geom::CoordinateSequence* getCoordinates();
88 
89  static void addEdge(const geom::CoordinateSequence* coords,
90  bool isForward,
91  geom::CoordinateSequence* coordList);
92 
94  if (ringLocator == nullptr) {
95  ringLocator.reset(new algorithm::locate::IndexedPointInAreaLocator(*getRingInternal()));
96  }
97  return ringLocator.get();
98  }
99 
100 public:
106  void add(const PolygonizeDirectedEdge* de);
107 
126  EdgeRing* findEdgeRingContaining(const std::vector<EdgeRing*> & erList);
127 
138  static std::vector<PolygonizeDirectedEdge*> findDirEdgesInRing(PolygonizeDirectedEdge* startDE);
139 
151  const geom::CoordinateSequence* testPts,
152  const geom::CoordinateSequence* pts);
153 
162  static bool isInList(const geom::Coordinate& pt,
163  const geom::CoordinateSequence* pts);
164 
165  explicit EdgeRing(const geom::GeometryFactory* newFactory);
166 
167  ~EdgeRing() = default;
168 
169  void build(PolygonizeDirectedEdge* startDE);
170 
171  void computeHole();
172 
173  const DeList& getEdges() const {
174  return deList;
175  }
176 
184  bool isHole() const {
185  return is_hole;
186  }
187 
188  /* Indicates whether we know if the ring should be included in a polygonizer
189  * output of only polygons.
190  */
191  bool isIncludedSet() const {
192  return is_included_set;
193  }
194 
195  /* Indicates whether the ring should be included in a polygonizer output of
196  * only polygons.
197  */
198  bool isIncluded() const {
199  return is_included;
200  }
201 
202  void setIncluded(bool included) {
203  is_included = included;
204  is_included_set = true;
205  }
206 
207  bool isProcessed() const {
208  return is_processed;
209  }
210 
211  void setProcessed(bool processed) {
212  is_processed = processed;
213  }
214 
220  void setShell(EdgeRing* shellRing) {
221  shell = shellRing;
222  }
223 
229  bool hasShell() const {
230  return shell != nullptr;
231  }
232 
240  return isHole() ? shell : this;
241  }
242 
249  bool isOuterHole() const {
250  if (!isHole()) {
251  return false;
252  }
253 
254  return !hasShell();
255  }
256 
262  bool isOuterShell() const {
263  return getOuterHole() != nullptr;
264  }
265 
276 
282 
289 
290  void addHole(EdgeRing* holeER);
291 
300  std::unique_ptr<geom::Polygon> getPolygon();
301 
306  bool isValid() const;
307 
308  void computeValid();
309 
318  std::unique_ptr<geom::LineString> getLineString();
319 
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 
Determines the location of Coordinates relative to an areal geometry, using indexing for efficiency.
Definition: IndexedPointInAreaLocator.h:54
An interface for classes which determine the Location of points in Polygon or MultiPolygon geometries...
Definition: PointOnGeometryLocator.h:36
The internal representation of a list of coordinates inside a Geometry.
Definition: CoordinateSequence.h:56
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:216
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition: GeometryFactory.h:65
Models an OGC SFS LinearRing. A LinearRing is a LineString which is both closed and simple.
Definition: LinearRing.h:54
Represents a ring of PolygonizeDirectedEdge which form a ring of a polygon. The ring may be either an...
Definition: operation/polygonize/EdgeRing.h:59
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:220
static bool isInList(const geom::Coordinate &pt, const geom::CoordinateSequence *pts)
Tests whether a given point is in an array of points. Uses a value-based test.
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:239
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:249
bool isOuterShell() const
Tests whether this ring is an outer shell.
Definition: operation/polygonize/EdgeRing.h:262
void addHole(geom::LinearRing *hole)
Adds a hole to the polygon formed by this ring.
std::unique_ptr< geom::Polygon > getPolygon()
Computes the Polygon formed by this ring and any contained holes.
std::unique_ptr< geom::LineString > getLineString()
Gets the coordinates for this ring as a LineString.
bool isHole() const
Tests whether this ring is a hole.
Definition: operation/polygonize/EdgeRing.h:184
bool isValid() const
Tests if the LinearRing ring formed by this edge ring is topologically valid.
static std::vector< PolygonizeDirectedEdge * > findDirEdgesInRing(PolygonizeDirectedEdge *startDE)
Traverses a ring of DirectedEdges, accumulating them into a list.
EdgeRing * getOuterHole() const
Gets the outer hole of a shell, if it has one. An outer hole is one that is not contained in any othe...
void updateIncludedRecursive()
Updates the included status for currently non-included shells based on whether they are adjacent to a...
EdgeRing * findEdgeRingContaining(const std::vector< EdgeRing * > &erList)
Find the innermost enclosing shell EdgeRing containing this, if any.
std::unique_ptr< geom::LinearRing > getRingOwnership()
Returns this ring as a LinearRing, or null if an Exception occurs while creating it (such as a topolo...
bool hasShell() const
Tests whether this ring has a shell assigned to it.
Definition: operation/polygonize/EdgeRing.h:229
static const geom::Coordinate & ptNotInList(const geom::CoordinateSequence *testPts, const geom::CoordinateSequence *pts)
Finds a point in a list of points which is not contained in another list of points.
void add(const PolygonizeDirectedEdge *de)
Adds a DirectedEdge which is known to form part of this ring.
geom::LinearRing * getRingInternal()
Returns this ring as a LinearRing, or null if an Exception occurs while creating it (such as a topolo...
A DirectedEdge of a PolygonizeGraph, which represents an edge of a polygon formed by the graph.
Definition: PolygonizeDirectedEdge.h:52
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25