#include <polygon_triangulation.h>

Inheritance diagram for POLYGON_TRIANGULATION:

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

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

void	SetBoundingBox (const BOX2I &aBBox)

VERTEX *	insertVertex (int aIndex, const VECTOR2I &pt, VERTEX last, void aUserData=nullptr)
	Insert a vertex into the vertex set.

VERTEX *	createList (const SHAPE_LINE_CHAIN &points, VERTEX aTail=nullptr, void aUserData=nullptr)
	Create a list of vertices from a line chain.

Protected Member Functions
VERTEX *	getNextOutlineVertex (const VERTEX *aPt) const
	Get the next vertex in the outline, avoiding steiner points and points that overlap with splits.

VERTEX *	getPrevOutlineVertex (const VERTEX *aPt) const
	Get the previous vertex in the outline, avoiding steiner points and points that overlap with splits.

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 if the middle of the segment from a to b is inside the polygon.

bool	same_point (const VERTEX aA, const VERTEX aB) const
	Check if two vertices are at the same point.

uint32_t	zOrder (const double aX, const double aY) const
	Note that while the inputs are doubles, these are scaled by the size of the bounding box to fit into a 32-bit Morton code.

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.

Protected Attributes
BOX2I	m_bbox

std::deque< VERTEX >	m_vertices

VECTOR2I::extended_type	m_simplificationLevel

Private Member Functions
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.

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.

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.

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.

VERTEX *	insertTriVertex (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
size_t	m_vertices_original_size

SHAPE_POLY_SET::TRIANGULATED_POLYGON &	m_result

Detailed Description

Definition at line 75 of file polygon_triangulation.h.

Constructor & Destructor Documentation

◆ POLYGON_TRIANGULATION()

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

inline

Definition at line 78 of file polygon_triangulation.h.

Member Function Documentation

◆ area()

double VERTEX_SET::area	(	const VERTEX *	p,
		const VERTEX *	q,
		const VERTEX *	r
	)		const

protectedinherited

Return the twice the signed area of the triangle formed by vertices p, q, and r.

Returns: the area of the triangle defined by the three vertices

Definition at line 86 of file vertex_set.cpp.

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

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

◆ createList()

VERTEX * VERTEX_SET::createList	(	const SHAPE_LINE_CHAIN &	points,
		VERTEX *	aTail = `nullptr`,
		void *	aUserData = `nullptr`
	)

inherited

Create a list of vertices from a line chain.

Take a SHAPE_LINE_CHAIN and links each point into a circular, doubly-linked list.

Parameters

points	the line chain to create the list from
aTail	the optional vertex to which to append the list
aUserData	user data to associate with the vertices

Returns: the first vertex in the list

Definition at line 9 of file vertex_set.cpp.

References SHAPE_LINE_CHAIN::CPoint(), VERTEX_SET::insertVertex(), VERTEX_SET::m_simplificationLevel, VERTEX::next, SHAPE_LINE_CHAIN::PointCount(), VERTEX::remove(), VECTOR2< T >::SquaredEuclideanNorm(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by POLYGON_TEST::FindPairs(), TesselatePolygon(), and VERTEX_CONNECTOR::VERTEX_CONNECTOR().

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

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

Referenced by splitPolygon(), and TesselatePolygon().

◆ getNextOutlineVertex()

VERTEX * VERTEX_SET::getNextOutlineVertex ( const VERTEX * aPt ) const

protectedinherited

Get the next vertex in the outline, avoiding steiner points and points that overlap with splits.

Parameters

aPt	the current vertex

Returns: the next vertex in the outline

Definition at line 97 of file vertex_set.cpp.

References VERTEX::next, VERTEX::nextZ, VERTEX::prev, VERTEX::prevZ, VERTEX_SET::same_point(), and VERTEX::y.

Referenced by POLYGON_TEST::isSubstantial(), and VERTEX_SET::locallyInside().

◆ getPrevOutlineVertex()

VERTEX * VERTEX_SET::getPrevOutlineVertex ( const VERTEX * aPt ) const

protectedinherited

Get the previous vertex in the outline, avoiding steiner points and points that overlap with splits.

Parameters

aPt	the current vertex

Returns: the previous vertex in the outline

Definition at line 124 of file vertex_set.cpp.

References VERTEX::nextZ, VERTEX::prev, VERTEX::prevZ, VERTEX_SET::same_point(), and VERTEX::y.

Referenced by POLYGON_TEST::isSubstantial(), and VERTEX_SET::locallyInside().

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

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

Referenced by splitPolygon().

◆ insertTriVertex()

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

References SHAPE_POLY_SET::TRIANGULATED_POLYGON::AddVertex(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetVertexCount(), VERTEX_SET::insertVertex(), and m_result.

Referenced by subdividePolygon().

◆ insertVertex()

VERTEX * VERTEX_SET::insertVertex	(	int	aIndex,
		const VECTOR2I &	pt,
		VERTEX *	last,
		void *	aUserData = `nullptr`
	)

inherited

Insert a vertex into the vertex set.

Create an entry in the vertices lookup and optionally inserts the newly created vertex into an existing linked list.

Parameters

aIndex	the index of the vertex
pt	the point to insert
last	the last vertex in the list
aUserData	user data to associate with the vertex

Returns: the newly inserted vertex; a pointer to the newly created vertex.

Definition at line 190 of file vertex_set.cpp.

References VERTEX_SET::m_vertices, VERTEX::next, VERTEX::prev, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by VERTEX_SET::createList(), insertTriVertex(), and VERTEX::split().

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

References VERTEX_SET::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 696 of file polygon_triangulation.h.

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

Referenced by goodSplit().

◆ isTooSmall()

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

inlineprivate

Check whether a given vertex is too small to matter.

Definition at line 451 of file polygon_triangulation.h.

References VERTEX::next, VERTEX::prev, TRIANGULATEMINIMUMAREA, VERTEX::x, and VERTEX::y.

Referenced by earcutList().

◆ locallyInside()

bool VERTEX_SET::locallyInside	(	const VERTEX *	a,
		const VERTEX *	b
	)		const

protectedinherited

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 153 of file vertex_set.cpp.

References VERTEX_SET::area(), VERTEX_SET::getNextOutlineVertex(), and VERTEX_SET::getPrevOutlineVertex().

Referenced by earcutList(), POLYGON_TEST::getKink(), and goodSplit().

◆ logRemaining()

void POLYGON_TRIANGULATION::logRemaining ( )

inlineprivate

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

Definition at line 137 of file polygon_triangulation.h.

References logVertices(), and VERTEX_SET::m_vertices.

Referenced by TesselatePolygon().

◆ logVertices()

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

inlineprivate

Definition at line 150 of file polygon_triangulation.h.

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

Referenced by logRemaining(), and splitPolygon().

◆ middleInside()

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

protectedinherited

Check if the middle of the segment from a to b is inside the polygon.

Parameters

a	the first vertex
b	the second vertex

Returns: true if the point is in the middle of the triangle

Definition at line 165 of file vertex_set.cpp.

References VERTEX::next, VERTEX::x, and 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 651 of file polygon_triangulation.h.

References VERTEX::x, and 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 240 of file polygon_triangulation.h.

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

Referenced by earcutList().

◆ same_point()

bool VERTEX_SET::same_point	(	const VERTEX *	aA,
		const VERTEX *	aB
	)		const

protectedinherited

Check if two vertices are at the same point.

Parameters

aA	the first vertex
aB	the second vertex

Returns: true if the vertices are at the same point

Definition at line 92 of file vertex_set.cpp.

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

Referenced by VERTEX_SET::getNextOutlineVertex(), VERTEX_SET::getPrevOutlineVertex(), and POLYGON_TEST::isSubstantial().

◆ SetBoundingBox()

void VERTEX_SET::SetBoundingBox ( const BOX2I & aBBox )

inherited

Definition at line 3 of file vertex_set.cpp.

References VERTEX_SET::m_bbox.

Referenced by VERTEX_CONNECTOR::VERTEX_CONNECTOR().

◆ sign()

constexpr int POLYGON_TRIANGULATION::sign ( double aVal ) const

inlineconstexprprivate

Definition at line 643 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 185 of file polygon_triangulation.h.

References next(), VERTEX::next, VERTEX::prev, VERTEX::remove(), VECTOR2< T >::SquaredEuclideanNorm(), TRIANGULATE_TRACE, TRIANGULATESIMPLIFICATIONLEVEL, VERTEX::x, and 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 523 of file polygon_triangulation.h.

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

Referenced by earcutList().

◆ subdividePolygon()

void POLYGON_TRIANGULATION::subdividePolygon	(	VERTEX *	aStart,
		int	pass = `0`
	)

inlineprivate

Inserts a new vertex halfway between each existing pair of vertices.

Definition at line 467 of file polygon_triangulation.h.

References insertTriVertex(), VERTEX::next, TRIANGULATE_TRACE, VERTEX::updateList(), VERTEX::x, and VERTEX::y.

Referenced by earcutList().

◆ TesselatePolygon()

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

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

If we have a hint data, we can skip the tesselation process as long as the the hint source did not need to subdivide the polygon.

Definition at line 83 of file polygon_triangulation.h.

References SHAPE_POLY_SET::TRIANGULATED_POLYGON::AddVertex(), VERTEX::area(), SHAPE_LINE_CHAIN::BBox(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::Clear(), SHAPE_LINE_CHAIN::CPoints(), VERTEX_SET::createList(), earcutList(), BOX2< Vec >::GetHeight(), BOX2< Vec >::GetWidth(), logRemaining(), VERTEX_SET::m_bbox, m_result, VERTEX_SET::m_vertices, m_vertices_original_size, VERTEX::next, VERTEX::prev, SHAPE_POLY_SET::TRIANGULATED_POLYGON::SetTriangles(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::Triangles(), TRIANGULATE_TRACE, VERTEX::updateList(), and SHAPE_POLY_SET::TRIANGULATED_POLYGON::Vertices().

Referenced by SHAPE_POLY_SET::cacheTriangulation().

◆ zOrder()

uint32_t VERTEX_SET::zOrder	(	const double	aX,
		const double	aY
	)		const

protectedinherited

Note that while the inputs are doubles, these are scaled by the size of the bounding box to fit into a 32-bit Morton code.

Calculate the Morton code of the VERTEX http://www.graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN.

Returns: the Morton code for the point (aX, aY)

Definition at line 61 of file vertex_set.cpp.

References BOX2< Vec >::GetHeight(), BOX2< Vec >::GetWidth(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), and VERTEX_SET::m_bbox.

Referenced by POLYGON_TEST::getKink(), VERTEX_CONNECTOR::getPoint(), VERTEX::isEar(), and VERTEX::updateOrder().

Member Data Documentation

◆ m_bbox

BOX2I VERTEX_SET::m_bbox

protectedinherited

Definition at line 342 of file vertex_set.h.

Referenced by POLYGON_TEST::FindPairs(), VERTEX_SET::SetBoundingBox(), TesselatePolygon(), and VERTEX_SET::zOrder().

◆ m_result

SHAPE_POLY_SET::TRIANGULATED_POLYGON& POLYGON_TRIANGULATION::m_result

private

Definition at line 727 of file polygon_triangulation.h.

Referenced by earcutList(), insertTriVertex(), and TesselatePolygon().

◆ m_simplificationLevel

VECTOR2I::extended_type VERTEX_SET::m_simplificationLevel

protectedinherited

Definition at line 344 of file vertex_set.h.

Referenced by VERTEX_SET::createList(), and VERTEX_SET::VERTEX_SET().

◆ m_vertices

std::deque<VERTEX> VERTEX_SET::m_vertices

protectedinherited

Definition at line 343 of file vertex_set.h.

Referenced by POLYGON_TEST::FindPairs(), VERTEX_CONNECTOR::FindResults(), VERTEX_SET::insertVertex(), intersectsPolygon(), POLYGON_TEST::isSubstantial(), logRemaining(), VERTEX::split(), and TesselatePolygon().

◆ m_vertices_original_size

size_t POLYGON_TRIANGULATION::m_vertices_original_size

private

Definition at line 726 of file polygon_triangulation.h.

Referenced by intersectsPolygon(), and TesselatePolygon().

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

polygon_triangulation.h

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ POLYGON_TRIANGULATION()

Member Function Documentation

◆ area()

◆ createList()

◆ earcutList()

◆ getNextOutlineVertex()

◆ getPrevOutlineVertex()

◆ goodSplit()

◆ insertTriVertex()

◆ insertVertex()

◆ intersects()

◆ intersectsPolygon()

◆ isTooSmall()

◆ locallyInside()

◆ logRemaining()

◆ logVertices()

◆ middleInside()

◆ overlapping()

◆ removeNullTriangles()

◆ same_point()

◆ SetBoundingBox()

◆ sign()

◆ simplifyList()

◆ splitPolygon()

◆ subdividePolygon()

◆ TesselatePolygon()

◆ zOrder()

Member Data Documentation

◆ m_bbox

◆ m_result

◆ m_simplificationLevel

◆ m_vertices

◆ m_vertices_original_size