1 /********************************************************************** 2 * 3 * GEOS - Geometry Engine Open Source 4 * http://geos.osgeo.org 5 * 6 * Copyright (C) 2011 Sandro Santilli <strk@kbt.io> 7 * Copyright (C) 2005-2006 Refractions Research Inc. 8 * Copyright (C) 2001-2002 Vivid Solutions Inc. 9 * 10 * This is free software; you can redistribute and/or modify it under 11 * the terms of the GNU Lesser General Public Licence as published 12 * by the Free Software Foundation. 13 * See the COPYING file for more information. 14 * 15 ********************************************************************** 16 * 17 * Last port: geomgraph/DirectedEdgeStar.java r428 (JTS-1.12+) 18 * 19 **********************************************************************/ 20 21 22 #ifndef GEOS_GEOMGRAPH_DIRECTEDEDGEENDSTAR_H 23 #define GEOS_GEOMGRAPH_DIRECTEDEDGEENDSTAR_H 24 25 #include <geos/export.h> 26 #include <set> 27 #include <string> 28 #include <vector> 29 30 #include <geos/geomgraph/EdgeEndStar.h> // for inheritance 31 #include <geos/geomgraph/Label.h> // for private member 32 #include <geos/geom/Coordinate.h> // for p0,p1 33 34 #include <geos/inline.h> 35 36 // Forward declarations 37 namespace geos { 38 namespace geomgraph { 39 class DirectedEdge; 40 class EdgeRing; 41 } 42 } 43 44 namespace geos { 45 namespace geomgraph { // geos.geomgraph 46 47 /** 48 * \brief 49 * A DirectedEdgeStar is an ordered list of **outgoing** DirectedEdges around a node. 50 * 51 * It supports labelling the edges as well as linking the edges to form both 52 * MaximalEdgeRings and MinimalEdgeRings. 53 * 54 */ 55 class GEOS_DLL DirectedEdgeStar: public EdgeEndStar { 56 57 public: 58 DirectedEdgeStar()59 DirectedEdgeStar() 60 : 61 EdgeEndStar(), 62 label(), 63 resultAreaEdgesComputed(false) 64 {} 65 66 ~DirectedEdgeStar() override = default; 67 68 /// Insert a directed edge in the list 69 void insert(EdgeEnd* ee) override; 70 71 Label& getLabel()72 getLabel() 73 { 74 return label; 75 } 76 77 int getOutgoingDegree(); 78 79 int getOutgoingDegree(EdgeRing* er); 80 81 DirectedEdge* getRightmostEdge(); 82 83 /** \brief 84 * Compute the labelling for all dirEdges in this star, as well as the overall labelling 85 */ 86 void computeLabelling(std::vector<GeometryGraph*>* geom) override; // throw(TopologyException *); 87 88 /** \brief 89 * For each dirEdge in the star, merge the label from the sym dirEdge into the label 90 */ 91 void mergeSymLabels(); 92 93 /// \brief Update incomplete dirEdge labels from the labelling for the node 94 void updateLabelling(const Label& nodeLabel); 95 96 97 /** \brief 98 * Traverse the star of DirectedEdges, linking the included edges together. 99 * 100 * To link two dirEdges, the `next` pointer for an incoming dirEdge 101 * is set to the next outgoing edge. 102 * 103 * DirEdges are only linked if: 104 * 105 * - they belong to an area (i.e. they have sides) 106 * - they are marked as being in the result 107 * 108 * Edges are linked in CCW order (the order they are stored). This means 109 * that rings have their face on the Right (in other words, the topological 110 * location of the face is given by the RHS label of the DirectedEdge) 111 * 112 * PRECONDITION: No pair of dirEdges are both marked as being in the result 113 */ 114 void linkResultDirectedEdges(); // throw(TopologyException *); 115 116 void linkMinimalDirectedEdges(EdgeRing* er); 117 118 void linkAllDirectedEdges(); 119 120 /** \brief 121 * Traverse the star of edges, maintaing the current location in the result 122 * area at this node (if any). 123 * 124 * If any L edges are found in the interior of the result, mark them as covered. 125 */ 126 void findCoveredLineEdges(); 127 128 /** \brief 129 * Compute the DirectedEdge depths for a subsequence of the edge array. 130 */ 131 void computeDepths(DirectedEdge* de); 132 133 std::string print() const override; 134 135 private: 136 137 /** 138 * A list of all outgoing edges in the result, in CCW order 139 */ 140 std::vector<DirectedEdge*> resultAreaEdgeList; 141 142 Label label; 143 144 bool resultAreaEdgesComputed; 145 146 /// \brief 147 /// Returned vector is owned by DirectedEdgeStar object, but 148 /// lazily created 149 const std::vector<DirectedEdge*>& getResultAreaEdges(); 150 151 152 /// States for linResultDirectedEdges 153 enum { 154 SCANNING_FOR_INCOMING = 1, 155 LINKING_TO_OUTGOING 156 }; 157 158 int computeDepths(EdgeEndStar::iterator startIt, 159 EdgeEndStar::iterator endIt, int startDepth); 160 }; 161 162 163 } // namespace geos.geomgraph 164 } // namespace geos 165 166 //#ifdef GEOS_INLINE 167 //# include "geos/geomgraph/DirectedEdgeEndStar.inl" 168 //#endif 169 170 #endif // ifndef GEOS_GEOMGRAPH_DIRECTEDEDGEENDSTAR_H 171 172