/src/geos/src/planargraph/DirectedEdgeStar.cpp
Line | Count | Source |
1 | | /********************************************************************** |
2 | | * |
3 | | * GEOS - Geometry Engine Open Source |
4 | | * http://geos.osgeo.org |
5 | | * |
6 | | * Copyright (C) 2001-2002 Vivid Solutions Inc. |
7 | | * Copyright (C) 2005 Refractions Research Inc. |
8 | | * |
9 | | * This is free software; you can redistribute and/or modify it under |
10 | | * the terms of the GNU Lesser General Licence as published |
11 | | * by the Free Software Foundation. |
12 | | * See the COPYING file for more information. |
13 | | * |
14 | | **********************************************************************/ |
15 | | |
16 | | #include <geos/planargraph/DirectedEdgeStar.h> |
17 | | #include <geos/planargraph/DirectedEdge.h> |
18 | | |
19 | | #include <vector> |
20 | | #include <algorithm> |
21 | | |
22 | | |
23 | | using namespace geos::geom; |
24 | | |
25 | | namespace geos { |
26 | | namespace planargraph { |
27 | | |
28 | | |
29 | | /* |
30 | | * Adds a new member to this DirectedEdgeStar. |
31 | | */ |
32 | | void |
33 | | DirectedEdgeStar::add(DirectedEdge* de) |
34 | 0 | { |
35 | 0 | outEdges.push_back(de); |
36 | 0 | sorted = false; |
37 | 0 | } |
38 | | |
39 | | /* |
40 | | * Drops a member of this DirectedEdgeStar. |
41 | | */ |
42 | | void |
43 | | DirectedEdgeStar::remove(DirectedEdge* de) |
44 | 0 | { |
45 | 0 | for(unsigned int i = 0; i < outEdges.size(); ++i) { |
46 | 0 | if(outEdges[i] == de) { |
47 | 0 | outEdges.erase(std::next(outEdges.begin(), static_cast<int>(i))); |
48 | 0 | --i; |
49 | 0 | } |
50 | 0 | } |
51 | 0 | } |
52 | | |
53 | | std::vector<DirectedEdge*>::iterator |
54 | | DirectedEdgeStar::begin() |
55 | 0 | { |
56 | 0 | sortEdges(); |
57 | 0 | return outEdges.begin(); |
58 | 0 | } |
59 | | |
60 | | std::vector<DirectedEdge*>::iterator |
61 | | DirectedEdgeStar::end() |
62 | 0 | { |
63 | 0 | sortEdges(); |
64 | 0 | return outEdges.end(); |
65 | 0 | } |
66 | | |
67 | | std::vector<DirectedEdge*>::const_iterator |
68 | | DirectedEdgeStar::begin() const |
69 | 0 | { |
70 | 0 | sortEdges(); |
71 | 0 | return outEdges.begin(); |
72 | 0 | } |
73 | | |
74 | | std::vector<DirectedEdge*>::const_iterator |
75 | | DirectedEdgeStar::end() const |
76 | 0 | { |
77 | 0 | sortEdges(); |
78 | 0 | return outEdges.end(); |
79 | 0 | } |
80 | | |
81 | | /* |
82 | | * Returns the coordinate for the node at which this star is based |
83 | | */ |
84 | | Coordinate& |
85 | | DirectedEdgeStar::getCoordinate() const |
86 | 0 | { |
87 | 0 | if(outEdges.empty()) { |
88 | 0 | static Coordinate nullCoord = Coordinate::getNull(); |
89 | 0 | return nullCoord; |
90 | 0 | } |
91 | 0 | DirectedEdge* e = outEdges[0]; |
92 | 0 | return e->getCoordinate(); |
93 | 0 | } |
94 | | |
95 | | /* |
96 | | * Returns the DirectedEdges, in ascending order by angle with |
97 | | * the positive x-axis. |
98 | | */ |
99 | | std::vector<DirectedEdge*>& |
100 | | DirectedEdgeStar::getEdges() |
101 | 0 | { |
102 | 0 | sortEdges(); |
103 | 0 | return outEdges; |
104 | 0 | } |
105 | | |
106 | | bool |
107 | | pdeLessThan(DirectedEdge* first, DirectedEdge* second) |
108 | 0 | { |
109 | 0 | if(first->compareTo(second) < 0) { |
110 | 0 | return true; |
111 | 0 | } |
112 | 0 | else { |
113 | 0 | return false; |
114 | 0 | } |
115 | 0 | } |
116 | | |
117 | | /*private*/ |
118 | | void |
119 | | DirectedEdgeStar::sortEdges() const |
120 | 0 | { |
121 | 0 | if(!sorted) { |
122 | 0 | sort(outEdges.begin(), outEdges.end(), pdeLessThan); |
123 | 0 | sorted = true; |
124 | 0 | } |
125 | 0 | } |
126 | | |
127 | | /* |
128 | | * Returns the zero-based index of the given Edge, after sorting in |
129 | | * ascending order by angle with the positive x-axis. |
130 | | */ |
131 | | int |
132 | | DirectedEdgeStar::getIndex(const Edge* edge) |
133 | 0 | { |
134 | 0 | sortEdges(); |
135 | 0 | for(unsigned int i = 0; i < outEdges.size(); ++i) { |
136 | 0 | DirectedEdge* de = outEdges[i]; |
137 | 0 | if(de->getEdge() == edge) { |
138 | 0 | return static_cast<int>(i); |
139 | 0 | } |
140 | 0 | } |
141 | 0 | return -1; |
142 | 0 | } |
143 | | |
144 | | /* |
145 | | * Returns the zero-based index of the given DirectedEdge, after sorting |
146 | | * in ascending order by angle with the positive x-axis. |
147 | | */ |
148 | | int |
149 | | DirectedEdgeStar::getIndex(const DirectedEdge* dirEdge) |
150 | 0 | { |
151 | 0 | sortEdges(); |
152 | 0 | for(unsigned int i = 0; i < outEdges.size(); ++i) { |
153 | 0 | DirectedEdge* de = outEdges[i]; |
154 | 0 | if(de == dirEdge) { |
155 | 0 | return static_cast<int>(i); |
156 | 0 | } |
157 | 0 | } |
158 | 0 | return -1; |
159 | 0 | } |
160 | | |
161 | | /* |
162 | | * Returns the remainder when i is divided by the number of edges in this |
163 | | * DirectedEdgeStar. |
164 | | */ |
165 | | unsigned int |
166 | | DirectedEdgeStar::getIndex(int i) const |
167 | 0 | { |
168 | 0 | int modi = i % (int)outEdges.size(); |
169 | | //I don't think modi can be 0 (assuming i is positive) [Jon Aquino 10/28/2003] |
170 | 0 | if(modi < 0) { |
171 | 0 | modi += (int)outEdges.size(); |
172 | 0 | } |
173 | 0 | return static_cast<unsigned int>(modi); |
174 | 0 | } |
175 | | |
176 | | /* |
177 | | * Returns the DirectedEdge on the left-hand side of the given |
178 | | * DirectedEdge (which must be a member of this DirectedEdgeStar). |
179 | | */ |
180 | | DirectedEdge* |
181 | | DirectedEdgeStar::getNextEdge(DirectedEdge* dirEdge) |
182 | 0 | { |
183 | 0 | int i = getIndex(dirEdge); |
184 | 0 | return outEdges[getIndex(i + 1)]; |
185 | 0 | } |
186 | | |
187 | | } // namespace planargraph |
188 | | } // namespace geos |
189 | | |