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 struct Edge;
43 
44 struct Point
45 {
46  double x, y;
47 
50  {
51  x = 0.0;
52  y = 0.0;
53  }
54 
56  std::vector<Edge*> edge_list;
57 
59  Point( double ax, double ay ) : x( ax ), y( ay ) {}
60 
62  void set_zero()
63  {
64  x = 0.0;
65  y = 0.0;
66  }
67 
69  void set( double x_, double y_ )
70  {
71  x = x_;
72  y = y_;
73  }
74 
76  Point operator -() const
77  {
78  Point v;
79 
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  double len = Length();
115 
116  x /= len;
117  y /= len;
118  return len;
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  {
132  q = &p1;
133  p = &p2;
134  }
135  else if( p1.y == p2.y )
136  {
137  if( p1.x > p2.x )
138  {
139  q = &p1;
140  p = &p2;
141  }
142  else if( p1.x == p2.x )
143  {
144  // Repeat points
145  assert( false );
146  }
147  }
148 
149  q->edge_list.push_back( this );
150  }
151 };
152 
153 // Triangle-based data structures are know to have better performance than quad-edge structures
154 // See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator"
155 // "Triangulations in CGAL"
156 class Triangle
157 {
158 public:
159 
161  Triangle( Point& a, Point& b, Point& c );
162 
166  bool delaunay_edge[3];
167 
168  Point* GetPoint( const int& index );
169  Point* PointCW( Point& point );
170  Point* PointCCW( Point& point );
171  Point* OppositePoint( Triangle& t, Point& p );
172 
173  Triangle* GetNeighbor( const int& index );
174  void MarkNeighbor( Point* p1, Point* p2, Triangle* t );
175  void MarkNeighbor( Triangle& t );
176 
177  void MarkConstrainedEdge( const int index );
178  void MarkConstrainedEdge( Edge& edge );
179  void MarkConstrainedEdge( Point* p, Point* q );
180 
181  int Index( const Point* p );
182  int EdgeIndex( const Point* p1, const Point* p2 );
183 
184  Triangle* NeighborCW( Point& point );
185  Triangle* NeighborCCW( Point& point );
186  bool GetConstrainedEdgeCCW( Point& p );
187  bool GetConstrainedEdgeCW( Point& p );
188  void SetConstrainedEdgeCCW( Point& p, bool ce );
189  void SetConstrainedEdgeCW( Point& p, bool ce );
190  bool GetDelunayEdgeCCW( Point& p );
191  bool GetDelunayEdgeCW( Point& p );
192  void SetDelunayEdgeCCW( Point& p, bool e );
193  void SetDelunayEdgeCW( Point& p, bool e );
194 
195  bool Contains( Point* p );
196  bool Contains( const Edge& e );
197  bool Contains( Point* p, Point* q );
198  void Legalize( Point& point );
199  void Legalize( Point& opoint, Point& npoint );
200 
204  void Clear();
205  void ClearNeighbor( Triangle* triangle );
206  void ClearNeighbors();
207  void ClearDelunayEdges();
208 
209  inline bool IsInterior();
210  inline void IsInterior( bool b );
211 
212  Triangle& NeighborAcross( Point& opoint );
213 
214  void DebugPrint();
215 
216 private:
217 
222 
224  bool interior_;
225 };
226 
227 inline bool cmp( const Point* a, const Point* b )
228 {
229  if( a->y < b->y )
230  {
231  return true;
232  }
233  else if( a->y == b->y )
234  {
235  // Make sure q is point with greater x value
236  if( a->x < b->x )
237  {
238  return true;
239  }
240  }
241 
242  return false;
243 }
244 
245 
247 inline Point operator +( const Point& a, const Point& b )
248 {
249  return Point( a.x + b.x, a.y + b.y );
250 }
251 
252 
254 inline Point operator -( const Point& a, const Point& b )
255 {
256  return Point( a.x - b.x, a.y - b.y );
257 }
258 
259 
261 inline Point operator *( double s, const Point& a )
262 {
263  return Point( s * a.x, s * a.y );
264 }
265 
266 
267 inline bool operator ==( const Point& a, const Point& b )
268 {
269  return a.x == b.x && a.y == b.y;
270 }
271 
272 
273 inline bool operator !=( const Point& a, const Point& b )
274 {
275  return !(a.x == b.x) && !(a.y == b.y);
276 }
277 
278 
280 inline double Dot( const Point& a, const Point& b )
281 {
282  return a.x * b.x + a.y * b.y;
283 }
284 
285 
287 inline double Cross( const Point& a, const Point& b )
288 {
289  return a.x * b.y - a.y * b.x;
290 }
291 
292 
295 inline Point Cross( const Point& a, double s )
296 {
297  return Point( s * a.y, -s * a.x );
298 }
299 
300 
303 inline Point Cross( const double s, const Point& a )
304 {
305  return Point( -s * a.y, s * a.x );
306 }
307 
308 
309 inline Point* Triangle::GetPoint( const int& index )
310 {
311  return points_[index];
312 }
313 
314 
315 inline Triangle* Triangle::GetNeighbor( const int& index )
316 {
317  return neighbors_[index];
318 }
319 
320 
321 inline bool Triangle::Contains( Point* p )
322 {
323  return p == points_[0] || p == points_[1] || p == points_[2];
324 }
325 
326 
327 inline bool Triangle::Contains( const Edge& e )
328 {
329  return Contains( e.p ) && Contains( e.q );
330 }
331 
332 
333 inline bool Triangle::Contains( Point* p, Point* q )
334 {
335  return Contains( p ) && Contains( q );
336 }
337 
338 
339 inline bool Triangle::IsInterior()
340 {
341  return interior_;
342 }
343 
344 
345 inline void Triangle::IsInterior( bool b )
346 {
347  interior_ = b;
348 }
349 }
350 
351 #endif
bool interior_
Has this triangle been marked as an interior triangle?
Definition: shapes.h:224
void DebugPrint()
Point * q
Definition: shapes.h:125
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:164
Point operator*(double s, const Point &a)
Multiply point by scalar.
Definition: shapes.h:261
void operator+=(const Point &v)
Add a point to this point.
Definition: shapes.h:85
double Length() const
Get the length of this point (the norm).
Definition: shapes.h:106
Point * GetPoint(const int &index)
Definition: shapes.h:309
Triangle & NeighborAcross(Point &opoint)
Triangle * NeighborCW(Point &point)
Point(double ax, double ay)
Construct using coordinates.
Definition: shapes.h:59
void SetDelunayEdgeCW(Point &p, bool e)
double y
Definition: shapes.h:46
bool delaunay_edge[3]
Flags to determine if an edge is a Delauney edge.
Definition: shapes.h:166
Triangle * neighbors_[3]
Neighbor list.
Definition: shapes.h:221
int Index(const Point *p)
double x
Definition: shapes.h:46
void MarkConstrainedEdge(const int index)
bool operator==(const Point &a, const Point &b)
Definition: shapes.h:267
Point * PointCCW(Point &point)
Point operator-() const
Negate this point.
Definition: shapes.h:76
Triangle(Point &a, Point &b, Point &c)
Constructor.
bool IsInterior()
Definition: shapes.h:339
void operator*=(double a)
Multiply this point by a scalar.
Definition: shapes.h:99
bool GetDelunayEdgeCCW(Point &p)
Point * points_[3]
Triangle points.
Definition: shapes.h:219
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:69
void SetConstrainedEdgeCCW(Point &p, bool ce)
Point * p
Definition: shapes.h:125
Point operator+(const Point &a, const Point &b)
Add two points_ component-wise.
Definition: shapes.h:247
void ClearNeighbor(Triangle *triangle)
Point()
Default constructor does nothing (for performance).
Definition: shapes.h:49
void operator-=(const Point &v)
Subtract a point from this point.
Definition: shapes.h:92
bool Contains(Point *p)
Definition: shapes.h:321
void set_zero()
Set this point to all zeros.
Definition: shapes.h:62
Point operator-(const Point &a, const Point &b)
Subtract two points_ component-wise.
Definition: shapes.h:254
Triangle * GetNeighbor(const int &index)
Definition: shapes.h:315
double Dot(const Point &a, const Point &b)
Peform the dot product on two vectors.
Definition: shapes.h:280
std::vector< Edge * > edge_list
The edges this point constitutes an upper ending point.
Definition: shapes.h:56
bool operator!=(const Point &a, const Point &b)
Definition: shapes.h:273
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:128
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:227
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:112
double Cross(const Point &a, const Point &b)
Perform the cross product on two vectors. In 2D this produces a scalar.
Definition: shapes.h:287
Point * OppositePoint(Triangle &t, Point &p)
void Clear()
Clears all references to all other triangles and points.