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