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