68 m_bbox = aPoly.
BBox();
71 if( !m_bbox.GetWidth() || !m_bbox.GetHeight() )
77 Vertex* firstVertex = createList( aPoly );
78 if( !firstVertex || firstVertex->prev == firstVertex->next )
81 firstVertex->updateList();
83 auto retval = earcutList( firstVertex );
99 Vertex& operator=(
const Vertex& ) =
delete;
100 Vertex& operator=( Vertex&& ) =
delete;
102 bool operator==(
const Vertex& rhs )
const
104 return this->x == rhs.x && this->y == rhs.y;
106 bool operator!=(
const Vertex& rhs )
const {
return !( *
this == rhs ); }
119 Vertex* split( Vertex* b )
121 parent->m_vertices.emplace_back( i, x, y, parent );
122 Vertex* a2 = &parent->m_vertices.back();
123 parent->m_vertices.emplace_back( b->i, b->x, b->y, parent );
124 Vertex* b2 = &parent->m_vertices.back();
126 Vertex* bp = b->prev;
152 prevZ->nextZ = nextZ;
155 nextZ->prevZ = prevZ;
166 z = parent->zOrder( x, 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 )
216 Vertex* prev_elem =
nullptr;
218 for(
auto elem : queue )
221 prev_elem->nextZ = elem;
223 elem->prevZ = prev_elem;
227 prev_elem->nextZ =
nullptr;
234 bool inTriangle(
const Vertex& a,
const Vertex& b,
const Vertex& c )
236 return ( c.x - x ) * ( a.y - y ) - ( a.x - x ) * ( c.y - y ) >= 0
237 && ( a.x - x ) * ( b.y - y ) - ( b.x - x ) * ( a.y - y ) >= 0
238 && ( b.x - x ) * ( c.y - y ) - ( c.x - x ) * ( b.y - y ) >= 0;
247 Vertex* prev =
nullptr;
248 Vertex* next =
nullptr;
254 Vertex* prevZ =
nullptr;
255 Vertex* nextZ =
nullptr;
263 int32_t zOrder(
const double aX,
const double aY )
const
265 int32_t x =
static_cast<int32_t
>( 32767.0 * ( aX - m_bbox.GetX() ) / m_bbox.GetWidth() );
266 int32_t y =
static_cast<int32_t
>( 32767.0 * ( aY - m_bbox.GetY() ) / m_bbox.GetHeight() );
268 x = ( x | ( x << 8 ) ) & 0x00FF00FF;
269 x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
270 x = ( x | ( x << 2 ) ) & 0x33333333;
271 x = ( x | ( x << 1 ) ) & 0x55555555;
273 y = ( y | ( y << 8 ) ) & 0x00FF00FF;
274 y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
275 y = ( y | ( y << 2 ) ) & 0x33333333;
276 y = ( y | ( y << 1 ) ) & 0x55555555;
278 return x | ( y << 1 );
288 Vertex* removeNullTriangles( Vertex* aStart )
290 Vertex* retval =
nullptr;
291 Vertex* p = aStart->next;
295 if( area( p->prev, p, p->next ) == 0.0 )
309 if( area( aStart->prev, aStart, aStart->next ) == 0.0 )
321 Vertex* createList(
const ClipperLibKiCad::Path& aPath )
323 Vertex* tail =
nullptr;
325 auto len = aPath.size();
328 for(
size_t i = 0; i < len; i++ )
330 auto p1 = aPath.at( i );
331 auto p2 = aPath.at( ( i + 1 ) < len ? i + 1 : 0 );
333 sum += ( ( p2.X - p1.X ) * ( p2.Y + p1.Y ) );
338 for(
auto point : aPath )
339 tail = insertVertex(
VECTOR2I( point.X, point.Y ), tail );
343 for(
size_t i = 0; i < len; i++ )
345 auto p = aPath.at( len - i - 1 );
346 tail = insertVertex(
VECTOR2I( p.X, p.Y ), tail );
350 if( tail && ( *tail == *tail->next ) )
352 tail->next->remove();
364 Vertex* tail =
nullptr;
368 for(
int i = 0; i < points.
PointCount(); i++ )
373 sum += ( ( p2.x - p1.x ) * ( p2.y + p1.y ) );
377 for(
int i = points.
PointCount() - 1; i >= 0; i--)
378 tail = insertVertex( points.
CPoint( i ), tail );
380 for(
int i = 0; i < points.
PointCount(); i++ )
381 tail = insertVertex( points.
CPoint( i ), tail );
383 if( tail && ( *tail == *tail->next ) )
385 tail->next->remove();
404 bool earcutList( Vertex* aPoint,
int pass = 0 )
409 Vertex* stop = aPoint;
413 while( aPoint->prev != aPoint->next )
418 if( isEar( aPoint ) )
420 m_result.AddTriangle( prev->i, aPoint->i, next->i );
430 Vertex* nextNext = next->next;
432 if( *prev != *nextNext && intersects( prev, aPoint, next, nextNext ) &&
433 locallyInside( prev, nextNext ) &&
434 locallyInside( nextNext, prev ) )
436 m_result.AddTriangle( prev->i, aPoint->i, nextNext->i );
458 if(
auto newPoint = removeNullTriangles( aPoint ) )
466 splitPolygon( aPoint );
472 if( aPoint->next && aPoint->prev == aPoint->next->next )
476 if( area( aPoint->prev, aPoint, aPoint->next ) >= 0 )
483 return( aPoint->prev == aPoint->next );
495 bool isEar( Vertex* aEar )
const
497 const Vertex* a = aEar->prev;
498 const Vertex* b = aEar;
499 const Vertex* c = aEar->next;
503 if( area( a, b, c ) >= 0 )
507 const double minTX = std::min( a->x, std::min( b->x, c->x ) );
508 const double minTY = std::min( a->y, std::min( b->y, c->y ) );
509 const double maxTX = std::max( a->x, std::max( b->x, c->x ) );
510 const double maxTY = std::max( a->y, std::max( b->y, c->y ) );
513 const int32_t minZ = zOrder( minTX, minTY );
514 const int32_t maxZ = zOrder( maxTX, maxTY );
517 Vertex* p = aEar->nextZ;
519 while( p && p->z <= maxZ )
522 && p->inTriangle( *a, *b, *c )
523 && area( p->prev, p, p->next ) >= 0 )
532 while( p && p->z >= minZ )
535 && p->inTriangle( *a, *b, *c )
536 && area( p->prev, p, p->next ) >= 0 )
551 void splitPolygon( Vertex* start )
553 Vertex* origPoly = start;
557 Vertex* marker = origPoly->next->next;
559 while( marker != origPoly->prev )
562 if( origPoly->i != marker->i && goodSplit( origPoly, marker ) )
564 Vertex* newPoly = origPoly->split( marker );
566 origPoly->updateList();
567 newPoly->updateList();
569 earcutList( origPoly );
570 earcutList( newPoly );
574 marker = marker->next;
577 origPoly = origPoly->next;
578 }
while( origPoly != start );
589 bool goodSplit(
const Vertex* a,
const Vertex* b )
const
591 return a->next->i != b->i &&
592 a->prev->i != b->i &&
593 !intersectsPolygon( a, b ) &&
594 locallyInside( a, b );
600 double area(
const Vertex* p,
const Vertex* q,
const Vertex* r )
const
602 return ( q->y - p->y ) * ( r->x - q->x ) - ( q->x - p->x ) * ( r->y - q->y );
610 bool intersects(
const Vertex* p1,
const Vertex* q1,
const Vertex* p2,
const Vertex* q2 )
const
612 if( ( *p1 == *q1 && *p2 == *q2 ) || ( *p1 == *q2 && *p2 == *q1 ) )
615 return ( area( p1, q1, p2 ) > 0 ) != ( area( p1, q1, q2 ) > 0 )
616 && ( area( p2, q2, p1 ) > 0 ) != ( area( p2, q2, q1 ) > 0 );
625 bool intersectsPolygon(
const Vertex* a,
const Vertex* b )
const
627 const Vertex* p = a->next;
632 p->next->i != a->i &&
634 p->next->i != b->i && intersects( p, p->next, a, b ) )
652 bool locallyInside(
const Vertex* a,
const Vertex* b )
const
654 if( area( a->prev, a, a->next ) < 0 )
655 return area( a, b, a->next ) >= 0 && area( a, a->prev, b ) >= 0;
657 return area( a, b, a->prev ) < 0 || area( a, a->next, b ) < 0;
666 Vertex* insertVertex(
const VECTOR2I& pt, Vertex* last )
668 m_result.AddVertex( pt );
669 m_vertices.emplace_back( m_result.GetVertexCount() - 1, pt.x, pt.y,
this );
671 Vertex* p = &m_vertices.back();
680 p->next = last->next;
682 last->next->prev = p;
690 std::deque<Vertex> m_vertices;