46#ifndef __POLYGON_TRIANGULATION_H
47#define __POLYGON_TRIANGULATION_H
78 if( !firstVertex || firstVertex->
prev == firstVertex->
next )
104 return this->
x == rhs.
x && this->
y == rhs.
y;
204 std::deque<Vertex*> queue;
206 queue.push_back(
this );
208 for(
auto p =
next; p && p !=
this; p = p->
next )
209 queue.push_back( p );
211 std::sort( queue.begin(), queue.end(), [](
const Vertex* a,
const Vertex* b )
225 Vertex* prev_elem =
nullptr;
227 for(
auto elem : queue )
230 prev_elem->
nextZ = elem;
232 elem->
prevZ = prev_elem;
236 prev_elem->
nextZ =
nullptr;
245 return ( c.
x -
x ) * ( a.
y -
y ) - ( a.
x -
x ) * ( c.
y -
y ) >= 0
246 && ( a.
x -
x ) * ( b.
y -
y ) - ( b.
x -
x ) * ( a.
y -
y ) >= 0
247 && ( b.
x -
x ) * ( c.
y -
y ) - ( c.
x -
x ) * ( b.
y -
y ) >= 0;
272 int32_t
zOrder(
const double aX,
const double aY )
const
277 x = ( x | ( x << 8 ) ) & 0x00FF00FF;
278 x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
279 x = ( x | ( x << 2 ) ) & 0x33333333;
280 x = ( x | ( x << 1 ) ) & 0x55555555;
282 y = ( y | ( y << 8 ) ) & 0x00FF00FF;
283 y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
284 y = ( y | ( y << 2 ) ) & 0x33333333;
285 y = ( y | ( y << 1 ) ) & 0x55555555;
287 return x | ( y << 1 );
334 auto len = aPath.size();
337 for(
size_t i = 0; i < len; i++ )
339 auto p1 = aPath.at( i );
340 auto p2 = aPath.at( ( i + 1 ) < len ? i + 1 : 0 );
342 sum += ( ( p2.X - p1.X ) * ( p2.Y + p1.Y ) );
347 for(
auto point : aPath )
352 for(
size_t i = 0; i < len; i++ )
354 auto p = aPath.at( len - i - 1 );
359 if( tail && ( *tail == *tail->
next ) )
377 for(
int i = 0; i < points.
PointCount(); i++ )
382 sum += ( ( p2.
x - p1.
x ) * ( p2.
y + p1.
y ) );
386 for(
int i = points.
PointCount() - 1; i >= 0; i--)
389 for(
int i = 0; i < points.
PointCount(); i++ )
392 if( tail && ( *tail == *tail->
next ) )
422 while( aPoint->
prev != aPoint->
next )
427 if(
isEar( aPoint ) )
441 if( *prev != *nextNext &&
intersects( prev, aPoint,
next, nextNext ) &&
492 return( aPoint->
prev == aPoint->
next );
512 if(
area( a, b, c ) >= 0 )
516 const double minTX = std::min( a->
x, std::min( b->
x, c->
x ) );
517 const double minTY = std::min( a->
y, std::min( b->
y, c->
y ) );
518 const double maxTX = std::max( a->
x, std::max( b->
x, c->
x ) );
519 const double maxTY = std::max( a->
y, std::max( b->
y, c->
y ) );
522 const int32_t minZ =
zOrder( minTX, minTY );
523 const int32_t maxZ =
zOrder( maxTX, maxTY );
528 while( p && p->
z <= maxZ )
541 while( p && p->
z >= minZ )
568 while( marker != origPoly->
prev )
571 if( origPoly->
i != marker->
i &&
goodSplit( origPoly, marker ) )
583 marker = marker->
next;
586 origPoly = origPoly->
next;
587 }
while( origPoly != start );
600 return a->
next->
i != b->
i &&
611 return ( q->
y - p->
y ) * ( r->
x - q->
x ) - ( q->
x - p->
x ) * ( r->
y - q->
y );
621 if( ( *p1 == *q1 && *p2 == *q2 ) || ( *p1 == *q2 && *p2 == *q1 ) )
624 return (
area( p1, q1, p2 ) > 0 ) != (
area( p1, q1, q2 ) > 0 )
625 && (
area( p2, q2, p1 ) > 0 ) != (
area( p2, q2, q1 ) > 0 );
coord_type GetHeight() const
coord_type GetWidth() const
Vertex * createList(const SHAPE_LINE_CHAIN &points)
Take a SHAPE_LINE_CHAIN and links each point into a circular, doubly-linked list.
Vertex * removeNullTriangles(Vertex *aStart)
Iterate through the list to remove NULL triangles if they exist.
int32_t zOrder(const double aX, const double aY) const
Calculate the Morton code of the Vertex http://www.graphics.stanford.edu/~seander/bithacks....
bool goodSplit(const Vertex *a, const Vertex *b) const
Check if a segment joining two vertices lies fully inside the polygon.
std::deque< Vertex > m_vertices
bool isEar(Vertex *aEar) const
Check whether the given vertex is in the middle of an ear.
bool intersects(const Vertex *p1, const Vertex *q1, const Vertex *p2, const Vertex *q2) const
Check for intersection between two segments, end points included.
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 * createList(const ClipperLib::Path &aPath)
Take a Clipper path and converts it into a circular, doubly-linked list for triangulation.
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result
void splitPolygon(Vertex *start)
If we cannot find an ear to slice in the current polygon list, we use this to split the polygon into ...
bool earcutList(Vertex *aPoint, int pass=0)
Walk through a circular linked list starting at aPoint.
bool TesselatePolygon(const SHAPE_LINE_CHAIN &aPoly)
Vertex * insertVertex(const VECTOR2I &pt, Vertex *last)
Create an entry in the vertices lookup and optionally inserts the newly created vertex into an existi...
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.
PolygonTriangulation(SHAPE_POLY_SET::TRIANGULATED_POLYGON &aResult)
bool intersectsPolygon(const Vertex *a, const Vertex *b) const
Check whether the segment from vertex a -> vertex b crosses any of the segments of the polygon of whi...
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.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
void AddVertex(const VECTOR2I &aP)
size_t GetVertexCount() const
void AddTriangle(int a, int b, int c)
void zSort()
Sort all vertices in this vertex's list by their Morton code.
PolygonTriangulation * parent
void updateList()
After inserting or changing nodes, this function should be called to remove duplicate vertices and en...
Vertex(size_t aIndex, double aX, double aY, PolygonTriangulation *aParent)
void remove()
Remove the node from the linked list and z-ordered linked list.
bool operator==(const Vertex &rhs) const
Vertex & operator=(Vertex &&)=delete
bool inTriangle(const Vertex &a, const Vertex &b, const Vertex &c)
Check to see if triangle surrounds our current vertex.
bool operator!=(const Vertex &rhs) const
Vertex & operator=(const Vertex &)=delete
Vertex * split(Vertex *b)
Split the referenced polygon between the reference point and vertex b, assuming they are in the same ...