KiCad PCB EDA Suite
PolygonTriangulation Class Reference

#include <polygon_triangulation.h>

Classes

struct  Vertex
 

Public Member Functions

 PolygonTriangulation (SHAPE_POLY_SET::TRIANGULATED_POLYGON &aResult)
 
bool TesselatePolygon (const SHAPE_LINE_CHAIN &aPoly)
 

Private Member Functions

int32_t zOrder (const double aX, const double aY) const
 Calculate the Morton code of the Vertex http://www.graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN. More...
 
VertexremoveNullTriangles (Vertex *aStart)
 Iterate through the list to remove NULL triangles if they exist. More...
 
VertexcreateList (const ClipperLib::Path &aPath)
 Take a Clipper path and converts it into a circular, doubly-linked list for triangulation. More...
 
VertexcreateList (const SHAPE_LINE_CHAIN &points)
 Take a SHAPE_LINE_CHAIN and links each point into a circular, doubly-linked list. More...
 
bool earcutList (Vertex *aPoint, int pass=0)
 Walk through a circular linked list starting at aPoint. More...
 
bool isEar (Vertex *aEar) const
 Check whether the given vertex is in the middle of an ear. More...
 
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 two separate lists and slice them each independently. More...
 
bool goodSplit (const Vertex *a, const Vertex *b) const
 Check if a segment joining two vertices lies fully inside the polygon. More...
 
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. More...
 
bool intersects (const Vertex *p1, const Vertex *q1, const Vertex *p2, const Vertex *q2) const
 Check for intersection between two segments, end points included. More...
 
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 which vertex a is a member. More...
 
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 of vertex a. More...
 
VertexinsertVertex (const VECTOR2I &pt, Vertex *last)
 Create an entry in the vertices lookup and optionally inserts the newly created vertex into an existing linked list. More...
 

Private Attributes

BOX2I m_bbox
 
std::deque< Vertexm_vertices
 
SHAPE_POLY_SET::TRIANGULATED_POLYGONm_result
 

Detailed Description

Definition at line 59 of file polygon_triangulation.h.

Constructor & Destructor Documentation

◆ PolygonTriangulation()

PolygonTriangulation::PolygonTriangulation ( SHAPE_POLY_SET::TRIANGULATED_POLYGON aResult)
inline

Definition at line 62 of file polygon_triangulation.h.

62 :
63 m_result( aResult )
64 {};
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result

Member Function Documentation

◆ area()

double PolygonTriangulation::area ( const Vertex p,
const Vertex q,
const Vertex r 
) const
inlineprivate

Return the twice the signed area of the triangle formed by vertices p, q, and r.

Definition at line 600 of file polygon_triangulation.h.

601 {
602 return ( q->y - p->y ) * ( r->x - q->x ) - ( q->x - p->x ) * ( r->y - q->y );
603 }
E_SERIE r
Definition: eserie.cpp:41

References r, PolygonTriangulation::Vertex::x, and PolygonTriangulation::Vertex::y.

Referenced by earcutList(), intersects(), isEar(), locallyInside(), and removeNullTriangles().

◆ createList() [1/2]

Vertex * PolygonTriangulation::createList ( const ClipperLib::Path &  aPath)
inlineprivate

Take a Clipper path and converts it into a circular, doubly-linked list for triangulation.

Definition at line 321 of file polygon_triangulation.h.

322 {
323 Vertex* tail = nullptr;
324 double sum = 0.0;
325 auto len = aPath.size();
326
327 // Check for winding order
328 for( size_t i = 0; i < len; i++ )
329 {
330 auto p1 = aPath.at( i );
331 auto p2 = aPath.at( ( i + 1 ) < len ? i + 1 : 0 );
332
333 sum += ( ( p2.X - p1.X ) * ( p2.Y + p1.Y ) );
334 }
335
336 if( sum <= 0.0 )
337 {
338 for( auto point : aPath )
339 tail = insertVertex( VECTOR2I( point.X, point.Y ), tail );
340 }
341 else
342 {
343 for( size_t i = 0; i < len; i++ )
344 {
345 auto p = aPath.at( len - i - 1 );
346 tail = insertVertex( VECTOR2I( p.X, p.Y ), tail );
347 }
348 }
349
350 if( tail && ( *tail == *tail->next ) )
351 {
352 tail->next->remove();
353 }
354
355 return tail;
356
357 }
Vertex * insertVertex(const VECTOR2I &pt, Vertex *last)
Create an entry in the vertices lookup and optionally inserts the newly created vertex into an existi...
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618

References insertVertex(), PolygonTriangulation::Vertex::next, and PolygonTriangulation::Vertex::remove().

Referenced by TesselatePolygon().

◆ createList() [2/2]

Vertex * PolygonTriangulation::createList ( const SHAPE_LINE_CHAIN points)
inlineprivate

Take a SHAPE_LINE_CHAIN and links each point into a circular, doubly-linked list.

Definition at line 362 of file polygon_triangulation.h.

363 {
364 Vertex* tail = nullptr;
365 double sum = 0.0;
366
367 // Check for winding order
368 for( int i = 0; i < points.PointCount(); i++ )
369 {
370 VECTOR2D p1 = points.CPoint( i );
371 VECTOR2D p2 = points.CPoint( i + 1 );
372
373 sum += ( ( p2.x - p1.x ) * ( p2.y + p1.y ) );
374 }
375
376 if( sum > 0.0 )
377 for( int i = points.PointCount() - 1; i >= 0; i--)
378 tail = insertVertex( points.CPoint( i ), tail );
379 else
380 for( int i = 0; i < points.PointCount(); i++ )
381 tail = insertVertex( points.CPoint( i ), tail );
382
383 if( tail && ( *tail == *tail->next ) )
384 {
385 tail->next->remove();
386 }
387
388 return tail;
389 }
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.
void remove()
Remove the node from the linked list and z-ordered linked list.

References SHAPE_LINE_CHAIN::CPoint(), insertVertex(), PolygonTriangulation::Vertex::next, SHAPE_LINE_CHAIN::PointCount(), PolygonTriangulation::Vertex::remove(), VECTOR2< T >::x, and VECTOR2< T >::y.

◆ earcutList()

bool PolygonTriangulation::earcutList ( Vertex aPoint,
int  pass = 0 
)
inlineprivate

Walk through a circular linked list starting at aPoint.

For each point, test to see if the adjacent points form a triangle that is completely enclosed by the remaining polygon (an "ear" sticking off the polygon). If the three points form an ear, we log the ear's location and remove the center point from the linked list.

This function can be called recursively in the case of difficult polygons. In cases where there is an intersection (not technically allowed by KiCad, but could exist in an edited file), we create a single triangle and remove both vertices before attempting to.

Definition at line 404 of file polygon_triangulation.h.

405 {
406 if( !aPoint )
407 return true;
408
409 Vertex* stop = aPoint;
410 Vertex* prev;
411 Vertex* next;
412
413 while( aPoint->prev != aPoint->next )
414 {
415 prev = aPoint->prev;
416 next = aPoint->next;
417
418 if( isEar( aPoint ) )
419 {
420 m_result.AddTriangle( prev->i, aPoint->i, next->i );
421 aPoint->remove();
422
423 // Skip one vertex as the triangle will account for the prev node
424 aPoint = next->next;
425 stop = next->next;
426
427 continue;
428 }
429
430 Vertex* nextNext = next->next;
431
432 if( *prev != *nextNext && intersects( prev, aPoint, next, nextNext ) &&
433 locallyInside( prev, nextNext ) &&
434 locallyInside( nextNext, prev ) )
435 {
436 m_result.AddTriangle( prev->i, aPoint->i, nextNext->i );
437
438 // remove two nodes involved
439 next->remove();
440 aPoint->remove();
441
442 aPoint = nextNext;
443 stop = nextNext;
444
445 continue;
446 }
447
448 aPoint = next;
449
450 /*
451 * We've searched the entire polygon for available ears and there are still
452 * un-sliced nodes remaining.
453 */
454 if( aPoint == stop )
455 {
456 // First, try to remove the remaining steiner points
457 // If aPoint is a steiner, we need to re-assign both the start and stop points
458 if( auto newPoint = removeNullTriangles( aPoint ) )
459 {
460 aPoint = newPoint;
461 stop = newPoint;
462 continue;
463 }
464
465 // If we don't have any NULL triangles left, cut the polygon in two and try again
466 splitPolygon( aPoint );
467 break;
468 }
469 }
470
471 // Check to see if we are left with only three points in the polygon
472 if( aPoint->next && aPoint->prev == aPoint->next->next )
473 {
474 // Three concave points will never be able to be triangulated because they were
475 // created by an intersecting polygon, so just drop them.
476 if( area( aPoint->prev, aPoint, aPoint->next ) >= 0 )
477 return true;
478 }
479
480 /*
481 * At this point, our polygon should be fully tessellated.
482 */
483 return( aPoint->prev == aPoint->next );
484 }
Vertex * removeNullTriangles(Vertex *aStart)
Iterate through the list to remove NULL triangles if they exist.
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...
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 ...
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.
void AddTriangle(int a, int b, int c)
CITER next(CITER it)
Definition: ptree.cpp:126

References SHAPE_POLY_SET::TRIANGULATED_POLYGON::AddTriangle(), area(), PolygonTriangulation::Vertex::i, intersects(), isEar(), locallyInside(), m_result, next(), PolygonTriangulation::Vertex::next, PolygonTriangulation::Vertex::prev, PolygonTriangulation::Vertex::remove(), removeNullTriangles(), and splitPolygon().

Referenced by splitPolygon(), and TesselatePolygon().

◆ goodSplit()

bool PolygonTriangulation::goodSplit ( const Vertex a,
const Vertex b 
) const
inlineprivate

Check if a segment joining two vertices lies fully inside the polygon.

To do this, we first ensure that the line isn't along the polygon edge. Next, we know that if the line doesn't intersect the polygon, then it is either fully inside or fully outside the polygon. Finally, by checking whether the segment is enclosed by the local triangles, we distinguish between these two cases and no further checks are needed.

Definition at line 589 of file polygon_triangulation.h.

590 {
591 return a->next->i != b->i &&
592 a->prev->i != b->i &&
593 !intersectsPolygon( a, b ) &&
594 locallyInside( a, b );
595 }
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...

References PolygonTriangulation::Vertex::i, intersectsPolygon(), locallyInside(), PolygonTriangulation::Vertex::next, and PolygonTriangulation::Vertex::prev.

Referenced by splitPolygon().

◆ insertVertex()

Vertex * PolygonTriangulation::insertVertex ( const VECTOR2I pt,
Vertex last 
)
inlineprivate

Create an entry in the vertices lookup and optionally inserts the newly created vertex into an existing linked list.

Returns
a pointer to the newly created vertex.

Definition at line 666 of file polygon_triangulation.h.

667 {
668 m_result.AddVertex( pt );
669 m_vertices.emplace_back( m_result.GetVertexCount() - 1, pt.x, pt.y, this );
670
671 Vertex* p = &m_vertices.back();
672
673 if( !last )
674 {
675 p->prev = p;
676 p->next = p;
677 }
678 else
679 {
680 p->next = last->next;
681 p->prev = last;
682 last->next->prev = p;
683 last->next = p;
684 }
685 return p;
686 }
std::deque< Vertex > m_vertices
void AddVertex(const VECTOR2I &aP)

References SHAPE_POLY_SET::TRIANGULATED_POLYGON::AddVertex(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetVertexCount(), m_result, m_vertices, PolygonTriangulation::Vertex::next, PolygonTriangulation::Vertex::prev, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by createList().

◆ intersects()

bool PolygonTriangulation::intersects ( const Vertex p1,
const Vertex q1,
const Vertex p2,
const Vertex q2 
) const
inlineprivate

Check for intersection between two segments, end points included.

Returns
true if p1-p2 intersects q1-q2.

Definition at line 610 of file polygon_triangulation.h.

611 {
612 if( ( *p1 == *q1 && *p2 == *q2 ) || ( *p1 == *q2 && *p2 == *q1 ) )
613 return true;
614
615 return ( area( p1, q1, p2 ) > 0 ) != ( area( p1, q1, q2 ) > 0 )
616 && ( area( p2, q2, p1 ) > 0 ) != ( area( p2, q2, q1 ) > 0 );
617 }

References area().

Referenced by earcutList(), and intersectsPolygon().

◆ intersectsPolygon()

bool PolygonTriangulation::intersectsPolygon ( const Vertex a,
const Vertex b 
) const
inlineprivate

Check whether the segment from vertex a -> vertex b crosses any of the segments of the polygon of which vertex a is a member.

Returns
true if the segment intersects the edge of the polygon.

Definition at line 625 of file polygon_triangulation.h.

626 {
627 const Vertex* p = a->next;
628
629 do
630 {
631 if( p->i != a->i &&
632 p->next->i != a->i &&
633 p->i != b->i &&
634 p->next->i != b->i && intersects( p, p->next, a, b ) )
635 return true;
636
637 p = p->next;
638 } while( p != a );
639
640 return false;
641 }

References PolygonTriangulation::Vertex::i, intersects(), and PolygonTriangulation::Vertex::next.

Referenced by goodSplit().

◆ isEar()

bool PolygonTriangulation::isEar ( Vertex aEar) const
inlineprivate

Check whether the given vertex is in the middle of an ear.

This works by walking forward and backward in zOrder to the limits of the minimal bounding box formed around the triangle, checking whether any points are located inside the given triangle.

Returns
true if aEar is the apex point of a ear in the polygon.

Definition at line 495 of file polygon_triangulation.h.

496 {
497 const Vertex* a = aEar->prev;
498 const Vertex* b = aEar;
499 const Vertex* c = aEar->next;
500
501 // If the area >=0, then the three points for a concave sequence
502 // with b as the reflex point
503 if( area( a, b, c ) >= 0 )
504 return false;
505
506 // triangle bbox
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 ) );
511
512 // z-order range for the current triangle bounding box
513 const int32_t minZ = zOrder( minTX, minTY );
514 const int32_t maxZ = zOrder( maxTX, maxTY );
515
516 // first look for points inside the triangle in increasing z-order
517 Vertex* p = aEar->nextZ;
518
519 while( p && p->z <= maxZ )
520 {
521 if( p != a && p != c
522 && p->inTriangle( *a, *b, *c )
523 && area( p->prev, p, p->next ) >= 0 )
524 return false;
525
526 p = p->nextZ;
527 }
528
529 // then look for points in decreasing z-order
530 p = aEar->prevZ;
531
532 while( p && p->z >= minZ )
533 {
534 if( p != a && p != c
535 && p->inTriangle( *a, *b, *c )
536 && area( p->prev, p, p->next ) >= 0 )
537 return false;
538
539 p = p->prevZ;
540 }
541
542 return true;
543 }
int32_t zOrder(const double aX, const double aY) const
Calculate the Morton code of the Vertex http://www.graphics.stanford.edu/~seander/bithacks....

References area(), PolygonTriangulation::Vertex::inTriangle(), PolygonTriangulation::Vertex::next, PolygonTriangulation::Vertex::nextZ, PolygonTriangulation::Vertex::prev, PolygonTriangulation::Vertex::prevZ, PolygonTriangulation::Vertex::x, PolygonTriangulation::Vertex::y, PolygonTriangulation::Vertex::z, and zOrder().

Referenced by earcutList().

◆ locallyInside()

bool PolygonTriangulation::locallyInside ( const Vertex a,
const Vertex b 
) const
inlineprivate

Check whether the segment from vertex a -> vertex b is inside the polygon around the immediate area of vertex a.

We don't define the exact area over which the segment is inside but it is guaranteed to be inside the polygon immediately adjacent to vertex a.

Returns
true if the segment from a->b is inside a's polygon next to vertex a.

Definition at line 652 of file polygon_triangulation.h.

653 {
654 if( area( a->prev, a, a->next ) < 0 )
655 return area( a, b, a->next ) >= 0 && area( a, a->prev, b ) >= 0;
656 else
657 return area( a, b, a->prev ) < 0 || area( a, a->next, b ) < 0;
658 }

References area(), PolygonTriangulation::Vertex::next, and PolygonTriangulation::Vertex::prev.

Referenced by earcutList(), and goodSplit().

◆ removeNullTriangles()

Vertex * PolygonTriangulation::removeNullTriangles ( Vertex aStart)
inlineprivate

Iterate through the list to remove NULL triangles if they exist.

This should only be called as a last resort when tesselation fails as the NULL triangles are inserted as Steiner points to improve the triangulation regularity of polygons

Definition at line 288 of file polygon_triangulation.h.

289 {
290 Vertex* retval = nullptr;
291 Vertex* p = aStart->next;
292
293 while( p != aStart )
294 {
295 if( area( p->prev, p, p->next ) == 0.0 )
296 {
297 p = p->prev;
298 p->next->remove();
299 retval = aStart;
300
301 if( p == p->next )
302 break;
303 }
304 p = p->next;
305 };
306
307 // We needed an end point above that wouldn't be removed, so
308 // here we do the final check for this as a Steiner point
309 if( area( aStart->prev, aStart, aStart->next ) == 0.0 )
310 {
311 retval = p->next;
312 p->remove();
313 }
314
315 return retval;
316 }

References area(), PolygonTriangulation::Vertex::next, PolygonTriangulation::Vertex::prev, and PolygonTriangulation::Vertex::remove().

Referenced by earcutList().

◆ splitPolygon()

void PolygonTriangulation::splitPolygon ( Vertex start)
inlineprivate

If we cannot find an ear to slice in the current polygon list, we use this to split the polygon into two separate lists and slice them each independently.

This is assured to generate at least one new ear if the split is successful

Definition at line 551 of file polygon_triangulation.h.

552 {
553 Vertex* origPoly = start;
554
555 do
556 {
557 Vertex* marker = origPoly->next->next;
558
559 while( marker != origPoly->prev )
560 {
561 // Find a diagonal line that is wholly enclosed by the polygon interior
562 if( origPoly->i != marker->i && goodSplit( origPoly, marker ) )
563 {
564 Vertex* newPoly = origPoly->split( marker );
565
566 origPoly->updateList();
567 newPoly->updateList();
568
569 earcutList( origPoly );
570 earcutList( newPoly );
571 return;
572 }
573
574 marker = marker->next;
575 }
576
577 origPoly = origPoly->next;
578 } while( origPoly != start );
579 }
bool goodSplit(const Vertex *a, const Vertex *b) const
Check if a segment joining two vertices lies fully inside the polygon.
bool earcutList(Vertex *aPoint, int pass=0)
Walk through a circular linked list starting at aPoint.

References earcutList(), goodSplit(), PolygonTriangulation::Vertex::i, PolygonTriangulation::Vertex::next, PolygonTriangulation::Vertex::prev, PolygonTriangulation::Vertex::split(), and PolygonTriangulation::Vertex::updateList().

Referenced by earcutList().

◆ TesselatePolygon()

bool PolygonTriangulation::TesselatePolygon ( const SHAPE_LINE_CHAIN aPoly)
inline

Place the polygon Vertices into a circular linked list and check for lists that have only 0, 1 or 2 elements and therefore cannot be polygons

Definition at line 66 of file polygon_triangulation.h.

67 {
68 m_bbox = aPoly.BBox();
70
71 if( !m_bbox.GetWidth() || !m_bbox.GetHeight() )
72 return false;
73
77 Vertex* firstVertex = createList( aPoly );
78 if( !firstVertex || firstVertex->prev == firstVertex->next )
79 return false;
80
81 firstVertex->updateList();
82
83 auto retval = earcutList( firstVertex );
84 m_vertices.clear();
85 return retval;
86 }
coord_type GetHeight() const
Definition: box2.h:188
coord_type GetWidth() const
Definition: box2.h:187
Vertex * createList(const ClipperLib::Path &aPath)
Take a Clipper path and converts it into a circular, doubly-linked list for triangulation.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.

References SHAPE_LINE_CHAIN::BBox(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::Clear(), createList(), earcutList(), BOX2< Vec >::GetHeight(), BOX2< Vec >::GetWidth(), m_bbox, m_result, m_vertices, PolygonTriangulation::Vertex::next, PolygonTriangulation::Vertex::prev, and PolygonTriangulation::Vertex::updateList().

Referenced by SHAPE_POLY_SET::CacheTriangulation().

◆ zOrder()

int32_t PolygonTriangulation::zOrder ( const double  aX,
const double  aY 
) const
inlineprivate

Calculate the Morton code of the Vertex http://www.graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN.

Definition at line 263 of file polygon_triangulation.h.

264 {
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() );
267
268 x = ( x | ( x << 8 ) ) & 0x00FF00FF;
269 x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
270 x = ( x | ( x << 2 ) ) & 0x33333333;
271 x = ( x | ( x << 1 ) ) & 0x55555555;
272
273 y = ( y | ( y << 8 ) ) & 0x00FF00FF;
274 y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
275 y = ( y | ( y << 2 ) ) & 0x33333333;
276 y = ( y | ( y << 1 ) ) & 0x55555555;
277
278 return x | ( y << 1 );
279 }
coord_type GetY() const
Definition: box2.h:181
coord_type GetX() const
Definition: box2.h:180

References BOX2< Vec >::GetHeight(), BOX2< Vec >::GetWidth(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), and m_bbox.

Referenced by isEar(), and PolygonTriangulation::Vertex::updateOrder().

Member Data Documentation

◆ m_bbox

BOX2I PolygonTriangulation::m_bbox
private

Definition at line 689 of file polygon_triangulation.h.

Referenced by TesselatePolygon(), and zOrder().

◆ m_result

SHAPE_POLY_SET::TRIANGULATED_POLYGON& PolygonTriangulation::m_result
private

Definition at line 691 of file polygon_triangulation.h.

Referenced by earcutList(), insertVertex(), and TesselatePolygon().

◆ m_vertices

std::deque<Vertex> PolygonTriangulation::m_vertices
private

The documentation for this class was generated from the following file: