Horizon
Loading...
Searching...
No Matches
sweep.h
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 */
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
61 void Triangulate(SweepContext& tcx);
62
66 ~Sweep();
67
68private:
69
75 void SweepPoints(SweepContext& tcx);
76
86 Node& PointEvent(SweepContext& tcx, Point& point);
87
95 void EdgeEvent(SweepContext& tcx, Edge* edge, Node* node);
96
97 void EdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* triangle, Point& point);
98
107 Node& NewFrontTriangle(SweepContext& tcx, Point& point, Node& node);
108
114 void Fill(SweepContext& tcx, Node& node);
115
119 bool Legalize(SweepContext& tcx, Triangle& t);
120
145 bool Incircle(const Point& pa, const Point& pb, const Point& pc, const Point& pd) const;
146
161 void RotateTrianglePair(Triangle& t, Point& p, Triangle& ot, Point& op) const;
162
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
184 double HoleAngle(const Node& node) const;
185
189 double BasinAngle(const Node& node) const;
190
200 void FillBasin(SweepContext& tcx, Node& node);
201
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
247 Triangle& NextFlipTriangle(SweepContext& tcx, int o, Triangle& t, Triangle& ot, Point& p, Point& op);
248
260 Point& NextFlipPoint(Point& ep, Point& eq, Triangle& ot, Point& op);
261
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
Definition sweep_context.h:51
Definition sweep.h:53
void Triangulate(SweepContext &tcx)
Triangulate.
Definition sweep.cpp:42
~Sweep()
Destructor - clean up memory.
Definition sweep.cpp:795
Definition shapes.h:152
Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V.
Definition shapes.cpp:36
Definition shapes.h:125
Definition advancing_front.h:42
Definition shapes.h:45