Horizon
shapes.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  */
31 
32 // Include guard
33 #ifndef SHAPES_H
34 #define SHAPES_H
35 
36 #include <vector>
37 #include <cstddef>
38 #include <assert.h>
39 #include <cmath>
40 
41 namespace p2t {
42 
43 struct Edge;
44 
45 struct Point {
46 
47  double x, y;
48 
51  {
52  x = 0.0;
53  y = 0.0;
54  }
55 
57  std::vector<Edge*> edge_list;
58 
60  Point(double x, double y) : x(x), y(y) {}
61 
63  void set_zero()
64  {
65  x = 0.0;
66  y = 0.0;
67  }
68 
70  void set(double x_, double y_)
71  {
72  x = x_;
73  y = y_;
74  }
75 
77  Point operator -() const
78  {
79  Point v;
80  v.set(-x, -y);
81  return v;
82  }
83 
85  void operator +=(const Point& v)
86  {
87  x += v.x;
88  y += v.y;
89  }
90 
92  void operator -=(const Point& v)
93  {
94  x -= v.x;
95  y -= v.y;
96  }
97 
99  void operator *=(double a)
100  {
101  x *= a;
102  y *= a;
103  }
104 
106  double Length() const
107  {
108  return sqrt(x * x + y * y);
109  }
110 
112  double Normalize()
113  {
114  const double len = Length();
115  x /= len;
116  y /= len;
117  return len;
118  }
119 
120 };
121 
122 // Represents a simple polygon's edge
123 struct Edge {
124 
125  Point* p, *q;
126 
128  Edge(Point& p1, Point& p2) : p(&p1), q(&p2)
129  {
130  if (p1.y > p2.y) {
131  q = &p1;
132  p = &p2;
133  } else if (p1.y == p2.y) {
134  if (p1.x > p2.x) {
135  q = &p1;
136  p = &p2;
137  } else if (p1.x == p2.x) {
138  // Repeat points
139  assert(false);
140  }
141  }
142 
143  q->edge_list.push_back(this);
144  }
145 };
146 
147 // Triangle-based data structures are know to have better performance than quad-edge structures
148 // See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator"
149 // "Triangulations in CGAL"
150 class Triangle {
151 public:
152 
154 Triangle(Point& a, Point& b, Point& c);
155 
160 
161 Point* GetPoint(int index);
162 Point* PointCW(const Point& point);
163 Point* PointCCW(const Point& point);
164 Point* OppositePoint(Triangle& t, const Point& p);
165 
166 Triangle* GetNeighbor(int index);
167 void MarkNeighbor(Point* p1, Point* p2, Triangle* t);
168 void MarkNeighbor(Triangle& t);
169 
170 void MarkConstrainedEdge(int index);
171 void MarkConstrainedEdge(Edge& edge);
172 void MarkConstrainedEdge(Point* p, Point* q);
173 
174 int Index(const Point* p);
175 int EdgeIndex(const Point* p1, const Point* p2);
176 
177 Triangle* NeighborCW(const Point& point);
178 Triangle* NeighborCCW(const Point& point);
179 bool GetConstrainedEdgeCCW(const Point& p);
180 bool GetConstrainedEdgeCW(const Point& p);
181 void SetConstrainedEdgeCCW(const Point& p, bool ce);
182 void SetConstrainedEdgeCW(const Point& p, bool ce);
183 bool GetDelunayEdgeCCW(const Point& p);
184 bool GetDelunayEdgeCW(const Point& p);
185 void SetDelunayEdgeCCW(const Point& p, bool e);
186 void SetDelunayEdgeCW(const Point& p, bool e);
187 
188 bool Contains(const Point* p);
189 bool Contains(const Edge& e);
190 bool Contains(const Point* p, const Point* q);
191 void Legalize(Point& point);
192 void Legalize(Point& opoint, Point& npoint);
196 void Clear();
197 void ClearNeighbor(const Triangle *triangle);
198 void ClearNeighbors();
199 void ClearDelunayEdges();
200 
201 inline bool IsInterior();
202 inline void IsInterior(bool b);
203 
204 Triangle& NeighborAcross(const Point& opoint);
205 
206 void DebugPrint();
207 
208 private:
209 
211 Point* points_[3];
213 Triangle* neighbors_[3];
214 
216 bool interior_;
217 };
218 
219 inline bool cmp(const Point* a, const Point* b)
220 {
221  if (a->y < b->y) {
222  return true;
223  } else if (a->y == b->y) {
224  // Make sure q is point with greater x value
225  if (a->x < b->x) {
226  return true;
227  }
228  }
229  return false;
230 }
231 
233 inline Point operator +(const Point& a, const Point& b)
234 {
235  return Point(a.x + b.x, a.y + b.y);
236 }
237 
239 inline Point operator -(const Point& a, const Point& b)
240 {
241  return Point(a.x - b.x, a.y - b.y);
242 }
243 
245 inline Point operator *(double s, const Point& a)
246 {
247  return Point(s * a.x, s * a.y);
248 }
249 
250 inline bool operator ==(const Point& a, const Point& b)
251 {
252  return a.x == b.x && a.y == b.y;
253 }
254 
255 inline bool operator !=(const Point& a, const Point& b)
256 {
257  return !(a.x == b.x) && !(a.y == b.y);
258 }
259 
261 inline double Dot(const Point& a, const Point& b)
262 {
263  return a.x * b.x + a.y * b.y;
264 }
265 
267 inline double Cross(const Point& a, const Point& b)
268 {
269  return a.x * b.y - a.y * b.x;
270 }
271 
274 inline Point Cross(const Point& a, double s)
275 {
276  return Point(s * a.y, -s * a.x);
277 }
278 
281 inline Point Cross(double s, const Point& a)
282 {
283  return Point(-s * a.y, s * a.x);
284 }
285 
286 inline Point* Triangle::GetPoint(int index)
287 {
288  return points_[index];
289 }
290 
291 inline Triangle* Triangle::GetNeighbor(int index)
292 {
293  return neighbors_[index];
294 }
295 
296 inline bool Triangle::Contains(const Point* p)
297 {
298  return p == points_[0] || p == points_[1] || p == points_[2];
299 }
300 
301 inline bool Triangle::Contains(const Edge& e)
302 {
303  return Contains(e.p) && Contains(e.q);
304 }
305 
306 inline bool Triangle::Contains(const Point* p, const Point* q)
307 {
308  return Contains(p) && Contains(q);
309 }
310 
311 inline bool Triangle::IsInterior()
312 {
313  return interior_;
314 }
315 
316 inline void Triangle::IsInterior(bool b)
317 {
318  interior_ = b;
319 }
320 
321 }
322 
323 #endif
p2t::Point::Length
double Length() const
Get the length of this point (the norm).
Definition: shapes.h:106
p2t::Triangle::Triangle
Triangle(Point &a, Point &b, Point &c)
Constructor.
Definition: shapes.cpp:36
p2t::Cross
double Cross(const Point &a, const Point &b)
Perform the cross product on two vectors. In 2D this produces a scalar.
Definition: shapes.h:267
p2t::Point::edge_list
std::vector< Edge * > edge_list
The edges this point constitutes an upper ending point.
Definition: shapes.h:57
p2t
Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V.
Definition: shapes.cpp:34
p2t::operator+
Point operator+(const Point &a, const Point &b)
Add two points_ component-wise.
Definition: shapes.h:233
p2t::Edge
Definition: shapes.h:123
p2t::Edge::Edge
Edge(Point &p1, Point &p2)
Constructor.
Definition: shapes.h:128
p2t::Point::Normalize
double Normalize()
Convert this point into a unit point. Returns the Length.
Definition: shapes.h:112
p2t::Point::operator-=
void operator-=(const Point &v)
Subtract a point from this point.
Definition: shapes.h:92
p2t::Point::operator+=
void operator+=(const Point &v)
Add a point to this point.
Definition: shapes.h:85
p2t::Point::operator-
Point operator-() const
Negate this point.
Definition: shapes.h:77
p2t::Point::set
void set(double x_, double y_)
Set this point to some specified coordinates.
Definition: shapes.h:70
p2t::Triangle::delaunay_edge
bool delaunay_edge[3]
Flags to determine if an edge is a Delauney edge.
Definition: shapes.h:159
p2t::Point::operator*=
void operator*=(double a)
Multiply this point by a scalar.
Definition: shapes.h:99
p2t::Point
Definition: shapes.h:45
p2t::Point::Point
Point()
Default constructor does nothing (for performance).
Definition: shapes.h:50
p2t::Triangle::constrained_edge
bool constrained_edge[3]
Flags to determine if an edge is a Constrained edge.
Definition: shapes.h:157
p2t::Triangle::Clear
void Clear()
Clears all references to all other triangles and points.
Definition: shapes.cpp:76
p2t::Point::Point
Point(double x, double y)
Construct using coordinates.
Definition: shapes.h:60
p2t::operator*
Point operator*(double s, const Point &a)
Multiply point by scalar.
Definition: shapes.h:245
p2t::Triangle
Definition: shapes.h:150
p2t::Point::set_zero
void set_zero()
Set this point to all zeros.
Definition: shapes.h:63
p2t::operator-
Point operator-(const Point &a, const Point &b)
Subtract two points_ component-wise.
Definition: shapes.h:239
p2t::Dot
double Dot(const Point &a, const Point &b)
Peform the dot product on two vectors.
Definition: shapes.h:261