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 : : #include "sweep_context.h"
32 : : #include <algorithm>
33 : : #include "advancing_front.h"
34 : :
35 : : namespace p2t {
36 : :
37 : 13 : SweepContext::SweepContext(const std::vector<Point*>& polyline) : points_(polyline),
38 : 13 : front_(0),
39 : 13 : head_(0),
40 : 13 : tail_(0),
41 : 13 : af_head_(0),
42 : 13 : af_middle_(0),
43 : 13 : af_tail_(0)
44 : : {
45 : 13 : InitEdges(points_);
46 : 13 : }
47 : :
48 : 13 : void SweepContext::AddHole(const std::vector<Point*>& polyline)
49 : : {
50 : 13 : InitEdges(polyline);
51 : 52 : for(unsigned int i = 0; i < polyline.size(); i++) {
52 : 39 : points_.push_back(polyline[i]);
53 : 39 : }
54 : 13 : }
55 : :
56 : 0 : void SweepContext::AddPoint(Point* point) {
57 : 0 : points_.push_back(point);
58 : 0 : }
59 : :
60 : 13 : std::vector<Triangle*> &SweepContext::GetTriangles()
61 : : {
62 : 13 : return triangles_;
63 : : }
64 : :
65 : 0 : std::list<Triangle*> &SweepContext::GetMap()
66 : : {
67 : 0 : return map_;
68 : : }
69 : :
70 : 13 : void SweepContext::InitTriangulation()
71 : : {
72 : 13 : double xmax(points_[0]->x), xmin(points_[0]->x);
73 : 13 : double ymax(points_[0]->y), ymin(points_[0]->y);
74 : :
75 : : // Calculate bounds.
76 : 104 : for (unsigned int i = 0; i < points_.size(); i++) {
77 : 91 : Point& p = *points_[i];
78 : 91 : if (p.x > xmax)
79 : 13 : xmax = p.x;
80 : 91 : if (p.x < xmin)
81 : 0 : xmin = p.x;
82 : 91 : if (p.y > ymax)
83 : 13 : ymax = p.y;
84 : 91 : if (p.y < ymin)
85 : 0 : ymin = p.y;
86 : 91 : }
87 : :
88 : 13 : double dx = kAlpha * (xmax - xmin);
89 : 13 : double dy = kAlpha * (ymax - ymin);
90 : 13 : head_ = new Point(xmax + dx, ymin - dy);
91 : 13 : tail_ = new Point(xmin - dx, ymin - dy);
92 : :
93 : : // Sort points along y-axis
94 : 13 : std::sort(points_.begin(), points_.end(), cmp);
95 : :
96 : 13 : }
97 : :
98 : 26 : void SweepContext::InitEdges(const std::vector<Point*>& polyline)
99 : : {
100 : 26 : size_t num_points = polyline.size();
101 : 117 : for (size_t i = 0; i < num_points; i++) {
102 : 91 : size_t j = i < num_points - 1 ? i + 1 : 0;
103 : 91 : edge_list.push_back(new Edge(*polyline[i], *polyline[j]));
104 : 91 : }
105 : 26 : }
106 : :
107 : 78 : Point* SweepContext::GetPoint(size_t index)
108 : : {
109 : 78 : return points_[index];
110 : : }
111 : :
112 : 143 : void SweepContext::AddToMap(Triangle* triangle)
113 : : {
114 : 143 : map_.push_back(triangle);
115 : 143 : }
116 : :
117 : 78 : Node& SweepContext::LocateNode(const Point& point)
118 : : {
119 : : // TODO implement search tree
120 : 78 : return *front_->LocateNode(point.x);
121 : : }
122 : :
123 : 13 : void SweepContext::CreateAdvancingFront()
124 : : {
125 : :
126 : : // Initial triangle
127 : 13 : Triangle* triangle = new Triangle(*points_[0], *tail_, *head_);
128 : :
129 : 13 : map_.push_back(triangle);
130 : :
131 : 13 : af_head_ = new Node(*triangle->GetPoint(1), *triangle);
132 : 13 : af_middle_ = new Node(*triangle->GetPoint(0), *triangle);
133 : 13 : af_tail_ = new Node(*triangle->GetPoint(2));
134 : 13 : front_ = new AdvancingFront(*af_head_, *af_tail_);
135 : :
136 : : // TODO: More intuitive if head is middles next and not previous?
137 : : // so swap head and tail
138 : 13 : af_head_->next = af_middle_;
139 : 13 : af_middle_->next = af_tail_;
140 : 13 : af_middle_->prev = af_head_;
141 : 13 : af_tail_->prev = af_middle_;
142 : 13 : }
143 : :
144 : 0 : void SweepContext::RemoveNode(Node* node)
145 : : {
146 : 0 : delete node;
147 : 0 : }
148 : :
149 : 156 : void SweepContext::MapTriangleToNodes(Triangle& t)
150 : : {
151 : 624 : for (int i = 0; i < 3; i++) {
152 : 468 : if (!t.GetNeighbor(i)) {
153 : 234 : Node* n = front_->LocatePoint(t.PointCW(*t.GetPoint(i)));
154 : 234 : if (n)
155 : 234 : n->triangle = &t;
156 : 234 : }
157 : 468 : }
158 : 156 : }
159 : :
160 : 0 : void SweepContext::RemoveFromMap(Triangle* triangle)
161 : : {
162 : 0 : map_.remove(triangle);
163 : 0 : }
164 : :
165 : 13 : void SweepContext::MeshClean(Triangle& triangle)
166 : : {
167 : 13 : std::vector<Triangle *> triangles;
168 : 13 : triangles.push_back(&triangle);
169 : :
170 : 208 : while(!triangles.empty()){
171 : 195 : Triangle *t = triangles.back();
172 : 195 : triangles.pop_back();
173 : :
174 : 195 : if (t != NULL && !t->IsInterior()) {
175 : 91 : t->IsInterior(true);
176 : 91 : triangles_.push_back(t);
177 : 364 : for (int i = 0; i < 3; i++) {
178 : 273 : if (!t->constrained_edge[i])
179 : 182 : triangles.push_back(t->GetNeighbor(i));
180 : 273 : }
181 : 91 : }
182 : : }
183 : 13 : }
184 : :
185 : 13 : SweepContext::~SweepContext()
186 : : {
187 : :
188 : : // Clean up memory
189 : :
190 : 13 : delete head_;
191 : 13 : delete tail_;
192 : 13 : delete front_;
193 : 13 : delete af_head_;
194 : 13 : delete af_middle_;
195 : 13 : delete af_tail_;
196 : :
197 : : typedef std::list<Triangle*> type_list;
198 : :
199 : 169 : for(type_list::iterator iter = map_.begin(); iter != map_.end(); ++iter) {
200 : 156 : Triangle* ptr = *iter;
201 : 156 : delete ptr;
202 : 156 : }
203 : :
204 : 104 : for(unsigned int i = 0; i < edge_list.size(); i++) {
205 : 91 : delete edge_list[i];
206 : 91 : }
207 : :
208 : 13 : }
209 : :
210 : : }
|
