 KiCad PCB EDA Suite
PolygonTriangulation Class Reference

`#include <polygon_triangulation.h>`

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)
Function removeNullTriangles Iterates through the list to remove NULL triangles if they exist. More...

VertexcreateList (const ClipperLib::Path &aPath)
Function createList Takes a Clipper path and converts it into a circular, doubly-linked list for triangulation. More...

VertexcreateList (const SHAPE_LINE_CHAIN &points)
Function createList Takes the SHAPE_LINE_CHAIN and links each point into a circular, doubly-linked list. More...

bool earcutList (Vertex *aPoint, int pass=0)
Function: earcutList Walks through a circular linked list starting at aPoint. More...

bool isEar (Vertex *aEar) const
Function isEar Checks whether the given vertex is in the middle of an ear. More...

void splitPolygon (Vertex *start)
Function splitPolygon 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
Function area Returns the twice the signed area of the triangle formed by vertices p, q, r. More...

bool intersects (const Vertex *p1, const Vertex *q1, const Vertex *p2, const Vertex *q2) const
Function intersects Checks for intersection between two segments, end points included. More...

bool intersectsPolygon (const Vertex *a, const Vertex *b) const
Function intersectsPolygon Checks 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
Function locallyInside Checks 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)
Function insertVertex Creates 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.

## ◆ PolygonTriangulation()

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

Definition at line 64 of file polygon_triangulation.h.

64  :
65  m_result( aResult )
66  {};
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result

## ◆ area()

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

Function area Returns the twice the signed area of the triangle formed by vertices p, q, r.

Definition at line 571 of file polygon_triangulation.h.

572  {
573  return ( q->y - p->y ) * ( r->x - q->x ) - ( q->x - p->x ) * ( r->y - q->y );
574  }

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

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

## ◆ createList() [1/2]

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

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

Definition at line 304 of file polygon_triangulation.h.

305  {
306  Vertex* tail = nullptr;
307  double sum = 0.0;
308  auto len = aPath.size();
309
310  // Check for winding order
311  for( size_t i = 0; i < len; i++ )
312  {
313  auto p1 = aPath.at( i );
314  auto p2 = aPath.at( ( i + 1 ) < len ? i + 1 : 0 );
315
316  sum += ( ( p2.X - p1.X ) * ( p2.Y + p1.Y ) );
317  }
318
319  if( sum <= 0.0 )
320  {
321  for( auto point : aPath )
322  tail = insertVertex( VECTOR2I( point.X, point.Y ), tail );
323  }
324  else
325  {
326  for( size_t i = 0; i < len; i++ )
327  {
328  auto p = aPath.at( len - i - 1 );
329  tail = insertVertex( VECTOR2I( p.X, p.Y ), tail );
330  }
331  }
332
333  if( tail && ( *tail == *tail->next ) )
334  {
335  tail->next->remove();
336  }
337
338  return tail;
339
340  }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
Vertex * insertVertex(const VECTOR2I &pt, Vertex *last)
Function insertVertex Creates an entry in the vertices lookup and optionally inserts the newly create...

Referenced by TesselatePolygon().

## ◆ createList() [2/2]

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

Function createList Takes the SHAPE_LINE_CHAIN and links each point into a circular, doubly-linked list.

Definition at line 347 of file polygon_triangulation.h.

348  {
349  Vertex* tail = nullptr;
350  double sum = 0.0;
351
352  // Check for winding order
353  for( int i = 0; i < points.PointCount(); i++ )
354  {
355  VECTOR2D p1 = points.CPoint( i );
356  VECTOR2D p2 = points.CPoint( i + 1 );
357
358  sum += ( ( p2.x - p1.x ) * ( p2.y + p1.y ) );
359  }
360
361  if( sum > 0.0 )
362  for( int i = points.PointCount() - 1; i >= 0; i--)
363  tail = insertVertex( points.CPoint( i ), tail );
364  else
365  for( int i = 0; i < points.PointCount(); i++ )
366  tail = insertVertex( points.CPoint( i ), tail );
367
368  if( tail && ( *tail == *tail->next ) )
369  {
370  tail->next->remove();
371  }
372
373  return tail;
374  }
void remove()
Function remove Removes the node from the linked list and z-ordered linked list.
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
Vertex * insertVertex(const VECTOR2I &pt, Vertex *last)
Function insertVertex Creates an entry in the vertices lookup and optionally inserts the newly create...

## ◆ earcutList()

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

Function: earcutList Walks 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

We've searched the entire polygon for available ears and there are still un-sliced nodes remaining

At this point, our polygon should be fully tesselated.

Definition at line 387 of file polygon_triangulation.h.

388  {
389  if( !aPoint )
390  return true;
391
392  Vertex* stop = aPoint;
393  Vertex* prev;
394  Vertex* next;
395
396  while( aPoint->prev != aPoint->next )
397  {
398  prev = aPoint->prev;
399  next = aPoint->next;
400
401  if( isEar( aPoint ) )
402  {
403  m_result.AddTriangle( prev->i, aPoint->i, next->i );
404  aPoint->remove();
405
406  // Skip one vertex as the triangle will account for the prev node
407  aPoint = next->next;
408  stop = next->next;
409
410  continue;
411  }
412
413  Vertex* nextNext = next->next;
414
415  if( *prev != *nextNext && intersects( prev, aPoint, next, nextNext ) &&
416  locallyInside( prev, nextNext ) &&
417  locallyInside( nextNext, prev ) )
418  {
419  m_result.AddTriangle( prev->i, aPoint->i, nextNext->i );
420
421  // remove two nodes involved
422  next->remove();
423  aPoint->remove();
424
425  aPoint = nextNext;
426  stop = nextNext;
427
428  continue;
429  }
430
431  aPoint = next;
432
437  if( aPoint == stop )
438  {
439  // First, try to remove the remaining steiner points
440  // If aPoint is a steiner, we need to re-assign both the start and stop points
441  if( auto newPoint = removeNullTriangles( aPoint ) )
442  {
443  aPoint = newPoint;
444  stop = newPoint;
445  continue;
446  }
447
448  // If we don't have any NULL triangles left, cut the polygon in two and try again
449  splitPolygon( aPoint );
450  break;
451  }
452  }
453
457  return( aPoint->prev == aPoint->next );
458  }
CITER next(CITER it)
Definition: ptree.cpp:130
bool intersects(const Vertex *p1, const Vertex *q1, const Vertex *p2, const Vertex *q2) const
Function intersects Checks for intersection between two segments, end points included.
Vertex * removeNullTriangles(Vertex *aStart)
Function removeNullTriangles Iterates through the list to remove NULL triangles if they exist.
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result
bool locallyInside(const Vertex *a, const Vertex *b) const
Function locallyInside Checks whether the segment from vertex a -> vertex b is inside the polygon aro...
bool isEar(Vertex *aEar) const
Function isEar Checks whether the given vertex is in the middle of an ear.
void splitPolygon(Vertex *start)
Function splitPolygon If we cannot find an ear to slice in the current polygon list,...

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 558 of file polygon_triangulation.h.

559  {
560  return a->next->i != b->i &&
561  a->prev->i != b->i &&
562  !intersectsPolygon( a, b ) &&
563  locallyInside( a, b );
564  }
bool intersectsPolygon(const Vertex *a, const Vertex *b) const
Function intersectsPolygon Checks whether the segment from vertex a -> vertex b crosses any of the se...
bool locallyInside(const Vertex *a, const Vertex *b) const
Function locallyInside Checks whether the segment from vertex a -> vertex b is inside the polygon aro...

Referenced by splitPolygon().

## ◆ insertVertex()

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

Function insertVertex Creates 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 635 of file polygon_triangulation.h.

636  {
638  m_vertices.emplace_back( m_result.GetVertexCount() - 1, pt.x, pt.y, this );
639
640  Vertex* p = &m_vertices.back();
641  if( !last )
642  {
643  p->prev = p;
644  p->next = p;
645  }
646  else
647  {
648  p->next = last->next;
649  p->prev = last;
650  last->next->prev = p;
651  last->next = p;
652  }
653  return p;
654  }
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result
std::deque< Vertex > m_vertices

Referenced by createList().

## ◆ intersects()

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

Function intersects Checks for intersection between two segments, end points included.

Returns true if p1-p2 intersects q1-q2

Definition at line 581 of file polygon_triangulation.h.

582  {
583  if( ( *p1 == *q1 && *p2 == *q2 ) || ( *p1 == *q2 && *p2 == *q1 ) )
584  return true;
585
586  return ( area( p1, q1, p2 ) > 0 ) != ( area( p1, q1, q2 ) > 0 )
587  && ( area( p2, q2, p1 ) > 0 ) != ( area( p2, q2, q1 ) > 0 );
588  }
double area(const Vertex *p, const Vertex *q, const Vertex *r) const
Function area Returns the twice the signed area of the triangle formed by vertices p,...

References area().

Referenced by earcutList(), and intersectsPolygon().

## ◆ intersectsPolygon()

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

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

Return true if the segment intersects the edge of the polygon

Definition at line 596 of file polygon_triangulation.h.

597  {
598  const Vertex* p = a->next;
599  do
600  {
601  if( p->i != a->i &&
602  p->next->i != a->i &&
603  p->i != b->i &&
604  p->next->i != b->i && intersects( p, p->next, a, b ) )
605  return true;
606
607  p = p->next;
608  } while( p != a );
609
610  return false;
611  }
bool intersects(const Vertex *p1, const Vertex *q1, const Vertex *p2, const Vertex *q2) const
Function intersects Checks for intersection between two segments, end points included.

Referenced by goodSplit().

## ◆ isEar()

 bool PolygonTriangulation::isEar ( Vertex * aEar ) const
inlineprivate

Function isEar Checks 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 469 of file polygon_triangulation.h.

470  {
471  const Vertex* a = aEar->prev;
472  const Vertex* b = aEar;
473  const Vertex* c = aEar->next;
474
475  // If the area >=0, then the three points for a concave sequence
476  // with b as the reflex point
477  if( area( a, b, c ) >= 0 )
478  return false;
479
480  // triangle bbox
481  const double minTX = std::min( a->x, std::min( b->x, c->x ) );
482  const double minTY = std::min( a->y, std::min( b->y, c->y ) );
483  const double maxTX = std::max( a->x, std::max( b->x, c->x ) );
484  const double maxTY = std::max( a->y, std::max( b->y, c->y ) );
485
486  // z-order range for the current triangle bounding box
487  const int32_t minZ = zOrder( minTX, minTY );
488  const int32_t maxZ = zOrder( maxTX, maxTY );
489
490  // first look for points inside the triangle in increasing z-order
491  Vertex* p = aEar->nextZ;
492
493  while( p && p->z <= maxZ )
494  {
495  if( p != a && p != c
496  && p->inTriangle( *a, *b, *c )
497  && area( p->prev, p, p->next ) >= 0 )
498  return false;
499  p = p->nextZ;
500  }
501
502  // then look for points in decreasing z-order
503  p = aEar->prevZ;
504
505  while( p && p->z >= minZ )
506  {
507  if( p != a && p != c
508  && p->inTriangle( *a, *b, *c )
509  && area( p->prev, p, p->next ) >= 0 )
510  return false;
511  p = p->prevZ;
512  }
513
514  return true;
515  }
int32_t zOrder(const double aX, const double aY) const
Calculate the Morton code of the Vertex http://www.graphics.stanford.edu/~seander/bithacks....
double area(const Vertex *p, const Vertex *q, const Vertex *r) const
Function area Returns the twice the signed area of the triangle formed by vertices p,...

Referenced by earcutList().

## ◆ locallyInside()

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

Function locallyInside Checks 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 621 of file polygon_triangulation.h.

622  {
623  if( area( a->prev, a, a->next ) < 0 )
624  return area( a, b, a->next ) >= 0 && area( a, a->prev, b ) >= 0;
625  else
626  return area( a, b, a->prev ) < 0 || area( a, a->next, b ) < 0;
627  }
double area(const Vertex *p, const Vertex *q, const Vertex *r) const
Function area Returns the twice the signed area of the triangle formed by vertices p,...

Referenced by earcutList(), and goodSplit().

## ◆ removeNullTriangles()

 Vertex* PolygonTriangulation::removeNullTriangles ( Vertex * aStart )
inlineprivate

Function removeNullTriangles Iterates 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 269 of file polygon_triangulation.h.

270  {
271  Vertex* retval = nullptr;
272  Vertex* p = aStart->next;
273
274  while( p != aStart )
275  {
276  if( area( p->prev, p, p->next ) == 0.0 )
277  {
278  p = p->prev;
279  p->next->remove();
280  retval = aStart;
281
282  if( p == p->next )
283  break;
284  }
285  p = p->next;
286  };
287
288  // We needed an end point above that wouldn't be removed, so
289  // here we do the final check for this as a Steiner point
290  if( area( aStart->prev, aStart, aStart->next ) == 0.0 )
291  {
292  retval = p->next;
293  p->remove();
294  }
295
296  return retval;
297  }
double area(const Vertex *p, const Vertex *q, const Vertex *r) const
Function area Returns the twice the signed area of the triangle formed by vertices p,...

Referenced by earcutList().

## ◆ splitPolygon()

 void PolygonTriangulation::splitPolygon ( Vertex * start )
inlineprivate

Function splitPolygon 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 524 of file polygon_triangulation.h.

525  {
526  Vertex* origPoly = start;
527  do
528  {
529  Vertex* marker = origPoly->next->next;
530  while( marker != origPoly->prev )
531  {
532  // Find a diagonal line that is wholly enclosed by the polygon interior
533  if( origPoly->i != marker->i && goodSplit( origPoly, marker ) )
534  {
535  Vertex* newPoly = origPoly->split( marker );
536
537  origPoly->updateList();
538  newPoly->updateList();
539
540  earcutList( origPoly );
541  earcutList( newPoly );
542  return;
543  }
544  marker = marker->next;
545  }
546  origPoly = origPoly->next;
547  } while( origPoly != start );
548  }
bool earcutList(Vertex *aPoint, int pass=0)
Function: earcutList Walks through a circular linked list starting at aPoint.
bool goodSplit(const Vertex *a, const Vertex *b) const
Check if a segment joining two vertices lies fully inside the polygon.

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 659 of file polygon_triangulation.h.

660  {
661  m_bbox = aPoly.BBox();
662  m_result.Clear();
663
664  if( !m_bbox.GetWidth() || !m_bbox.GetHeight() )
665  return false;
666
670  Vertex* firstVertex = createList( aPoly );
671  if( !firstVertex || firstVertex->prev == firstVertex->next )
672  return false;
673
674  firstVertex->updateList();
675
676  auto retval = earcutList( firstVertex );
677  m_vertices.clear();
678  return retval;
679  }
Vertex * createList(const ClipperLib::Path &aPath)
Function createList Takes a Clipper path and converts it into a circular, doubly-linked list for tria...
bool earcutList(Vertex *aPoint, int pass=0)
Function: earcutList Walks through a circular linked list starting at aPoint.
const BOX2I BBox(int aClearance=0) const override
Function BBox()
coord_type GetWidth() const
Definition: box2.h:197
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result
coord_type GetHeight() const
Definition: box2.h:198
std::deque< Vertex > m_vertices

## ◆ 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 244 of file polygon_triangulation.h.

245  {
246  int32_t x = static_cast<int32_t>( 32767.0 * ( aX - m_bbox.GetX() ) / m_bbox.GetWidth() );
247  int32_t y = static_cast<int32_t>( 32767.0 * ( aY - m_bbox.GetY() ) / m_bbox.GetHeight() );
248
249  x = ( x | ( x << 8 ) ) & 0x00FF00FF;
250  x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
251  x = ( x | ( x << 2 ) ) & 0x33333333;
252  x = ( x | ( x << 1 ) ) & 0x55555555;
253
254  y = ( y | ( y << 8 ) ) & 0x00FF00FF;
255  y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
256  y = ( y | ( y << 2 ) ) & 0x33333333;
257  y = ( y | ( y << 1 ) ) & 0x55555555;
258
259  return x | ( y << 1 );
260  }
coord_type GetX() const
Definition: box2.h:190
coord_type GetWidth() const
Definition: box2.h:197
coord_type GetY() const
Definition: box2.h:191
coord_type GetHeight() const
Definition: box2.h:198

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

## ◆ m_bbox

 BOX2I PolygonTriangulation::m_bbox
private

Definition at line 235 of file polygon_triangulation.h.

Referenced by TesselatePolygon(), and zOrder().

## ◆ m_result

 SHAPE_POLY_SET::TRIANGULATED_POLYGON& PolygonTriangulation::m_result
private

Definition at line 237 of file polygon_triangulation.h.

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

## ◆ m_vertices

 std::deque PolygonTriangulation::m_vertices
private

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