38 sum += ( ( p2.
x - p1.
x ) * ( p2.
y + p1.
y ) );
41 VECTOR2I last_pt{ std::numeric_limits<int>::max(), std::numeric_limits<int>::max() };
43 auto addVertex = [&](
int i )
56 for(
int i = points.
PointCount() - 1; i >= 0; i-- )
65 if( tail && ( *tail == *tail->
next ) )
84 uint32_t x =
static_cast<uint32_t
>( limit_x * 32767.0 );
85 uint32_t y =
static_cast<uint32_t
>( limit_y * 32767.0 );
87 x = ( x | ( x << 8 ) ) & 0x00FF00FF;
88 x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
89 x = ( x | ( x << 2 ) ) & 0x33333333;
90 x = ( x | ( x << 1 ) ) & 0x55555555;
92 y = ( y | ( y << 8 ) ) & 0x00FF00FF;
93 y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
94 y = ( y | ( y << 2 ) ) & 0x33333333;
95 y = ( y | ( y << 1 ) ) & 0x55555555;
97 return x | ( y << 1 );
106 return ( q->
y - p->
y ) * ( r->
x - q->
x ) - ( q->
x - p->
x ) * ( r->
y - q->
y );
112 return aA && aB && aA->
x == aB->
x && aA->
y == aB->
y;
128 && aPt->
y == aPt->
next->
y )
134 && aPt->
y == aPt->
next->
y )
155 && aPt->
y == aPt->
prev->
y)
161 && aPt->
y == aPt->
prev->
y )
176 if(
area( ap, a, an ) < 0 )
177 return area( a, b, an ) >= 0 &&
area( a, ap, b ) >= 0;
179 return area( a, b, ap ) < 0 ||
area( a, an, b ) < 0;
187 double px = ( a->
x + b->
x ) / 2;
188 double py = ( a->
y + b->
y ) / 2;
192 if( ( ( p->
y > py ) != ( p->
next->
y > py ) )
193 && ( px < ( p->
next->
x - p->
x ) * ( py - p->
y ) / ( p->
next->
y - p->
y ) + p->
x ) )
210 m_vertices.emplace_back( aIndex, pt.
x, pt.
y,
this, aUserData );
283 const double minTX = std::min( a->
x, std::min( b->
x, c->
x ) );
284 const double minTY = std::min( a->
y, std::min( b->
y, c->
y ) );
285 const double maxTX = std::max( a->
x, std::max( b->
x, c->
x ) );
286 const double maxTY = std::max( a->
y, std::max( b->
y, c->
y ) );
295 while( p && p->
z <= maxZ )
309 while( p && p->
z >= minZ )
constexpr coord_type GetY() const
constexpr size_type GetWidth() const
constexpr coord_type GetX() const
constexpr size_type GetHeight() 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.
constexpr 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
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.
uint32_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 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 * GetUserData() const
void remove()
Remove the node from the linked list and z-ordered linked list.
bool isEar(bool aMatchUserData=false) const
Check whether the given vertex is in the middle of an ear.
VECTOR2< int32_t > VECTOR2I