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

## ◆ PolygonTriangulation()

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

Definition at line 61 of file polygon_triangulation.h.

61  :
62  m_result( aResult )
63  {};
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 568 of file polygon_triangulation.h.

569  {
570  return ( q->y - p->y ) * ( r->x - q->x ) - ( q->x - p->x ) * ( r->y - q->y );
571  }

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

302  {
303  Vertex* tail = nullptr;
304  double sum = 0.0;
305  auto len = aPath.size();
306
307  // Check for winding order
308  for( size_t i = 0; i < len; i++ )
309  {
310  auto p1 = aPath.at( i );
311  auto p2 = aPath.at( ( i + 1 ) < len ? i + 1 : 0 );
312
313  sum += ( ( p2.X - p1.X ) * ( p2.Y + p1.Y ) );
314  }
315
316  if( sum <= 0.0 )
317  {
318  for( auto point : aPath )
319  tail = insertVertex( VECTOR2I( point.X, point.Y ), tail );
320  }
321  else
322  {
323  for( size_t i = 0; i < len; i++ )
324  {
325  auto p = aPath.at( len - i - 1 );
326  tail = insertVertex( VECTOR2I( p.X, p.Y ), tail );
327  }
328  }
329
330  if( tail && ( *tail == *tail->next ) )
331  {
332  tail->next->remove();
333  }
334
335  return tail;
336
337  }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
size_t i
Definition: json11.cpp:649
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 344 of file polygon_triangulation.h.

345  {
346  Vertex* tail = nullptr;
347  double sum = 0.0;
348
349  // Check for winding order
350  for( int i = 0; i < points.PointCount(); i++ )
351  {
352  VECTOR2D p1 = points.CPoint( i );
353  VECTOR2D p2 = points.CPoint( i + 1 );
354
355  sum += ( ( p2.x - p1.x ) * ( p2.y + p1.y ) );
356  }
357
358  if( sum > 0.0 )
359  for( int i = points.PointCount() - 1; i >= 0; i--)
360  tail = insertVertex( points.CPoint( i ), tail );
361  else
362  for( int i = 0; i < points.PointCount(); i++ )
363  tail = insertVertex( points.CPoint( i ), tail );
364
365  if( tail && ( *tail == *tail->next ) )
366  {
367  tail->next->remove();
368  }
369
370  return tail;
371  }
void remove()
Function remove Removes the node from the linked list and z-ordered linked list.
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
size_t i
Definition: json11.cpp:649
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 384 of file polygon_triangulation.h.

385  {
386  if( !aPoint )
387  return true;
388
389  Vertex* stop = aPoint;
390  Vertex* prev;
391  Vertex* next;
392
393  while( aPoint->prev != aPoint->next )
394  {
395  prev = aPoint->prev;
396  next = aPoint->next;
397
398  if( isEar( aPoint ) )
399  {
400  m_result.AddTriangle( prev->i, aPoint->i, next->i );
401  aPoint->remove();
402
403  // Skip one vertex as the triangle will account for the prev node
404  aPoint = next->next;
405  stop = next->next;
406
407  continue;
408  }
409
410  Vertex* nextNext = next->next;
411
412  if( *prev != *nextNext && intersects( prev, aPoint, next, nextNext ) &&
413  locallyInside( prev, nextNext ) &&
414  locallyInside( nextNext, prev ) )
415  {
416  m_result.AddTriangle( prev->i, aPoint->i, nextNext->i );
417
418  // remove two nodes involved
419  next->remove();
420  aPoint->remove();
421
422  aPoint = nextNext;
423  stop = nextNext;
424
425  continue;
426  }
427
428  aPoint = next;
429
434  if( aPoint == stop )
435  {
436  // First, try to remove the remaining steiner points
437  // If aPoint is a steiner, we need to re-assign both the start and stop points
438  if( auto newPoint = removeNullTriangles( aPoint ) )
439  {
440  aPoint = newPoint;
441  stop = newPoint;
442  continue;
443  }
444
445  // If we don't have any NULL triangles left, cut the polygon in two and try again
446  splitPolygon( aPoint );
447  break;
448  }
449  }
450
454  return( aPoint->prev == aPoint->next );
455  }
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 555 of file polygon_triangulation.h.

556  {
557  return a->next->i != b->i &&
558  a->prev->i != b->i &&
559  !intersectsPolygon( a, b ) &&
560  locallyInside( a, b );
561  }
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 632 of file polygon_triangulation.h.

633  {
635  m_vertices.emplace_back( m_result.GetVertexCount() - 1, pt.x, pt.y, this );
636
637  Vertex* p = &m_vertices.back();
638  if( !last )
639  {
640  p->prev = p;
641  p->next = p;
642  }
643  else
644  {
645  p->next = last->next;
646  p->prev = last;
647  last->next->prev = p;
648  last->next = p;
649  }
650  return p;
651  }
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 578 of file polygon_triangulation.h.

579  {
580  if( ( *p1 == *q1 && *p2 == *q2 ) || ( *p1 == *q2 && *p2 == *q1 ) )
581  return true;
582
583  return ( area( p1, q1, p2 ) > 0 ) != ( area( p1, q1, q2 ) > 0 )
584  && ( area( p2, q2, p1 ) > 0 ) != ( area( p2, q2, q1 ) > 0 );
585  }
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 593 of file polygon_triangulation.h.

594  {
595  const Vertex* p = a->next;
596  do
597  {
598  if( p->i != a->i &&
599  p->next->i != a->i &&
600  p->i != b->i &&
601  p->next->i != b->i && intersects( p, p->next, a, b ) )
602  return true;
603
604  p = p->next;
605  } while( p != a );
606
607  return false;
608  }
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 466 of file polygon_triangulation.h.

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

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

619  {
620  if( area( a->prev, a, a->next ) < 0 )
621  return area( a, b, a->next ) >= 0 && area( a, a->prev, b ) >= 0;
622  else
623  return area( a, b, a->prev ) < 0 || area( a, a->next, b ) < 0;
624  }
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 266 of file polygon_triangulation.h.

267  {
268  Vertex* retval = nullptr;
269  Vertex* p = aStart->next;
270
271  while( p != aStart )
272  {
273  if( area( p->prev, p, p->next ) == 0.0 )
274  {
275  p = p->prev;
276  p->next->remove();
277  retval = aStart;
278
279  if( p == p->next )
280  break;
281  }
282  p = p->next;
283  };
284
285  // We needed an end point above that wouldn't be removed, so
286  // here we do the final check for this as a Steiner point
287  if( area( aStart->prev, aStart, aStart->next ) == 0.0 )
288  {
289  retval = p->next;
290  p->remove();
291  }
292
293  return retval;
294  }
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 521 of file polygon_triangulation.h.

522  {
523  Vertex* origPoly = start;
524  do
525  {
526  Vertex* marker = origPoly->next->next;
527  while( marker != origPoly->prev )
528  {
529  // Find a diagonal line that is wholly enclosed by the polygon interior
530  if( origPoly->i != marker->i && goodSplit( origPoly, marker ) )
531  {
532  Vertex* newPoly = origPoly->split( marker );
533
534  origPoly->updateList();
535  newPoly->updateList();
536
537  earcutList( origPoly );
538  earcutList( newPoly );
539  return;
540  }
541  marker = marker->next;
542  }
543  origPoly = origPoly->next;
544  } while( origPoly != start );
545  }
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 656 of file polygon_triangulation.h.

657  {
658  m_bbox = aPoly.BBox();
659  m_result.Clear();
660
661  if( !m_bbox.GetWidth() || !m_bbox.GetHeight() )
662  return false;
663
667  Vertex* firstVertex = createList( aPoly );
668  if( !firstVertex || firstVertex->prev == firstVertex->next )
669  return false;
670
671  firstVertex->updateList();
672
673  auto retval = earcutList( firstVertex );
674  m_vertices.clear();
675  return retval;
676  }
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:195
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result
coord_type GetHeight() const
Definition: box2.h:196
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 241 of file polygon_triangulation.h.

242  {
243  int32_t x = static_cast<int32_t>( 32767.0 * ( aX - m_bbox.GetX() ) / m_bbox.GetWidth() );
244  int32_t y = static_cast<int32_t>( 32767.0 * ( aY - m_bbox.GetY() ) / m_bbox.GetHeight() );
245
246  x = ( x | ( x << 8 ) ) & 0x00FF00FF;
247  x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
248  x = ( x | ( x << 2 ) ) & 0x33333333;
249  x = ( x | ( x << 1 ) ) & 0x55555555;
250
251  y = ( y | ( y << 8 ) ) & 0x00FF00FF;
252  y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
253  y = ( y | ( y << 2 ) ) & 0x33333333;
254  y = ( y | ( y << 1 ) ) & 0x55555555;
255
256  return x | ( y << 1 );
257  }
coord_type GetX() const
Definition: box2.h:188
coord_type GetWidth() const
Definition: box2.h:195
coord_type GetY() const
Definition: box2.h:189
coord_type GetHeight() const
Definition: box2.h:196

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

## ◆ m_bbox

 BOX2I PolygonTriangulation::m_bbox
private

Definition at line 232 of file polygon_triangulation.h.

Referenced by TesselatePolygon(), and zOrder().

## ◆ m_result

 SHAPE_POLY_SET::TRIANGULATED_POLYGON& PolygonTriangulation::m_result
private

Definition at line 234 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: