20 sum += ( ( p2.
x - p1.
x ) * ( p2.
y + p1.
y ) );
23 VECTOR2I last_pt{ std::numeric_limits<int>::max(), std::numeric_limits<int>::max() };
25 auto addVertex = [&](
int i )
38 for(
int i = points.
PointCount() - 1; i >= 0; i-- )
47 if( tail && ( *tail == *tail->
next ) )
66 x = ( x | ( x << 8 ) ) & 0x00FF00FF;
67 x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
68 x = ( x | ( x << 2 ) ) & 0x33333333;
69 x = ( x | ( x << 1 ) ) & 0x55555555;
71 y = ( y | ( y << 8 ) ) & 0x00FF00FF;
72 y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
73 y = ( y | ( y << 2 ) ) & 0x33333333;
74 y = ( y | ( y << 1 ) ) & 0x55555555;
76 return x | ( y << 1 );
85 return ( q->
y - p->
y ) * ( r->
x - q->
x ) - ( q->
x - p->
x ) * ( r->
y - q->
y );
91 return aA && aB && aA->
x == aB->
x && aA->
y == aB->
y;
107 && aPt->
y == aPt->
next->
y )
113 && aPt->
y == aPt->
next->
y )
134 && aPt->
y == aPt->
prev->
y)
140 && aPt->
y == aPt->
prev->
y )
155 if(
area( ap, a, an ) < 0 )
156 return area( a, b, an ) >= 0 &&
area( a, ap, b ) >= 0;
158 return area( a, b, ap ) < 0 ||
area( a, an, b ) < 0;
166 double px = ( a->
x + b->
x ) / 2;
167 double py = ( a->
y + b->
y ) / 2;
171 if( ( ( p->
y > py ) != ( p->
next->
y > py ) )
172 && ( px < ( p->
next->
x - p->
x ) * ( py - p->
y ) / ( p->
next->
y - p->
y ) + p->
x ) )
189 m_vertices.emplace_back( aIndex, pt.
x, pt.
y,
this, aUserData );
253 const double minTX = std::min( a->
x, std::min( b->
x, c->
x ) );
254 const double minTY = std::min( a->
y, std::min( b->
y, c->
y ) );
255 const double maxTX = std::max( a->
x, std::max( b->
x, c->
x ) );
256 const double maxTY = std::max( a->
y, std::max( b->
y, c->
y ) );
265 while( p && p->
z <= maxZ )
278 while( p && p->
z >= minZ )
size_type GetHeight() const
size_type GetWidth() const
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
std::deque< VERTEX > m_vertices
int32_t zOrder(const double aX, const double aY) const
Note that while the inputs are doubles, these are scaled by the size of the bounding box to fit into ...
bool middleInside(const VERTEX *a, const VERTEX *b) const
Check if the middle of the segment from a to b is inside the polygon.
VERTEX * createList(const SHAPE_LINE_CHAIN &points, VERTEX *aTail=nullptr, void *aUserData=nullptr)
Create a list of vertices from a line chain.
bool locallyInside(const VERTEX *a, const VERTEX *b) const
Check whether the segment from vertex a -> vertex b is inside the polygon around the immediate area o...
VERTEX * getPrevOutlineVertex(const VERTEX *aPt) const
Get the previous vertex in the outline, avoiding steiner points and points that overlap with splits.
void SetBoundingBox(const BOX2I &aBBox)
double area(const VERTEX *p, const VERTEX *q, const VERTEX *r) const
Return the twice the signed area of the triangle formed by vertices p, q, and r.
VERTEX * insertVertex(int aIndex, const VECTOR2I &pt, VERTEX *last, void *aUserData=nullptr)
Insert a vertex into the vertex set.
VECTOR2I::extended_type m_simplificationLevel
VERTEX * getNextOutlineVertex(const VERTEX *aPt) const
Get the next vertex in the outline, avoiding steiner points and points that overlap with splits.
bool same_point(const VERTEX *aA, const VERTEX *aB) const
Check if two vertices are at the same point.
VERTEX * split(VERTEX *b)
Split the referenced polygon between the reference point and vertex b, assuming they are in the same ...
bool inTriangle(const VERTEX &a, const VERTEX &b, const VERTEX &c)
Check to see if triangle surrounds our current vertex.
void remove()
Remove the node from the linked list and z-ordered linked list.
bool isEar() const
Check whether the given vertex is in the middle of an ear.
VECTOR2< int32_t > VECTOR2I