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
35namespace p2t {
36
37SweepContext::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
53void 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
61void SweepContext::AddPoint(Point* point) {
62 points_.push_back(x: point);
63}
64
65std::vector<Triangle*> SweepContext::GetTriangles()
66{
67 return triangles_;
68}
69
70std::list<Triangle*> SweepContext::GetMap()
71{
72 return map_;
73}
74
75void 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
103void 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
112Point* SweepContext::GetPoint(const int& index)
113{
114 return points_[index];
115}
116
117void SweepContext::AddToMap(Triangle* triangle)
118{
119 map_.push_back(x: triangle);
120}
121
122Node& SweepContext::LocateNode(Point& point)
123{
124 // TODO implement search tree
125 return *front_->LocateNode(x: point.x);
126}
127
128void 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
150void SweepContext::RemoveNode(Node* node)
151{
152 delete node;
153}
154
155void 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
166void SweepContext::RemoveFromMap(Triangle* triangle)
167{
168 map_.remove(value: triangle);
169}
170
171void 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
191SweepContext::~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

source code of qtlocation/src/3rdparty/poly2tri/sweep/sweep_context.cpp