#include <polygon_triangulation.h>

Classes
struct	VERTEX

Public Member Functions
	POLYGON_TRIANGULATION (SHAPE_POLY_SET::TRIANGULATED_POLYGON &aResult)

bool	TesselatePolygon (const SHAPE_LINE_CHAIN &aPoly, SHAPE_POLY_SET::TRIANGULATED_POLYGON *aHintData)

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.

void	logRemaining ()
	Outputs a list of vertices that have not yet been triangulated.

void	logVertices (VERTEX aStart, std::set< VERTEX > *aSeen)

VERTEX *	simplifyList (VERTEX *aStart)
	Simplify the line chain by removing points that are too close to each other.

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

VERTEX *	createList (const SHAPE_LINE_CHAIN &points)
	Take a SHAPE_LINE_CHAIN and links each point into a circular, doubly-linked list.

bool	earcutList (VERTEX *aPoint, int pass=0)
	Walk through a circular linked list starting at aPoint.

bool	isTooSmall (const VERTEX *aPoint) const
	Check whether a given vertex is too small to matter.

bool	isEar (VERTEX *aEar) const
	Check whether the given vertex is in the middle of an ear.

void	subdividePolygon (VERTEX *aStart, int pass=0)
	Inserts a new vertex halfway between each existing pair of vertices.

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

bool	goodSplit (const VERTEX a, const VERTEX b) const
	Check if a segment joining two vertices lies fully inside the polygon.

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.

constexpr int	sign (double aVal) const

constexpr bool	overlapping (const VERTEX p, const VERTEX q, const VERTEX *r) const
	If p, q, and r are collinear and r lies between p and q, then return true.

bool	intersects (const VERTEX p1, const VERTEX q1, const VERTEX p2, const VERTEX q2) const
	Check for intersection between two segments, end points included.

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.

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.

bool	middleInside (const VERTEX a, const VERTEX b) const
	Check to see if the segment halfway point between a and b is inside the polygon.

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.

Private Attributes
BOX2I	m_bbox

std::deque< VERTEX >	m_vertices

size_t	m_vertices_original_size

SHAPE_POLY_SET::TRIANGULATED_POLYGON &	m_result

Detailed Description

Definition at line 63 of file polygon_triangulation.h.

Constructor & Destructor Documentation

◆ POLYGON_TRIANGULATION()

POLYGON_TRIANGULATION::POLYGON_TRIANGULATION ( SHAPE_POLY_SET::TRIANGULATED_POLYGON & aResult )

inline

Definition at line 66 of file polygon_triangulation.h.

Member Function Documentation

◆ area()

double POLYGON_TRIANGULATION::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 962 of file polygon_triangulation.h.

References POLYGON_TRIANGULATION::VERTEX::x, and POLYGON_TRIANGULATION::VERTEX::y.

Referenced by earcutList(), goodSplit(), intersects(), isEar(), locallyInside(), removeNullTriangles(), and splitPolygon().

◆ createList()

VERTEX * POLYGON_TRIANGULATION::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 516 of file polygon_triangulation.h.

References SHAPE_LINE_CHAIN::CPoint(), ADVANCED_CFG::GetCfg(), insertVertex(), ADVANCED_CFG::m_TriangulateSimplificationLevel, POLYGON_TRIANGULATION::VERTEX::next, SHAPE_LINE_CHAIN::PointCount(), POLYGON_TRIANGULATION::VERTEX::remove(), VECTOR2< T >::SquaredEuclideanNorm(), TRIANGULATE_TRACE, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by TesselatePolygon().

◆ earcutList()

bool POLYGON_TRIANGULATION::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 577 of file polygon_triangulation.h.

References std::abs(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::AddTriangle(), POLYGON_TRIANGULATION::VERTEX::area(), area(), ADVANCED_CFG::GetCfg(), POLYGON_TRIANGULATION::VERTEX::i, intersects(), isEar(), isTooSmall(), locallyInside(), m_result, ADVANCED_CFG::m_TriangulateMinimumArea, next(), POLYGON_TRIANGULATION::VERTEX::next, POLYGON_TRIANGULATION::VERTEX::prev, POLYGON_TRIANGULATION::VERTEX::remove(), removeNullTriangles(), splitPolygon(), subdividePolygon(), and TRIANGULATE_TRACE.

Referenced by splitPolygon(), and TesselatePolygon().

◆ goodSplit()

bool POLYGON_TRIANGULATION::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. Next, we ensure that the proposed split is inside the local area of the polygon at both ends and the midpoint. Finally, we check to split creates two new polygons, each with positive area.

Definition at line 945 of file polygon_triangulation.h.

References POLYGON_TRIANGULATION::VERTEX::area(), area(), POLYGON_TRIANGULATION::VERTEX::i, intersectsPolygon(), locallyInside(), middleInside(), POLYGON_TRIANGULATION::VERTEX::next, POLYGON_TRIANGULATION::VERTEX::nextZ, POLYGON_TRIANGULATION::VERTEX::prev, and POLYGON_TRIANGULATION::VERTEX::prevZ.

Referenced by splitPolygon().

◆ insertVertex()

VERTEX * POLYGON_TRIANGULATION::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 1083 of file polygon_triangulation.h.

References SHAPE_POLY_SET::TRIANGULATED_POLYGON::AddVertex(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetVertexCount(), m_result, m_vertices, POLYGON_TRIANGULATION::VERTEX::next, POLYGON_TRIANGULATION::VERTEX::prev, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by createList(), and subdividePolygon().

◆ intersects()

bool POLYGON_TRIANGULATION::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 989 of file polygon_triangulation.h.

References area(), overlapping(), and sign().

Referenced by earcutList(), and intersectsPolygon().

◆ intersectsPolygon()

bool POLYGON_TRIANGULATION::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 1021 of file polygon_triangulation.h.

References POLYGON_TRIANGULATION::VERTEX::i, intersects(), m_vertices, and m_vertices_original_size.

Referenced by goodSplit().

◆ isEar()

bool POLYGON_TRIANGULATION::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 731 of file polygon_triangulation.h.

References area(), POLYGON_TRIANGULATION::VERTEX::inTriangle(), POLYGON_TRIANGULATION::VERTEX::next, POLYGON_TRIANGULATION::VERTEX::nextZ, POLYGON_TRIANGULATION::VERTEX::prev, POLYGON_TRIANGULATION::VERTEX::prevZ, POLYGON_TRIANGULATION::VERTEX::x, POLYGON_TRIANGULATION::VERTEX::y, POLYGON_TRIANGULATION::VERTEX::z, and zOrder().

Referenced by earcutList().

◆ isTooSmall()

bool POLYGON_TRIANGULATION::isTooSmall ( const VERTEX * aPoint ) const

inlineprivate

Check whether a given vertex is too small to matter.

Definition at line 708 of file polygon_triangulation.h.

References ADVANCED_CFG::GetCfg(), ADVANCED_CFG::m_TriangulateMinimumArea, POLYGON_TRIANGULATION::VERTEX::next, POLYGON_TRIANGULATION::VERTEX::prev, POLYGON_TRIANGULATION::VERTEX::x, and POLYGON_TRIANGULATION::VERTEX::y.

Referenced by earcutList().

◆ locallyInside()

bool POLYGON_TRIANGULATION::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 1047 of file polygon_triangulation.h.

References area(), POLYGON_TRIANGULATION::VERTEX::next, and POLYGON_TRIANGULATION::VERTEX::prev.

Referenced by earcutList(), and goodSplit().

◆ logRemaining()

void POLYGON_TRIANGULATION::logRemaining ( )

inlineprivate

Outputs a list of vertices that have not yet been triangulated.

Definition at line 343 of file polygon_triangulation.h.

References logVertices(), and m_vertices.

Referenced by TesselatePolygon().

◆ logVertices()

void POLYGON_TRIANGULATION::logVertices	(	VERTEX *	aStart,
		std::set< VERTEX * > *	aSeen
	)

inlineprivate

Definition at line 356 of file polygon_triangulation.h.

References POLYGON_TRIANGULATION::VERTEX::next, TRIANGULATE_TRACE, POLYGON_TRIANGULATION::VERTEX::x, and POLYGON_TRIANGULATION::VERTEX::y.

Referenced by logRemaining(), and splitPolygon().

◆ middleInside()

bool POLYGON_TRIANGULATION::middleInside	(	const VERTEX *	a,
		const VERTEX *	b
	)		const

inlineprivate

Check to see if the segment halfway point between a and b is inside the polygon.

Definition at line 1058 of file polygon_triangulation.h.

References POLYGON_TRIANGULATION::VERTEX::next, POLYGON_TRIANGULATION::VERTEX::x, and POLYGON_TRIANGULATION::VERTEX::y.

Referenced by goodSplit().

◆ overlapping()

constexpr bool POLYGON_TRIANGULATION::overlapping	(	const VERTEX *	p,
		const VERTEX *	q,
		const VERTEX *	r
	)		const

inlineconstexprprivate

If p, q, and r are collinear and r lies between p and q, then return true.

Definition at line 976 of file polygon_triangulation.h.

References POLYGON_TRIANGULATION::VERTEX::x, and POLYGON_TRIANGULATION::VERTEX::y.

Referenced by intersects().

◆ removeNullTriangles()

VERTEX * POLYGON_TRIANGULATION::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

We've removed all possible triangles

Definition at line 446 of file polygon_triangulation.h.

References std::abs(), area(), POLYGON_TRIANGULATION::VERTEX::next, POLYGON_TRIANGULATION::VERTEX::prev, POLYGON_TRIANGULATION::VERTEX::remove(), simplifyList(), TRIANGULATE_TRACE, POLYGON_TRIANGULATION::VERTEX::x, and POLYGON_TRIANGULATION::VERTEX::y.

Referenced by earcutList().

◆ sign()

constexpr int POLYGON_TRIANGULATION::sign ( double aVal ) const

inlineconstexprprivate

Definition at line 968 of file polygon_triangulation.h.

Referenced by intersects().

◆ simplifyList()

VERTEX * POLYGON_TRIANGULATION::simplifyList ( VERTEX * aStart )

inlineprivate

Simplify the line chain by removing points that are too close to each other.

If no points are removed, it returns nullptr.

Definition at line 391 of file polygon_triangulation.h.

References ADVANCED_CFG::GetCfg(), ADVANCED_CFG::m_TriangulateSimplificationLevel, next(), POLYGON_TRIANGULATION::VERTEX::next, POLYGON_TRIANGULATION::VERTEX::prev, POLYGON_TRIANGULATION::VERTEX::remove(), VECTOR2< T >::SquaredEuclideanNorm(), TRIANGULATE_TRACE, POLYGON_TRIANGULATION::VERTEX::x, and POLYGON_TRIANGULATION::VERTEX::y.

Referenced by removeNullTriangles().

◆ splitPolygon()

bool POLYGON_TRIANGULATION::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 840 of file polygon_triangulation.h.

References area(), earcutList(), goodSplit(), POLYGON_TRIANGULATION::VERTEX::i, logVertices(), next(), POLYGON_TRIANGULATION::VERTEX::next, POLYGON_TRIANGULATION::VERTEX::nextZ, POLYGON_TRIANGULATION::VERTEX::prev, POLYGON_TRIANGULATION::VERTEX::prevZ, POLYGON_TRIANGULATION::VERTEX::split(), TRIANGULATE_TRACE, and POLYGON_TRIANGULATION::VERTEX::updateList().