KiCad PCB EDA Suite
p2t Namespace Reference

Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V. More...

Classes

class  AdvancingFront
 
class  CDT
 
struct  Edge
 
struct  Node
 
struct  Point
 
class  Sweep
 
class  SweepContext
 
class  Triangle
 

Enumerations

enum  Orientation { CW, CCW, COLLINEAR }
 

Functions

bool cmp (const Point *a, const Point *b)
 
Point operator+ (const Point &a, const Point &b)
 Add two points_ component-wise. More...
 
Point operator- (const Point &a, const Point &b)
 Subtract two points_ component-wise. More...
 
Point operator* (double s, const Point &a)
 Multiply point by scalar. More...
 
bool operator== (const Point &a, const Point &b)
 
bool operator!= (const Point &a, const Point &b)
 
double Dot (const Point &a, const Point &b)
 Peform the dot product on two vectors. More...
 
double Cross (const Point &a, const Point &b)
 Perform the cross product on two vectors. In 2D this produces a scalar. More...
 
Point Cross (const Point &a, double s)
 Perform the cross product on a point and a scalar. More...
 
Point Cross (const double s, const Point &a)
 Perform the cross product on a scalar and a point. More...
 
Orientation Orient2d (Point &pa, Point &pb, Point &pc)
 Forumla to calculate signed area
Positive if CCW
Negative if CW
0 if collinear
More...
 
bool InScanArea (Point &pa, Point &pb, Point &pc, Point &pd)
 

Variables

const double PI_3div4 = 3 * M_PI / 4
 
const double PI_div2 = 1.57079632679489661923
 
const double EPSILON = 1e-12
 
const double kAlpha = 0.3
 

Detailed Description

Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V.

Author
Mason Green mason.nosp@m..gre.nosp@m.en@gm.nosp@m.ail..nosp@m.com

and Zalik, B.(2008)'Sweep-line algorithm for constrained Delaunay triangulation', International Journal of Geographical Information Science

"FlipScan" Constrained Edge Algorithm invented by Thomas ┼hlÚn, thahl.nosp@m.en@g.nosp@m.mail..nosp@m.com

Enumeration Type Documentation

Function Documentation

bool p2t::cmp ( const Point a,
const Point b 
)
inline

Definition at line 221 of file shapes.h.

References p2t::Point::x, and p2t::Point::y.

Referenced by SCH_EDIT_FRAME::addCurrentItemToList(), FIELDS_EDITOR_GRID_DATA_MODEL::ExpandRow(), PCB_EDIT_FRAME::RecreateBOMFileFromBoard(), FIELDS_EDITOR_GRID_DATA_MODEL::Sort(), and TrackListSortByNetcode().

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 }
double p2t::Cross ( const Point a,
const Point b 
)
inline

Perform the cross product on two vectors. In 2D this produces a scalar.

Definition at line 269 of file shapes.h.

References p2t::Point::x, and p2t::Point::y.

Referenced by VECTOR2< unsigned int >::operator wxPoint(), and SEG::Side().

270 {
271  return a.x * b.y - a.y * b.x;
272 }
Point p2t::Cross ( const Point a,
double  s 
)
inline

Perform the cross product on a point and a scalar.

In 2D this produces a point.

Definition at line 276 of file shapes.h.

References p2t::Point::Point(), p2t::Point::x, and p2t::Point::y.

277 {
278  return Point(s * a.y, -s * a.x);
279 }
Point p2t::Cross ( const double  s,
const Point a 
)
inline

Perform the cross product on a scalar and a point.

In 2D this produces a point.

Definition at line 283 of file shapes.h.

References p2t::Point::Point(), p2t::Point::x, and p2t::Point::y.

284 {
285  return Point(-s * a.y, s * a.x);
286 }
double p2t::Dot ( const Point a,
const Point b 
)
inline

Peform the dot product on two vectors.

Definition at line 263 of file shapes.h.

References p2t::Point::x, and p2t::Point::y.

Referenced by VECTOR2< unsigned int >::operator wxPoint().

264 {
265  return a.x * b.x + a.y * b.y;
266 }
bool p2t::InScanArea ( Point pa,
Point pb,
Point pc,
Point pd 
)

Definition at line 106 of file polygon/poly2tri/common/utils.h.

References p2t::Point::x, and p2t::Point::y.

107 {
108  double oadb = (pa.x - pb.x)*(pd.y - pb.y) - (pd.x - pb.x)*(pa.y - pb.y);
109  if (oadb >= -EPSILON) {
110  return false;
111  }
112 
113  double oadc = (pa.x - pc.x)*(pd.y - pc.y) - (pd.x - pc.x)*(pa.y - pc.y);
114  if (oadc <= EPSILON) {
115  return false;
116  }
117  return true;
118 }
const double EPSILON
bool p2t::operator!= ( const Point a,
const Point b 
)
inline

Definition at line 257 of file shapes.h.

References p2t::Point::x, and p2t::Point::y.

258 {
259  return !(a.x == b.x) && !(a.y == b.y);
260 }
Point p2t::operator* ( double  s,
const Point a 
)
inline

Multiply point by scalar.

Definition at line 247 of file shapes.h.

References p2t::Point::Point(), p2t::Point::x, and p2t::Point::y.

248 {
249  return Point(s * a.x, s * a.y);
250 }
Point p2t::operator+ ( const Point a,
const Point b 
)
inline

Add two points_ component-wise.

Definition at line 235 of file shapes.h.

References p2t::Point::Point(), p2t::Point::x, and p2t::Point::y.

236 {
237  return Point(a.x + b.x, a.y + b.y);
238 }
Point p2t::operator- ( const Point a,
const Point b 
)
inline

Subtract two points_ component-wise.

Definition at line 241 of file shapes.h.

References p2t::Point::Point(), p2t::Point::x, and p2t::Point::y.

Referenced by VECTOR2< unsigned int >::operator wxPoint().

242 {
243  return Point(a.x - b.x, a.y - b.y);
244 }
bool p2t::operator== ( const Point a,
const Point b 
)
inline

Definition at line 252 of file shapes.h.

References p2t::Point::x, and p2t::Point::y.

253 {
254  return a.x == b.x && a.y == b.y;
255 }
Orientation p2t::Orient2d ( Point pa,
Point pb,
Point pc 
)

Forumla to calculate signed area
Positive if CCW
Negative if CW
0 if collinear

A[P1,P2,P3]  =  (x1*y2 - y1*x2) + (x2*y3 - y2*x3) + (x3*y1 - y3*x1)
             =  (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)

Definition at line 59 of file polygon/poly2tri/common/utils.h.

References CCW, COLLINEAR, CW, p2t::Point::x, and p2t::Point::y.

60 {
61  double detleft = (pa.x - pc.x) * (pb.y - pc.y);
62  double detright = (pa.y - pc.y) * (pb.x - pc.x);
63  double val = detleft - detright;
64  if (val > -EPSILON && val < EPSILON) {
65  return COLLINEAR;
66  } else if (val > 0) {
67  return CCW;
68  }
69  return CW;
70 }
const double EPSILON

Variable Documentation

const double p2t::EPSILON = 1e-12

Definition at line 45 of file polygon/poly2tri/common/utils.h.

const double p2t::kAlpha = 0.3

Definition at line 43 of file sweep_context.h.

const double p2t::PI_3div4 = 3 * M_PI / 4

Definition at line 43 of file polygon/poly2tri/common/utils.h.

const double p2t::PI_div2 = 1.57079632679489661923

Definition at line 44 of file polygon/poly2tri/common/utils.h.