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
44namespace p2t {
45
46class SweepContext;
47struct Node;
48struct Point;
49struct Edge;
50class Triangle;
51
52class Sweep
53{
54public:
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
68private:
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

source code of qtlocation/src/3rdparty/poly2tri/sweep/sweep.h