KiCad PCB EDA Suite
PolygonTriangulation Class Reference

#include <polygon_triangulation.h>

Classes

struct  Vertex
 

Public Member Functions

 PolygonTriangulation (SHAPE_POLY_SET::TRIANGULATED_POLYGON &aResult)
 
void 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...
 
bool removeNullTriangles (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.

Constructor & Destructor Documentation

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

Member Function Documentation

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

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

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

527  {
528  return ( q->y - p->y ) * ( r->x - q->x ) - ( q->x - p->x ) * ( r->y - q->y );
529  }
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.

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

Referenced by TesselatePolygon().

302  {
303  Vertex* tail = nullptr;
304 
305  for( auto point : aPath )
306  tail = insertVertex( VECTOR2I( point.X, point.Y ), tail );
307 
308  if( tail && ( *tail == *tail->next ) )
309  {
310  tail->next->remove();
311  }
312 
313  return tail;
314 
315  }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
Vertex * insertVertex(const VECTOR2I &pt, Vertex *last)
Function insertVertex Creates an entry in the vertices lookup and optionally inserts the newly create...
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 322 of file polygon_triangulation.h.

References SHAPE_LINE_CHAIN::CPoint(), PolygonTriangulation::Vertex::i, insertVertex(), PolygonTriangulation::Vertex::next, SHAPE_LINE_CHAIN::PointCount(), and PolygonTriangulation::Vertex::remove().

323  {
324  Vertex* tail = nullptr;
325 
326  for( int i = 0; i < points.PointCount(); i++ )
327  tail = insertVertex( points.CPoint( i ), tail );
328 
329  if( tail && ( *tail == *tail->next ) )
330  {
331  tail->next->remove();
332  }
333 
334  return tail;
335  }
int PointCount() const
Function PointCount()
void remove()
Function remove Removes the node from the linked list and z-ordered linked list.
size_t i
Definition: json11.cpp:597
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
Vertex * insertVertex(const VECTOR2I &pt, Vertex *last)
Function insertVertex Creates an entry in the vertices lookup and optionally inserts the newly create...
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 348 of file polygon_triangulation.h.

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

Referenced by splitPolygon(), and TesselatePolygon().

349  {
350  if( !aPoint )
351  return true;
352 
353  Vertex* stop = aPoint;
354  Vertex* prev;
355  Vertex* next;
356 
357  while( aPoint->prev != aPoint->next )
358  {
359  prev = aPoint->prev;
360  next = aPoint->next;
361 
362  if( isEar( aPoint ) )
363  {
364  m_result.AddTriangle( prev->i, aPoint->i, next->i );
365  aPoint->remove();
366 
367  // Skip one vertex as the triangle will account for the prev node
368  aPoint = next->next;
369  stop = next->next;
370 
371  continue;
372  }
373 
374  Vertex* nextNext = next->next;
375 
376  if( *prev != *nextNext && intersects( prev, aPoint, next, nextNext ) &&
377  locallyInside( prev, nextNext ) &&
378  locallyInside( nextNext, prev ) )
379  {
380  m_result.AddTriangle( prev->i, aPoint->i, nextNext->i );
381 
382  // remove two nodes involved
383  next->remove();
384  aPoint->remove();
385 
386  aPoint = nextNext;
387 
388  continue;
389  }
390 
391  aPoint = next;
392 
397  if( aPoint == stop )
398  {
399  // First, try to remove the remaining steiner points
400  if( removeNullTriangles( aPoint ) )
401  continue;
402 
403  // If we don't have any NULL triangles left, cut the polygon in two and try again
404  splitPolygon( aPoint );
405  break;
406  }
407  }
408 
412  return( aPoint->prev == aPoint->next );
413  }
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.
CITER next(CITER it)
Definition: ptree.cpp:130
bool 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, we use this to split the polygon into two separate lists and slice them each independently.
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 513 of file polygon_triangulation.h.

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

Referenced by splitPolygon().

514  {
515  return a->next->i != b->i &&
516  a->prev->i != b->i &&
517  !intersectsPolygon( a, b ) &&
518  locallyInside( a, b );
519  }
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 intersectsPolygon(const Vertex *a, const Vertex *b) const
Function intersectsPolygon Checks whether the segment from vertex a -> vertex b crosses any of the se...
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 590 of file polygon_triangulation.h.

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

Referenced by createList().

591  {
592  m_result.AddVertex( pt );
593  m_vertices.emplace_back( m_result.GetVertexCount() - 1, pt.x, pt.y, this );
594 
595  Vertex* p = &m_vertices.back();
596  if( !last )
597  {
598  p->prev = p;
599  p->next = p;
600  }
601  else
602  {
603  p->next = last->next;
604  p->prev = last;
605  last->next->prev = p;
606  last->next = p;
607  }
608  return p;
609  }
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result
void AddVertex(const VECTOR2I &aP)
std::deque< Vertex > m_vertices
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 536 of file polygon_triangulation.h.

References area().

Referenced by earcutList(), and intersectsPolygon().

537  {
538  if( ( *p1 == *q1 && *p2 == *q2 ) || ( *p1 == *q2 && *p2 == *q1 ) )
539  return true;
540 
541  return ( area( p1, q1, p2 ) > 0 ) != ( area( p1, q1, q2 ) > 0 )
542  && ( area( p2, q2, p1 ) > 0 ) != ( area( p2, q2, q1 ) > 0 );
543  }
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...
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 551 of file polygon_triangulation.h.

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

Referenced by goodSplit().

552  {
553  const Vertex* p = a->next;
554  do
555  {
556  if( p->i != a->i &&
557  p->next->i != a->i &&
558  p->i != b->i &&
559  p->next->i != b->i && intersects( p, p->next, a, b ) )
560  return true;
561 
562  p = p->next;
563  } while( p != a );
564 
565  return false;
566  }
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.
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 424 of file polygon_triangulation.h.

References area(), PolygonTriangulation::Vertex::inTriangle(), max, min, 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().

425  {
426  const Vertex* a = aEar->prev;
427  const Vertex* b = aEar;
428  const Vertex* c = aEar->next;
429 
430  // If the area >=0, then the three points for a concave sequence
431  // with b as the reflex point
432  if( area( a, b, c ) >= 0 )
433  return false;
434 
435  // triangle bbox
436  const double minTX = std::min( a->x, std::min( b->x, c->x ) );
437  const double minTY = std::min( a->y, std::min( b->y, c->y ) );
438  const double maxTX = std::max( a->x, std::max( b->x, c->x ) );
439  const double maxTY = std::max( a->y, std::max( b->y, c->y ) );
440 
441  // z-order range for the current triangle bounding box
442  const int32_t minZ = zOrder( minTX, minTY );
443  const int32_t maxZ = zOrder( maxTX, maxTY );
444 
445  // first look for points inside the triangle in increasing z-order
446  Vertex* p = aEar->nextZ;
447 
448  while( p && p->z <= maxZ )
449  {
450  if( p != a && p != c
451  && p->inTriangle( *a, *b, *c )
452  && area( p->prev, p, p->next ) >= 0 )
453  return false;
454  p = p->nextZ;
455  }
456 
457  // then look for points in decreasing z-order
458  p = aEar->prevZ;
459 
460  while( p && p->z >= minZ )
461  {
462  if( p != a && p != c
463  && p->inTriangle( *a, *b, *c )
464  && area( p->prev, p, p->next ) >= 0 )
465  return false;
466  p = p->prevZ;
467  }
468 
469  return true;
470  }
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 max(a, b)
Definition: auxiliary.h:86
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.
#define min(a, b)
Definition: auxiliary.h:85
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 576 of file polygon_triangulation.h.

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

Referenced by earcutList(), and goodSplit().

577  {
578  if( area( a->prev, a, a->next ) < 0 )
579  return area( a, b, a->next ) >= 0 && area( a, a->prev, b ) >= 0;
580  else
581  return area( a, b, a->prev ) < 0 || area( a, a->next, b ) < 0;
582  }
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...
bool 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.

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

Referenced by earcutList().

267  {
268  bool retval = false;
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 = true;
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  p->remove();
290  retval = true;
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...
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 479 of file polygon_triangulation.h.

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

Referenced by earcutList().

480  {
481  Vertex* origPoly = start;
482  do
483  {
484  Vertex* marker = origPoly->next->next;
485  while( marker != origPoly->prev )
486  {
487  // Find a diagonal line that is wholly enclosed by the polygon interior
488  if( origPoly->i != marker->i && goodSplit( origPoly, marker ) )
489  {
490  Vertex* newPoly = origPoly->split( marker );
491 
492  origPoly->updateList();
493  newPoly->updateList();
494 
495  earcutList( origPoly );
496  earcutList( newPoly );
497  return;
498  }
499  marker = marker->next;
500  }
501  origPoly = origPoly->next;
502  } while( origPoly != start );
503  }
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)
Function: earcutList Walks through a circular linked list starting at aPoint.
void PolygonTriangulation::TesselatePolygon ( const SHAPE_LINE_CHAIN aPoly)
inline

Definition at line 614 of file polygon_triangulation.h.

References SHAPE_LINE_CHAIN::BBox(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::Clear(), SHAPE_LINE_CHAIN::convertToClipper(), createList(), earcutList(), BOX2< Vec >::GetHeight(), BOX2< Vec >::GetWidth(), and PolygonTriangulation::Vertex::updateList().

Referenced by SHAPE_POLY_SET::CacheTriangulation().

615  {
616  ClipperLib::Clipper c;
617  m_bbox = aPoly.BBox();
618 
619  if( !m_bbox.GetWidth() || !m_bbox.GetHeight() )
620  return;
621 
622  Vertex* outerNode = createList( aPoly );
623  if( !outerNode )
624  return;
625 
626  outerNode->updateList();
627  if( !earcutList( outerNode ) )
628  {
629  m_vertices.clear();
630  m_result.Clear();
631 
632  ClipperLib::Paths simplified;
633  ClipperLib::SimplifyPolygon( aPoly.convertToClipper( true ), simplified );
634 
635  for( auto path : simplified )
636  {
637  outerNode = createList( path );
638  if( !outerNode )
639  return;
640 
641  earcutList( outerNode );
642  }
643  }
644 
645  m_vertices.clear();
646  }
Vertex * createList(const ClipperLib::Path &aPath)
Function createList Takes a Clipper path and converts it into a circular, doubly-linked list for tria...
ClipperLib::Path convertToClipper(bool aRequiredOrientation) const
Creates a new Clipper path from the SHAPE_LINE_CHAIN in a given orientation.
coord_type GetWidth() const
Definition: box2.h:195
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()
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result
coord_type GetHeight() const
Definition: box2.h:196
std::deque< Vertex > m_vertices
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.

References BOX2< Vec >::GetHeight(), BOX2< Vec >::GetWidth(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), PolygonTriangulation::Vertex::x, and PolygonTriangulation::Vertex::y.

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

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 GetY() const
Definition: box2.h:189
coord_type GetWidth() const
Definition: box2.h:195
coord_type GetHeight() const
Definition: box2.h:196
coord_type GetX() const
Definition: box2.h:188

Member Data Documentation

BOX2I PolygonTriangulation::m_bbox
private

Definition at line 232 of file polygon_triangulation.h.

SHAPE_POLY_SET::TRIANGULATED_POLYGON& PolygonTriangulation::m_result
private

Definition at line 234 of file polygon_triangulation.h.

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

Definition at line 233 of file polygon_triangulation.h.

Referenced by PolygonTriangulation::Vertex::split().


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