GEOS  3.13.0dev
PolygonizeGraph.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/PolygonizeGraph.java rev. 974
17  *
18  **********************************************************************/
19 
20 #pragma once
21 
22 #include <geos/export.h>
23 
24 #include <geos/planargraph/PlanarGraph.h> // for inheritance
25 
26 #include <vector>
27 
28 #ifdef _MSC_VER
29 #pragma warning(push)
30 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
31 #endif
32 
33 // Forward declarations
34 namespace geos {
35 namespace geom {
36 class LineString;
37 class GeometryFactory;
38 class Coordinate;
39 class CoordinateSequence;
40 }
41 namespace planargraph {
42 class Node;
43 class Edge;
44 class DirectedEdge;
45 }
46 namespace operation {
47 namespace polygonize {
48 class EdgeRing;
49 class PolygonizeDirectedEdge;
50 }
51 }
52 }
53 
54 namespace geos {
55 namespace operation { // geos::operation
56 namespace polygonize { // geos::operation::polygonize
57 
58 
68 class GEOS_DLL PolygonizeGraph: public planargraph::PlanarGraph {
69 
70 public:
71 
76  static void deleteAllEdges(planargraph::Node* node);
77 
82  explicit PolygonizeGraph(const geom::GeometryFactory* newFactory);
83 
88  ~PolygonizeGraph() override;
89 
95  void addEdge(const geom::LineString* line);
96 
105  void getEdgeRings(std::vector<EdgeRing*>& edgeRingList);
106 
116  void deleteCutEdges(std::vector<const geom::LineString*>& cutLines);
117 
130  void deleteDangles(std::vector<const geom::LineString*>& dangleLines);
131 
132 private:
133 
134  static int getDegreeNonDeleted(planargraph::Node* node);
135 
136  static int getDegree(planargraph::Node* node, long label);
137 
138  const geom::GeometryFactory* factory;
139 
140  planargraph::Node* getNode(const geom::Coordinate& pt);
141 
142  void computeNextCWEdges();
143 
153  void convertMaximalToMinimalEdgeRings(
154  std::vector<PolygonizeDirectedEdge*>& ringEdges);
155 
166  static void findIntersectionNodes(PolygonizeDirectedEdge* startDE,
167  long label, std::vector<planargraph::Node*>& intNodes
168  );
169 
179  static void findLabeledEdgeRings(
180  std::vector<planargraph::DirectedEdge*>& dirEdgesIn,
181  std::vector<PolygonizeDirectedEdge*>& dirEdgesOut);
182 
183  static void label(std::vector<PolygonizeDirectedEdge*>& dirEdges, long label);
184  static void label(std::vector<planargraph::DirectedEdge*>& dirEdges, long label);
185 
186  static void computeNextCWEdges(planargraph::Node* node);
187 
195  static void computeNextCCWEdges(planargraph::Node* node, long label);
196 
197  EdgeRing* findEdgeRing(PolygonizeDirectedEdge* startDE);
198 
199  /* Tese are for memory management */
200  std::vector<planargraph::Edge*> newEdges;
201  std::vector<planargraph::DirectedEdge*> newDirEdges;
202  std::vector<planargraph::Node*> newNodes;
203  std::vector<EdgeRing*> newEdgeRings;
204  std::vector<geom::CoordinateSequence*> newCoords;
205 };
206 
207 } // namespace geos::operation::polygonize
208 } // namespace geos::operation
209 } // namespace geos
210 
211 #ifdef _MSC_VER
212 #pragma warning(pop)
213 #endif
214 
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
Definition: LineString.h:65
Represents a ring of PolygonizeDirectedEdge which form a ring of a polygon. The ring may be either an...
Definition: operation/polygonize/EdgeRing.h:59
A DirectedEdge of a PolygonizeGraph, which represents an edge of a polygon formed by the graph.
Definition: PolygonizeDirectedEdge.h:52
Represents a planar graph of edges that can be used to compute a polygonization, and implements the a...
Definition: PolygonizeGraph.h:68
void getEdgeRings(std::vector< EdgeRing * > &edgeRingList)
Computes the EdgeRings formed by the edges in this graph.
static void deleteAllEdges(planargraph::Node *node)
Deletes all edges at a node.
void deleteCutEdges(std::vector< const geom::LineString * > &cutLines)
Finds and removes all cut edges from the graph.
void addEdge(const geom::LineString *line)
Add a LineString forming an edge of the polygon graph.
~PolygonizeGraph() override
Destroy a polygonization graph.
PolygonizeGraph(const geom::GeometryFactory *newFactory)
Create a new polygonization graph.
void deleteDangles(std::vector< const geom::LineString * > &dangleLines)
Marks all edges from the graph which are "dangles".
A node in a PlanarGraph is a location where 0 or more Edge meet.
Definition: planargraph/Node.h:44
Represents a directed graph which is embeddable in a planar surface.
Definition: planargraph/PlanarGraph.h:59
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25