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  }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
Vertex * insertVertex(const VECTOR2I &pt, Vertex *last)
Create an entry in the vertices lookup and optionally inserts the newly created vertex into an existi...

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  }
void remove()
Remove the node from the linked list and z-ordered linked list.
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.
Vertex * insertVertex(const VECTOR2I &pt, Vertex *last)
Create an entry in the vertices lookup and optionally inserts the newly created vertex into an existi...

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  }
CITER next(CITER it)
Definition: ptree.cpp:126
bool intersects(const Vertex *p1, const Vertex *q1, const Vertex *p2, const Vertex *q2) const
Check for intersection between two segments, end points included.
Vertex * removeNullTriangles(Vertex *aStart)
Iterate 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
Check whether the segment from vertex a -> vertex b is inside the polygon around the immediate area o...
void AddTriangle(int a, int b, int c)
bool isEar(Vertex *aEar) const
Check whether the given vertex is in the middle of an ear.
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 splitPolygon(Vertex *start)
If we cannot find an ear to slice in the current polygon list, we use this to split the polygon into ...

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...
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...

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  }
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result
void AddVertex(const VECTOR2I &aP)
std::deque< Vertex > m_vertices

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  }
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.

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  }
bool intersects(const Vertex *p1, const Vertex *q1, const Vertex *p2, const Vertex *q2) const
Check for intersection between two segments, end points included.

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....
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.

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  }
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.

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  }
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.

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 earcutList(Vertex *aPoint, int pass=0)
Walk 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.

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();
69  m_result.Clear();
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  }
Vertex * createList(const ClipperLib::Path &aPath)
Take a Clipper path and converts it into a circular, doubly-linked list for triangulation.
bool earcutList(Vertex *aPoint, int pass=0)
Walk through a circular linked list starting at aPoint.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
coord_type GetWidth() const
Definition: box2.h:180
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result
coord_type GetHeight() const
Definition: box2.h:181
std::deque< Vertex > m_vertices

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().

◆ 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 GetX() const
Definition: box2.h:173
coord_type GetWidth() const
Definition: box2.h:180
coord_type GetY() const
Definition: box2.h:174
coord_type GetHeight() const
Definition: box2.h:181

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: