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 #ifndef SWEEP_CONTEXT_H
33 #define SWEEP_CONTEXT_H
34
35 #include <list>
36 #include <vector>
37 #include <cstddef>
38
39 namespace p2t {
40
41 // Inital triangle factor, seed triangle will extend 30% of
42 // PointSet width to both left and right.
43 const double kAlpha = 0.3;
44
45 struct Point;
46 class Triangle;
47 struct Node;
48 struct Edge;
49 class AdvancingFront;
50
51 class SweepContext {
52 public:
53
54 /// Constructor
55 SweepContext(const std::vector<Point*>& polyline);
56 /// Destructor
57 ~SweepContext();
58
59 void set_head(Point* p1);
60
61 Point* head() const;
62
63 void set_tail(Point* p1);
64
65 Point* tail() const;
66
67 size_t point_count() const;
68
69 Node& LocateNode(const Point& point);
70
71 void RemoveNode(Node* node);
72
73 void CreateAdvancingFront();
74
75 /// Try to map a node to all sides of this triangle that don't have a neighbor
76 void MapTriangleToNodes(Triangle& t);
77
78 void AddToMap(Triangle* triangle);
79
80 Point* GetPoint(size_t index);
81
82 Point* GetPoints();
83
84 void RemoveFromMap(Triangle* triangle);
85
86 void AddHole(const std::vector<Point*>& polyline);
87
88 void AddPoint(Point* point);
89
90 AdvancingFront* front() const;
91
92 void MeshClean(Triangle& triangle);
93
94 std::vector<Triangle*> &GetTriangles();
95 std::list<Triangle*> &GetMap();
96
97 std::vector<Edge*> edge_list;
98
99 struct Basin {
100 Node* left_node;
101 Node* bottom_node;
102 Node* right_node;
103 double width;
104 bool left_highest;
105
BasinBasin106 Basin() : left_node(NULL), bottom_node(NULL), right_node(NULL), width(0.0), left_highest(false)
107 {
108 }
109
ClearBasin110 void Clear()
111 {
112 left_node = NULL;
113 bottom_node = NULL;
114 right_node = NULL;
115 width = 0.0;
116 left_highest = false;
117 }
118 };
119
120 struct EdgeEvent {
121 Edge* constrained_edge;
122 bool right;
123
EdgeEventEdgeEvent124 EdgeEvent() : constrained_edge(NULL), right(false)
125 {
126 }
127 };
128
129 Basin basin;
130 EdgeEvent edge_event;
131
132 private:
133
134 friend class Sweep;
135
136 std::vector<Triangle*> triangles_;
137 std::list<Triangle*> map_;
138 std::vector<Point*> points_;
139
140 // Advancing front
141 AdvancingFront* front_;
142 // head point used with advancing front
143 Point* head_;
144 // tail point used with advancing front
145 Point* tail_;
146
147 Node *af_head_, *af_middle_, *af_tail_;
148
149 void InitTriangulation();
150 void InitEdges(const std::vector<Point*>& polyline);
151
152 };
153
front()154 inline AdvancingFront* SweepContext::front() const
155 {
156 return front_;
157 }
158
point_count()159 inline size_t SweepContext::point_count() const
160 {
161 return points_.size();
162 }
163
set_head(Point * p1)164 inline void SweepContext::set_head(Point* p1)
165 {
166 head_ = p1;
167 }
168
head()169 inline Point* SweepContext::head() const
170 {
171 return head_;
172 }
173
set_tail(Point * p1)174 inline void SweepContext::set_tail(Point* p1)
175 {
176 tail_ = p1;
177 }
178
tail()179 inline Point* SweepContext::tail() const
180 {
181 return tail_;
182 }
183
184 }
185
186 #endif
187