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

Vertex *	removeNullTriangles (Vertex *aStart)
	Iterate through the list to remove NULL triangles if they exist. More...

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

Vertex *	createList (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...

Vertex *	insertVertex (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< Vertex >	m_vertices

SHAPE_POLY_SET::TRIANGULATED_POLYGON &	m_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.

 :
 m_result( aResult )
 {};

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

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

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

 {
 Vertex* tail = nullptr;
 double sum = 0.0;
 auto len = aPath.size();
 
 // Check for winding order
 for( size_t i = 0; i < len; i++ )
 {
 auto p1 = aPath.at( i );
 auto p2 = aPath.at( ( i + 1 ) < len ? i + 1 : 0 );
 
 sum += ( ( p2.X - p1.X ) * ( p2.Y + p1.Y ) );
 }
 
 if( sum <= 0.0 )
 {
 for( auto point : aPath )
 tail = insertVertex( VECTOR2I( point.X, point.Y ), tail );
 }
 else
 {
 for( size_t i = 0; i < len; i++ )
 {
 auto p = aPath.at( len - i - 1 );
 tail = insertVertex( VECTOR2I( p.X, p.Y ), tail );
 }
 }
 
 if( tail && ( *tail == *tail->next ) )
 {
 tail->next->remove();
 }
 
 return tail;
 
 }

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

 {
 Vertex* tail = nullptr;
 double sum = 0.0;
 
 // Check for winding order
 for( int i = 0; i < points.PointCount(); i++ )
 {
 VECTOR2D p1 = points.CPoint( i );
 VECTOR2D p2 = points.CPoint( i + 1 );
 
 sum += ( ( p2.x - p1.x ) * ( p2.y + p1.y ) );
 }
 
 if( sum > 0.0 )
 for( int i = points.PointCount() - 1; i >= 0; i--)
 tail = insertVertex( points.CPoint( i ), tail );
 else
 for( int i = 0; i < points.PointCount(); i++ )
 tail = insertVertex( points.CPoint( i ), tail );
 
 if( tail && ( *tail == *tail->next ) )
 {
 tail->next->remove();
 }
 
 return tail;
 }

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

 {
 if( !aPoint )
 return true;
 
 Vertex* stop = aPoint;
 Vertex* prev;
 Vertex* next;
 
 while( aPoint->prev != aPoint->next )
 {
 prev = aPoint->prev;
 next = aPoint->next;
 
 if( isEar( aPoint ) )
 {
 m_result.AddTriangle( prev->i, aPoint->i, next->i );
 aPoint->remove();
 
 // Skip one vertex as the triangle will account for the prev node
 aPoint = next->next;
 stop = next->next;
 
 continue;
 }
 
 Vertex* nextNext = next->next;
 
 if( *prev != *nextNext && intersects( prev, aPoint, next, nextNext ) &&
 locallyInside( prev, nextNext ) &&
 locallyInside( nextNext, prev ) )
 {
 m_result.AddTriangle( prev->i, aPoint->i, nextNext->i );
 
 // remove two nodes involved
 next->remove();
 aPoint->remove();
 
 aPoint = nextNext;
 stop = nextNext;
 
 continue;
 }
 
 aPoint = next;
 
 /*
 * We've searched the entire polygon for available ears and there are still
 * un-sliced nodes remaining.
 */
 if( aPoint == stop )
 {
 // First, try to remove the remaining steiner points
 // If aPoint is a steiner, we need to re-assign both the start and stop points
 if( auto newPoint = removeNullTriangles( aPoint ) )
 {
 aPoint = newPoint;
 stop = newPoint;
 continue;
 }
 
 // If we don't have any NULL triangles left, cut the polygon in two and try again
 splitPolygon( aPoint );
 break;
 }
 }
 
 // Check to see if we are left with only three points in the polygon
 if( aPoint->next && aPoint->prev == aPoint->next->next )
 {
 // Three concave points will never be able to be triangulated because they were
 // created by an intersecting polygon, so just drop them.
 if( area( aPoint->prev, aPoint, aPoint->next ) >= 0 )
 return true;
 }
 
 /*
 * At this point, our polygon should be fully tessellated.
 */
 return( aPoint->prev == aPoint->next );
 }

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

 {
 return a->next->i != b->i &&
 a->prev->i != b->i &&
 !intersectsPolygon( a, b ) &&
 locallyInside( a, b );
 }

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

 {
 m_result.AddVertex( pt );
 m_vertices.emplace_back( m_result.GetVertexCount() - 1, pt.x, pt.y, this );
 
 Vertex* p = &m_vertices.back();
 
 if( !last )
 {
 p->prev = p;
 p->next = p;
 }
 else
 {
 p->next = last->next;
 p->prev = last;
 last->next->prev = p;
 last->next = p;
 }
 return p;
 }

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

 {
 if( ( *p1 == *q1 && *p2 == *q2 ) || ( *p1 == *q2 && *p2 == *q1 ) )
 return true;
 
 return ( area( p1, q1, p2 ) > 0 ) != ( area( p1, q1, q2 ) > 0 )
 && ( area( p2, q2, p1 ) > 0 ) != ( area( p2, q2, q1 ) > 0 );
 }

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

 {
 const Vertex* p = a->next;
 
 do
 {
 if( p->i != a->i &&
 p->next->i != a->i &&
 p->i != b->i &&
 p->next->i != b->i && intersects( p, p->next, a, b ) )
 return true;
 
 p = p->next;
 } while( p != a );
 
 return false;
 }

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

 {
 const Vertex* a = aEar->prev;
 const Vertex* b = aEar;
 const Vertex* c = aEar->next;
 
 // If the area >=0, then the three points for a concave sequence
 // with b as the reflex point
 if( area( a, b, c ) >= 0 )
 return false;
 
 // triangle bbox
 const double minTX = std::min( a->x, std::min( b->x, c->x ) );
 const double minTY = std::min( a->y, std::min( b->y, c->y ) );
 const double maxTX = std::max( a->x, std::max( b->x, c->x ) );
 const double maxTY = std::max( a->y, std::max( b->y, c->y ) );
 
 // z-order range for the current triangle bounding box
 const int32_t minZ = zOrder( minTX, minTY );
 const int32_t maxZ = zOrder( maxTX, maxTY );
 
 // first look for points inside the triangle in increasing z-order
 Vertex* p = aEar->nextZ;
 
 while( p && p->z <= maxZ )
 {
 if( p != a && p != c
 && p->inTriangle( *a, *b, *c )
 && area( p->prev, p, p->next ) >= 0 )
 return false;
 
 p = p->nextZ;
 }
 
 // then look for points in decreasing z-order
 p = aEar->prevZ;
 
 while( p && p->z >= minZ )
 {
 if( p != a && p != c
 && p->inTriangle( *a, *b, *c )
 && area( p->prev, p, p->next ) >= 0 )
 return false;
 
 p = p->prevZ;
 }
 
 return true;
 }

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

 {
 if( area( a->prev, a, a->next ) < 0 )
 return area( a, b, a->next ) >= 0 && area( a, a->prev, b ) >= 0;
 else
 return area( a, b, a->prev ) < 0 || area( a, a->next, b ) < 0;
 }

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

 {
 Vertex* retval = nullptr;
 Vertex* p = aStart->next;
 
 while( p != aStart )
 {
 if( area( p->prev, p, p->next ) == 0.0 )
 {
 p = p->prev;
 p->next->remove();
 retval = aStart;
 
 if( p == p->next )
 break;
 }
 p = p->next;
 };
 
 // We needed an end point above that wouldn't be removed, so
 // here we do the final check for this as a Steiner point
 if( area( aStart->prev, aStart, aStart->next ) == 0.0 )
 {
 retval = p->next;
 p->remove();
 }
 
 return retval;
 }

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

 {
 Vertex* origPoly = start;
 
 do
 {
 Vertex* marker = origPoly->next->next;
 
 while( marker != origPoly->prev )
 {
 // Find a diagonal line that is wholly enclosed by the polygon interior
 if( origPoly->i != marker->i && goodSplit( origPoly, marker ) )
 {
 Vertex* newPoly = origPoly->split( marker );
 
 origPoly->updateList();
 newPoly->updateList();
 
 earcutList( origPoly );
 earcutList( newPoly );
 return;
 }
 
 marker = marker->next;
 }
 
 origPoly = origPoly->next;
 } while( origPoly != start );
 }

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.

 {
 m_bbox = aPoly.BBox();
 m_result.Clear();
 
 if( !m_bbox.GetWidth() || !m_bbox.GetHeight() )
 return false;
 
 Vertex* firstVertex = createList( aPoly );
 if( !firstVertex || firstVertex->prev == firstVertex->next )
 return false;
 
 firstVertex->updateList();
 
 auto retval = earcutList( firstVertex );
 m_vertices.clear();
 return retval;
 }

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

 {
 int32_t x = static_cast<int32_t>( 32767.0 * ( aX - m_bbox.GetX() ) / m_bbox.GetWidth() );
 int32_t y = static_cast<int32_t>( 32767.0 * ( aY - m_bbox.GetY() ) / m_bbox.GetHeight() );
 
 x = ( x | ( x << 8 ) ) & 0x00FF00FF;
 x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
 x = ( x | ( x << 2 ) ) & 0x33333333;
 x = ( x | ( x << 1 ) ) & 0x55555555;
 
 y = ( y | ( y << 8 ) ) & 0x00FF00FF;
 y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
 y = ( y | ( y << 2 ) ) & 0x33333333;
 y = ( y | ( y << 1 ) ) & 0x55555555;
 
 return x | ( y << 1 );
 }