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 #ifndef GEOS_OP_POLYGONIZE_POLYGONIZEGRAPH_H
21 #define GEOS_OP_POLYGONIZE_POLYGONIZEGRAPH_H
22 
23 #include <geos/export.h>
24 
25 #include <geos/planargraph/PlanarGraph.h> // for inheritance
26 
27 #include <vector>
28 
29 #ifdef _MSC_VER
30 #pragma warning(push)
31 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
32 #endif
33 
34 // Forward declarations
35 namespace geos {
36 namespace geom {
37 class LineString;
38 class GeometryFactory;
39 class Coordinate;
40 class CoordinateSequence;
41 }
42 namespace planargraph {
43 class Node;
44 class Edge;
45 class DirectedEdge;
46 }
47 namespace operation {
48 namespace polygonize {
49 class EdgeRing;
50 class PolygonizeDirectedEdge;
51 }
52 }
53 }
54 
55 namespace geos {
56 namespace operation { // geos::operation
57 namespace polygonize { // geos::operation::polygonize
58 
59 
60 /** \brief
61  * Represents a planar graph of edges that can be used to compute a
62  * polygonization, and implements the algorithms to compute the
63  * EdgeRings formed by the graph.
64  *
65  * The marked flag on DirectedEdge is used to indicate that a directed edge
66  * has be logically deleted from the graph.
67  *
68  */
69 class GEOS_DLL PolygonizeGraph: public planargraph::PlanarGraph {
70 
71 public:
72 
73     /**
74      * \brief
75      * Deletes all edges at a node
76      */
77     static void deleteAllEdges(planargraph::Node* node);
78 
79     /**
80      * \brief
81      * Create a new polygonization graph.
82      */
83     explicit PolygonizeGraph(const geom::GeometryFactory* newFactory);
84 
85     /**
86      * \brief
87      * Destroy a polygonization graph.
88      */
89     ~PolygonizeGraph() override;
90 
91     /**
92      * \brief
93      * Add a LineString forming an edge of the polygon graph.
94      * @param line the line to add
95      */
96     void addEdge(const geom::LineString* line);
97 
98     /**
99      * \brief
100      * Computes the EdgeRings formed by the edges in this graph.
101      *
102      * @param edgeRingList : the EdgeRing found by the
103      * 	polygonization process will be pushed here.
104      *
105      */
106     void getEdgeRings(std::vector<EdgeRing*>& edgeRingList);
107 
108     /**
109      * \brief
110      * Finds and removes all cut edges from the graph.
111      *
112      * @param cutLines : the list of the LineString forming the removed
113      *                   cut edges will be pushed here.
114      *
115      * TODO: document ownership of the returned LineStrings
116      */
117     void deleteCutEdges(std::vector<const geom::LineString*>& cutLines);
118 
119     /** \brief
120      * Marks all edges from the graph which are "dangles".
121      *
122      * Dangles are which are incident on a node with degree 1.
123      * This process is recursive, since removing a dangling edge
124      * may result in another edge becoming a dangle.
125      * In order to handle large recursion depths efficiently,
126      * an explicit recursion stack is used
127      *
128      * @param dangleLines : the LineStrings that formed dangles will
129      *                      be push_back'ed here
130      */
131     void deleteDangles(std::vector<const geom::LineString*>& dangleLines);
132 
133 private:
134 
135     static int getDegreeNonDeleted(planargraph::Node* node);
136 
137     static int getDegree(planargraph::Node* node, long label);
138 
139     const geom::GeometryFactory* factory;
140 
141     planargraph::Node* getNode(const geom::Coordinate& pt);
142 
143     void computeNextCWEdges();
144 
145     /**
146      * \brief
147      * Convert the maximal edge rings found by the initial graph traversal
148      * into the minimal edge rings required by JTS polygon topology rules.
149      *
150      * @param ringEdges
151      * 	the list of start edges for the edgeRings to convert.
152      *
153      */
154     void convertMaximalToMinimalEdgeRings(
155         std::vector<PolygonizeDirectedEdge*>& ringEdges);
156 
157     /**
158      * \brief
159      * Finds all nodes in a maximal edgering
160      * which are self-intersection nodes
161      *
162      * @param startDE
163      * @param label
164      * @param intNodes : intersection nodes found will be pushed here
165      *                   the vector won't be cleared before pushing.
166      */
167     static void findIntersectionNodes(PolygonizeDirectedEdge* startDE,
168                                       long label, std::vector<planargraph::Node*>& intNodes
169                                      );
170 
171     /**
172      * Finds and labels all edgerings in the graph.
173      *
174      * The edge rings are labeling with unique integers.
175      * The labeling allows detecting cut edges.
176      *
177      * @param dirEdgesIn  a list of the DirectedEdges in the graph
178      * @param dirEdgesOut each ring found will be pushed here
179      */
180     static void findLabeledEdgeRings(
181         std::vector<planargraph::DirectedEdge*>& dirEdgesIn,
182         std::vector<PolygonizeDirectedEdge*>& dirEdgesOut);
183 
184     static void label(std::vector<PolygonizeDirectedEdge*>& dirEdges, long label);
185     static void label(std::vector<planargraph::DirectedEdge*>& dirEdges, long label);
186 
187     static void computeNextCWEdges(planargraph::Node* node);
188 
189     /**
190      * \brief
191      * Computes the next edge pointers going CCW around the given node,
192      * for the given edgering label.
193      * This algorithm has the effect of converting maximal edgerings
194      * into minimal edgerings
195      */
196     static void computeNextCCWEdges(planargraph::Node* node, long label);
197 
198     EdgeRing* findEdgeRing(PolygonizeDirectedEdge* startDE);
199 
200     /* Tese are for memory management */
201     std::vector<planargraph::Edge*> newEdges;
202     std::vector<planargraph::DirectedEdge*> newDirEdges;
203     std::vector<planargraph::Node*> newNodes;
204     std::vector<EdgeRing*> newEdgeRings;
205     std::vector<geom::CoordinateSequence*> newCoords;
206 };
207 
208 } // namespace geos::operation::polygonize
209 } // namespace geos::operation
210 } // namespace geos
211 
212 #ifdef _MSC_VER
213 #pragma warning(pop)
214 #endif
215 
216 #endif // GEOS_OP_POLYGONIZE_POLYGONIZEGRAPH_H
217