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