Horizon
horizon-eda-1.3.0
3rd_party
poly2tri
sweep
sweep.h
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
*/
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
61
void
Triangulate
(
SweepContext
& tcx);
62
66
~Sweep
();
67
68
private
:
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
p2t::Sweep::~Sweep
~Sweep()
Destructor - clean up memory.
p2t
Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V.
Definition:
shapes.cpp:34
p2t::Sweep::Triangulate
void Triangulate(SweepContext &tcx)
Triangulate.
p2t::Edge
Definition:
shapes.h:123
p2t::SweepContext
Definition:
sweep_context.h:51
p2t::Node
Definition:
advancing_front.h:42
p2t::Point
Definition:
shapes.h:45
p2t::Triangle
Definition:
shapes.h:150
Generated by
1.8.20