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