1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
//
// libavg - Media Playback Engine.
// Copyright (C) 2003-2014 Ulrich von Zadow
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
// Current versions can be found at www.libavg.de
//
//
// Based on Poly2Tri algorithm.
// Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
// http://code.google.com/p/poly2tri/
//
#ifndef SWEEP_H
#define SWEEP_H
#include <vector>
namespace avg {
class SweepContext;
struct Node;
struct Point;
struct Edge;
class TriangulationTriangle;
class Sweep
{
public:
void Triangulate(SweepContext& sc);
~Sweep();
private:
void sweepPoints(SweepContext& sc);
Node& pointEvent(SweepContext& sc, Point& point);
void edgeEvent(SweepContext& sc, Edge* edge, Node* node);
void edgeEvent(SweepContext& sc, Point& ep, Point& eq,
TriangulationTriangle* triangle, Point& point);
Node& newFrontTriangle(SweepContext& sc, Point& point, Node& node);
void fill(SweepContext& sc, Node& node);
bool legalize(SweepContext& sc, TriangulationTriangle& t);
/**
* <b>Requirement</b>:<br>
* 1. a,b and c form a triangle.<br>
* 2. a and d is know to be on opposite side of bc<br>
* <pre>
* a
* +
* / \
* / \
* b/ \c
* +-------+
* / d \
* / \
* </pre>
* <b>Fact</b>: d has to be in area B to have a chance to be inside the circle formed by
* a,b and c<br>
* d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW<br>
* This preknowledge gives us a way to optimize the incircle test
* @param a - triangle point, opposite d
* @param b - triangle point
* @param c - triangle point
* @param d - point opposite a
* @return true if d is inside circle, false if on circle edge
*/
bool incircle(Point& pa, Point& pb, Point& pc, Point& pd);
/**
* Rotates a triangle pair one vertex CW
*<pre>
* n2 n2
* P +-----+ P +-----+
* | t /| |\ t |
* | / | | \ |
* n1| / |n3 n1| \ |n3
* | / | after CW | \ |
* |/ oT | | oT \|
* +-----+ oP +-----+
* n4 n4
* </pre>
*/
void rotateTrianglePair(TriangulationTriangle& t, Point& p, TriangulationTriangle& ot,
Point& op);
void fillAdvancingFront(SweepContext& sc, Node& n);
double holeAngle(Node& node);
/**
* The basin angle is decided against the horizontal line [1,0]
*/
double basinAngle(Node& node);
void fillBasin(SweepContext& sc, Node& node);
void fillBasinReq(SweepContext& sc, Node* node);
bool isShallow(SweepContext& sc, Node& node);
bool isEdgeSideOfTriangle(TriangulationTriangle& triangle, Point& ep, Point& eq);
void fillEdgeEvent(SweepContext& sc, Edge* edge, Node* node);
void fillRightAboveEdgeEvent(SweepContext& sc, Edge* edge, Node* node);
void fillRightBelowEdgeEvent(SweepContext& sc, Edge* edge, Node& node);
void fillRightConcaveEdgeEvent(SweepContext& sc, Edge* edge, Node& node);
void fillRightConvexEdgeEvent(SweepContext& sc, Edge* edge, Node& node);
void fillLeftAboveEdgeEvent(SweepContext& sc, Edge* edge, Node* node);
void fillLeftBelowEdgeEvent(SweepContext& sc, Edge* edge, Node& node);
void fillLeftConcaveEdgeEvent(SweepContext& sc, Edge* edge, Node& node);
void fillLeftConvexEdgeEvent(SweepContext& sc, Edge* edge, Node& node);
void flipEdgeEvent(SweepContext& sc, Point& ep, Point& eq, TriangulationTriangle* t,
Point& p);
/**
* After a flip we have two triangles and know that only one will still be
* intersecting the edge. So decide which to contiune with and legalize the other
*
* @param sc
* @param o - should be the result of an orient2d( eq, op, ep )
* @param t - triangle 1
* @param ot - triangle 2
* @param p - a point shared by both triangles
* @param op - another point shared by both triangles
* @return returns the triangle still intersecting the edge
*/
TriangulationTriangle& nextFlipTriangle(SweepContext& sc, int o,
TriangulationTriangle& t, TriangulationTriangle& ot, Point& p, Point& op);
/**
* When we need to traverse from one triangle to the next we need
* the point in current triangle that is the opposite point to the next
* triangle.
*
* @param ep
* @param eq
* @param ot
* @param op
* @return
*/
Point& nextFlipPoint(Point& ep, Point& eq, TriangulationTriangle& ot, Point& op);
/**
* Scan part of the FlipScan algorithm<br>
* When a triangle pair isn't flippable we will scan for the next
* point that is inside the flip triangle scan area. When found
* we generate a new flipEdgeEvent
*
* @param sc
* @param ep - last point on the edge we are traversing
* @param eq - first point on the edge we are traversing
* @param flipTriangle - the current triangle sharing the point eq with edge
* @param t
* @param p
*/
void flipScanEdgeEvent(SweepContext& sc, Point& ep, Point& eq,
TriangulationTriangle& flip_triangle, TriangulationTriangle& t, Point& p);
void finalizationPolygon(SweepContext& sc);
std::vector<Node*> m_Nodes;
unsigned int arrayCount;
};
}
#endif
|
