1 | /* |
2 | * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors |
3 | * http://code.google.com/p/poly2tri/ |
4 | * |
5 | * All rights reserved. |
6 | * |
7 | * Redistribution and use in source and binary forms, with or without modification, |
8 | * are permitted provided that the following conditions are met: |
9 | * |
10 | * * Redistributions of source code must retain the above copyright notice, |
11 | * this list of conditions and the following disclaimer. |
12 | * * Redistributions in binary form must reproduce the above copyright notice, |
13 | * this list of conditions and the following disclaimer in the documentation |
14 | * and/or other materials provided with the distribution. |
15 | * * Neither the name of Poly2Tri nor the names of its contributors may be |
16 | * used to endorse or promote products derived from this software without specific |
17 | * prior written permission. |
18 | * |
19 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
20 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
21 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
22 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR |
23 | * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
24 | * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
25 | * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
26 | * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
27 | * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
28 | * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
29 | * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
30 | */ |
31 | /** |
32 | * Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V. and |
33 | * Zalik, B.(2008)'Sweep-line algorithm for constrained Delaunay triangulation', |
34 | * International Journal of Geographical Information Science |
35 | * |
36 | * "FlipScan" Constrained Edge Algorithm invented by Thomas Åhlén, thahlen@gmail.com |
37 | */ |
38 | |
39 | #ifndef SWEEP_H |
40 | #define SWEEP_H |
41 | |
42 | #include <vector> |
43 | |
44 | namespace p2t { |
45 | |
46 | class SweepContext; |
47 | struct Node; |
48 | struct Point; |
49 | struct Edge; |
50 | class Triangle; |
51 | |
52 | class Sweep |
53 | { |
54 | public: |
55 | |
56 | /** |
57 | * Triangulate |
58 | * |
59 | * @param tcx |
60 | */ |
61 | void Triangulate(SweepContext& tcx); |
62 | |
63 | /** |
64 | * Destructor - clean up memory |
65 | */ |
66 | ~Sweep(); |
67 | |
68 | private: |
69 | |
70 | /** |
71 | * Start sweeping the Y-sorted point set from bottom to top |
72 | * |
73 | * @param tcx |
74 | */ |
75 | void SweepPoints(SweepContext& tcx); |
76 | |
77 | /** |
78 | * Find closes node to the left of the new point and |
79 | * create a new triangle. If needed new holes and basins |
80 | * will be filled to. |
81 | * |
82 | * @param tcx |
83 | * @param point |
84 | * @return |
85 | */ |
86 | Node& PointEvent(SweepContext& tcx, Point& point); |
87 | |
88 | /** |
89 | * |
90 | * |
91 | * @param tcx |
92 | * @param edge |
93 | * @param node |
94 | */ |
95 | void EdgeEvent(SweepContext& tcx, Edge* edge, Node* node); |
96 | |
97 | void EdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* triangle, Point& point); |
98 | |
99 | /** |
100 | * Creates a new front triangle and legalize it |
101 | * |
102 | * @param tcx |
103 | * @param point |
104 | * @param node |
105 | * @return |
106 | */ |
107 | Node& NewFrontTriangle(SweepContext& tcx, Point& point, Node& node); |
108 | |
109 | /** |
110 | * Adds a triangle to the advancing front to fill a hole. |
111 | * @param tcx |
112 | * @param node - middle node, that is the bottom of the hole |
113 | */ |
114 | void Fill(SweepContext& tcx, Node& node); |
115 | |
116 | /** |
117 | * Returns true if triangle was legalized |
118 | */ |
119 | bool Legalize(SweepContext& tcx, Triangle& t); |
120 | |
121 | /** |
122 | * <b>Requirement</b>:<br> |
123 | * 1. a,b and c form a triangle.<br> |
124 | * 2. a and d is know to be on opposite side of bc<br> |
125 | * <pre> |
126 | * a |
127 | * + |
128 | * / \ |
129 | * / \ |
130 | * b/ \c |
131 | * +-------+ |
132 | * / d \ |
133 | * / \ |
134 | * </pre> |
135 | * <b>Fact</b>: d has to be in area B to have a chance to be inside the circle formed by |
136 | * a,b and c<br> |
137 | * d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW<br> |
138 | * This preknowledge gives us a way to optimize the incircle test |
139 | * @param a - triangle point, opposite d |
140 | * @param b - triangle point |
141 | * @param c - triangle point |
142 | * @param d - point opposite a |
143 | * @return true if d is inside circle, false if on circle edge |
144 | */ |
145 | bool Incircle(Point& pa, Point& pb, Point& pc, Point& pd); |
146 | |
147 | /** |
148 | * Rotates a triangle pair one vertex CW |
149 | *<pre> |
150 | * n2 n2 |
151 | * P +-----+ P +-----+ |
152 | * | t /| |\ t | |
153 | * | / | | \ | |
154 | * n1| / |n3 n1| \ |n3 |
155 | * | / | after CW | \ | |
156 | * |/ oT | | oT \| |
157 | * +-----+ oP +-----+ |
158 | * n4 n4 |
159 | * </pre> |
160 | */ |
161 | void RotateTrianglePair(Triangle& t, Point& p, Triangle& ot, Point& op); |
162 | |
163 | /** |
164 | * Fills holes in the Advancing Front |
165 | * |
166 | * |
167 | * @param tcx |
168 | * @param n |
169 | */ |
170 | void FillAdvancingFront(SweepContext& tcx, Node& n); |
171 | |
172 | // Decision-making about when to Fill hole. |
173 | // Contributed by ToolmakerSteve2 |
174 | bool LargeHole_DontFill(Node* node); |
175 | bool AngleExceeds90Degrees(Point* origin, Point* pa, Point* pb); |
176 | bool AngleExceedsPlus90DegreesOrIsNegative(Point* origin, Point* pa, Point* pb); |
177 | double Angle(Point& origin, Point& pa, Point& pb); |
178 | |
179 | /** |
180 | * |
181 | * @param node - middle node |
182 | * @return the angle between 3 front nodes |
183 | */ |
184 | double HoleAngle(Node& node); |
185 | |
186 | /** |
187 | * The basin angle is decided against the horizontal line [1,0] |
188 | */ |
189 | double BasinAngle(Node& node); |
190 | |
191 | /** |
192 | * Fills a basin that has formed on the Advancing Front to the right |
193 | * of given node.<br> |
194 | * First we decide a left,bottom and right node that forms the |
195 | * boundaries of the basin. Then we do a reqursive fill. |
196 | * |
197 | * @param tcx |
198 | * @param node - starting node, this or next node will be left node |
199 | */ |
200 | void FillBasin(SweepContext& tcx, Node& node); |
201 | |
202 | /** |
203 | * Recursive algorithm to fill a Basin with triangles |
204 | * |
205 | * @param tcx |
206 | * @param node - bottom_node |
207 | * @param cnt - counter used to alternate on even and odd numbers |
208 | */ |
209 | void FillBasinReq(SweepContext& tcx, Node* node); |
210 | |
211 | bool IsShallow(SweepContext& tcx, Node& node); |
212 | |
213 | bool IsEdgeSideOfTriangle(Triangle& triangle, Point& ep, Point& eq); |
214 | |
215 | void FillEdgeEvent(SweepContext& tcx, Edge* edge, Node* node); |
216 | |
217 | void FillRightAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node); |
218 | |
219 | void FillRightBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); |
220 | |
221 | void FillRightConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); |
222 | |
223 | void FillRightConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); |
224 | |
225 | void FillLeftAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node); |
226 | |
227 | void FillLeftBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); |
228 | |
229 | void FillLeftConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); |
230 | |
231 | void FillLeftConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); |
232 | |
233 | void FlipEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* t, Point& p); |
234 | |
235 | /** |
236 | * After a flip we have two triangles and know that only one will still be |
237 | * intersecting the edge. So decide which to contiune with and legalize the other |
238 | * |
239 | * @param tcx |
240 | * @param o - should be the result of an orient2d( eq, op, ep ) |
241 | * @param t - triangle 1 |
242 | * @param ot - triangle 2 |
243 | * @param p - a point shared by both triangles |
244 | * @param op - another point shared by both triangles |
245 | * @return returns the triangle still intersecting the edge |
246 | */ |
247 | Triangle& NextFlipTriangle(SweepContext& tcx, int o, Triangle& t, Triangle& ot, Point& p, Point& op); |
248 | |
249 | /** |
250 | * When we need to traverse from one triangle to the next we need |
251 | * the point in current triangle that is the opposite point to the next |
252 | * triangle. |
253 | * |
254 | * @param ep |
255 | * @param eq |
256 | * @param ot |
257 | * @param op |
258 | * @return |
259 | */ |
260 | Point& NextFlipPoint(Point& ep, Point& eq, Triangle& ot, Point& op); |
261 | |
262 | /** |
263 | * Scan part of the FlipScan algorithm<br> |
264 | * When a triangle pair isn't flippable we will scan for the next |
265 | * point that is inside the flip triangle scan area. When found |
266 | * we generate a new flipEdgeEvent |
267 | * |
268 | * @param tcx |
269 | * @param ep - last point on the edge we are traversing |
270 | * @param eq - first point on the edge we are traversing |
271 | * @param flipTriangle - the current triangle sharing the point eq with edge |
272 | * @param t |
273 | * @param p |
274 | */ |
275 | void FlipScanEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle& flip_triangle, Triangle& t, Point& p); |
276 | |
277 | void FinalizationPolygon(SweepContext& tcx); |
278 | |
279 | std::vector<Node*> nodes_; |
280 | |
281 | }; |
282 | |
283 | } |
284 | |
285 | #endif |
286 | |