libosmscout
0.1
|
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 | Cross (const double s, const Point &a) |
Perform the cross product on a scalar and a point. 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... | |
double | Dot (const Point &a, const Point &b) |
Peform the dot product on two vectors. More... | |
bool | InScanArea (Point &pa, Point &pb, Point &pc, Point &pd) |
bool | operator!= (const Point &a, const Point &b) |
Point | operator* (double s, const Point &a) |
Multiply point by scalar. More... | |
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... | |
bool | operator== (const Point &a, const Point &b) |
Orientation | Orient2d (const Point &pa, const Point &pb, const Point &pc) |
Formula to calculate signed area Positive if CCW Negative if CW 0 if collinear More... | |
Variables | |
const double | EPSILON = 1e-12 |
const double | kAlpha = 0.3 |
const double | PI_3div4 = 3 * M_PI / 4 |
const double | PI_div2 = 1.57079632679489661923 |
Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V.
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 en@g mail. com
enum p2t::Orientation |
References p2t::Point::x, and p2t::Point::y.
Perform the cross product on a scalar and a point.
In 2D this produces a point.
References p2t::Point::x, and p2t::Point::y.
Perform the cross product on two vectors. In 2D this produces a scalar.
References p2t::Point::x, and p2t::Point::y.
Perform the cross product on a point and a scalar.
In 2D this produces a point.
References p2t::Point::x, and p2t::Point::y.
Peform the dot product on two vectors.
References p2t::Point::x, and p2t::Point::y.
References EPSILON, p2t::Point::x, and p2t::Point::y.
References p2t::Point::x, and p2t::Point::y.
Multiply point by scalar.
References p2t::Point::x, and p2t::Point::y.
Add two points_ component-wise.
References p2t::Point::x, and p2t::Point::y.
Subtract two points_ component-wise.
References p2t::Point::x, and p2t::Point::y.
References p2t::Point::x, and p2t::Point::y.
Orientation p2t::Orient2d | ( | const Point & | pa, |
const Point & | pb, | ||
const Point & | pc | ||
) |
Formula 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)
References CCW, COLLINEAR, CW, EPSILON, p2t::Point::x, and p2t::Point::y.
const double p2t::EPSILON = 1e-12 |
Referenced by InScanArea(), and Orient2d().
const double p2t::kAlpha = 0.3 |
const double p2t::PI_3div4 = 3 * M_PI / 4 |
const double p2t::PI_div2 = 1.57079632679489661923 |