Branch data Line data Source code
1 : : /*
2 : : * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
3 : : * https://github.com/jhasse/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 : 13 : 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(const Point& pa, const Point& pb, const Point& pc, const Point& pd) const;
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) const;
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(const Node* node) const;
175 : : bool AngleExceeds90Degrees(const Point* origin, const Point* pa, const Point* pb) const;
176 : : bool AngleExceedsPlus90DegreesOrIsNegative(const Point* origin, const Point* pa, const Point* pb) const;
177 : : double Angle(const Point* origin, const Point* pa, const Point* pb) const;
178 : :
179 : : /**
180 : : *
181 : : * @param node - middle node
182 : : * @return the angle between 3 front nodes
183 : : */
184 : : double HoleAngle(const Node& node) const;
185 : :
186 : : /**
187 : : * The basin angle is decided against the horizontal line [1,0]
188 : : */
189 : : double BasinAngle(const Node& node) const;
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
|
