#include <polygon_triangulation.h>

Inheritance diagram for POLYGON_TRIANGULATION:

Classes
struct	SCANLINE_HIT

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

bool	TesselatePolygon (const SHAPE_POLY_SET::POLYGON &aPolygon, SHAPE_POLY_SET::TRIANGULATED_POLYGON *aHintData)
	Triangulate a polygon with holes by bridging holes directly into the outer ring's VERTEX linked list, avoiding the Fracture() intermediate step.

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

std::vector< double >	PartitionAreaFractionsForTesting (const SHAPE_LINE_CHAIN &aPoly, size_t aTargetLeaves) const

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
bool	collectScanlineHits (const SHAPE_LINE_CHAIN &aPoly, bool aVertical, int aCut, std::array< SCANLINE_HIT, 2 > &aHits) const

SHAPE_LINE_CHAIN	createSplitChild (const SHAPE_LINE_CHAIN &aPoly, int aStart, int aEnd) const

bool	splitPolygonAtCoordinate (const SHAPE_LINE_CHAIN &aPoly, bool aVertical, int aCut, std::array< SHAPE_LINE_CHAIN, 2 > &aChildren, double &aAreaA, double &aAreaB) const

bool	splitPolygonBalanced (const SHAPE_LINE_CHAIN &aPoly, std::array< SHAPE_LINE_CHAIN, 2 > &aChildren) const

std::vector< SHAPE_LINE_CHAIN >	partitionPolygonBalanced (const SHAPE_LINE_CHAIN &aPoly, size_t aTargetLeaves) const

size_t	suggestedPartitionLeafCount (const SHAPE_LINE_CHAIN &aPoly) const

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.

double	earScore (const VERTEX a, const VERTEX b, const VERTEX *c) const

VERTEX *	createRing (const SHAPE_LINE_CHAIN &aPoints, int aBaseIndex, bool aWantCCW)
	Create a VERTEX linked list from a SHAPE_LINE_CHAIN with a global index offset.

VERTEX *	eliminateHoles (VERTEX aOuterRing, std::vector< VERTEX > &aHoleRings)
	Bridge all hole rings into the outer ring by sorting holes left-to-right and connecting each hole's leftmost vertex to the nearest visible point on the outer boundary via VERTEX::split().

void	filterPoints (VERTEX aStart, VERTEX aEnd=nullptr)
	Remove consecutive duplicate vertices from the linked list.

VERTEX *	findHoleBridge (VERTEX aHole, VERTEX aOuterStart)
	Find a vertex on the outer ring visible from the hole's leftmost vertex by casting a horizontal ray to the left.

bool	sectorContainsSector (const VERTEX m, const VERTEX p) const
	Whether sector in vertex m contains sector in vertex p in the same coordinate frame.

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.

Static Private Member Functions
static double	triArea (double ax, double ay, double bx, double by, double cx, double cy)
	Signed area of triangle (ax,ay), (bx,by), (cx,cy).

Private Attributes
size_t	m_vertices_original_size

SHAPE_POLY_SET::TRIANGULATED_POLYGON &	m_result

Friends
struct	POLYGON_TRIANGULATION_TEST_ACCESS

class	SHAPE_POLY_SET

Detailed Description

Definition at line 76 of file polygon_triangulation.h.

Constructor & Destructor Documentation

◆ POLYGON_TRIANGULATION()

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

inline

Definition at line 79 of file polygon_triangulation.h.

References m_result, m_vertices_original_size, TRIANGULATESIMPLIFICATIONLEVEL, and VERTEX_SET::VERTEX_SET().

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

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

Referenced by POLYGON_TRIANGULATION::earcutList(), POLYGON_TRIANGULATION::earScore(), POLYGON_TRIANGULATION::goodSplit(), POLYGON_TRIANGULATION::intersects(), locallyInside(), POLYGON_TRIANGULATION::partitionPolygonBalanced(), POLYGON_TRIANGULATION::removeNullTriangles(), POLYGON_TRIANGULATION::sectorContainsSector(), and POLYGON_TRIANGULATION::splitPolygon().

◆ collectScanlineHits()

bool POLYGON_TRIANGULATION::collectScanlineHits	(	const SHAPE_LINE_CHAIN &	aPoly,
		bool	aVertical,
		int	aCut,
		std::array< SCANLINE_HIT, 2 > &	aHits ) const

inlineprivate

Definition at line 245 of file polygon_triangulation.h.

References SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::PointCount(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by splitPolygonAtCoordinate().

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

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

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

◆ createRing()

VERTEX * POLYGON_TRIANGULATION::createRing	(	const SHAPE_LINE_CHAIN &	aPoints,
		int	aBaseIndex,
		bool	aWantCCW )

inlineprivate

Create a VERTEX linked list from a SHAPE_LINE_CHAIN with a global index offset.

The winding direction is controlled by aWantCCW.

Definition at line 797 of file polygon_triangulation.h.

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

Referenced by TesselatePolygon().

◆ createSplitChild()

SHAPE_LINE_CHAIN POLYGON_TRIANGULATION::createSplitChild	(	const SHAPE_LINE_CHAIN &	aPoly,
		int	aStart,
		int	aEnd ) const

inlineprivate

Definition at line 284 of file polygon_triangulation.h.

References SHAPE_LINE_CHAIN::Append(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_LINE_CHAIN::PointCount(), SHAPE_LINE_CHAIN::SetClosed(), and SHAPE_LINE_CHAIN::Simplify2().

Referenced by splitPolygonAtCoordinate().

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

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

Referenced by splitPolygon(), TesselatePolygon(), and TesselatePolygon().

◆ earScore()

double POLYGON_TRIANGULATION::earScore	(	const VERTEX *	a,
		const VERTEX *	b,
		const VERTEX *	c ) const

inlineprivate

Definition at line 780 of file polygon_triangulation.h.

References std::abs(), VERTEX_SET::area(), VERTEX_SET::VERTEX, VERTEX::x, and VERTEX::y.

Referenced by earcutList().

◆ eliminateHoles()

VERTEX * POLYGON_TRIANGULATION::eliminateHoles	(	VERTEX *	aOuterRing,
		std::vector< VERTEX * > &	aHoleRings )

inlineprivate

Bridge all hole rings into the outer ring by sorting holes left-to-right and connecting each hole's leftmost vertex to the nearest visible point on the outer boundary via VERTEX::split().

Definition at line 848 of file polygon_triangulation.h.

References filterPoints(), findHoleBridge(), VERTEX::next, VERTEX::split(), TRIANGULATE_TRACE, VERTEX_SET::VERTEX, VERTEX::x, and VERTEX::y.

Referenced by TesselatePolygon().

◆ filterPoints()

void POLYGON_TRIANGULATION::filterPoints	(	VERTEX *	aStart,
		VERTEX *	aEnd = nullptr )

inlineprivate

Remove consecutive duplicate vertices from the linked list.

Definition at line 901 of file polygon_triangulation.h.

References VERTEX::next, VERTEX::prev, VERTEX::remove(), and VERTEX_SET::VERTEX.

Referenced by eliminateHoles().

◆ findHoleBridge()

VERTEX * POLYGON_TRIANGULATION::findHoleBridge	(	VERTEX *	aHole,
		VERTEX *	aOuterStart )

inlineprivate

Find a vertex on the outer ring visible from the hole's leftmost vertex by casting a horizontal ray to the left.

Definition at line 937 of file polygon_triangulation.h.

References std::abs(), VERTEX_SET::locallyInside(), VERTEX::next, sectorContainsSector(), triArea(), VERTEX_SET::VERTEX, VERTEX::x, and VERTEX::y.

Referenced by eliminateHoles().

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

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

Referenced by POLYGON_TEST::isSubstantial(), and 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 144 of file vertex_set.cpp.

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

Referenced by POLYGON_TEST::isSubstantial(), and 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 1210 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, VERTEX::prevZ, and VERTEX_SET::VERTEX.

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

References VERTEX_SET::insertVertex(), m_result, and VERTEX_SET::VERTEX.

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

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

Referenced by createList(), POLYGON_TRIANGULATION::createRing(), and POLYGON_TRIANGULATION::insertTriVertex().

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

References VERTEX_SET::area(), overlapping(), sign(), and VERTEX_SET::VERTEX.

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

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

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

References VERTEX::next, VERTEX::prev, TRIANGULATEMINIMUMAREA, VERTEX_SET::VERTEX, 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 173 of file vertex_set.cpp.

References area(), getNextOutlineVertex(), getPrevOutlineVertex(), and VERTEX.

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

◆ logRemaining()

void POLYGON_TRIANGULATION::logRemaining ( )

inlineprivate

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

Definition at line 443 of file polygon_triangulation.h.

References logVertices(), VERTEX_SET::m_vertices, and VERTEX_SET::VERTEX.

Referenced by TesselatePolygon(), and TesselatePolygon().

◆ logVertices()

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

inlineprivate

Definition at line 456 of file polygon_triangulation.h.

References VERTEX::next, TRIANGULATE_TRACE, VERTEX_SET::VERTEX, 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 185 of file vertex_set.cpp.

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

Referenced by POLYGON_TRIANGULATION::goodSplit().

◆ overlapping()

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

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

Referenced by intersects().

◆ PartitionAreaFractionsForTesting()

std::vector< double > POLYGON_TRIANGULATION::PartitionAreaFractionsForTesting	(	const SHAPE_LINE_CHAIN &	aPoly,
		size_t	aTargetLeaves ) const

inline

Definition at line 218 of file polygon_triangulation.h.

References std::abs(), SHAPE_LINE_CHAIN::Area(), partitionPolygonBalanced(), and totalArea.

Referenced by POLYGON_TRIANGULATION_TEST_ACCESS::PartitionAreaFractions().

◆ partitionPolygonBalanced()

std::vector< SHAPE_LINE_CHAIN > POLYGON_TRIANGULATION::partitionPolygonBalanced	(	const SHAPE_LINE_CHAIN &	aPoly,
		size_t	aTargetLeaves ) const

inlineprivate

Definition at line 386 of file polygon_triangulation.h.

References std::abs(), VERTEX_SET::area(), and splitPolygonBalanced().

Referenced by SHAPE_POLY_SET::cacheTriangulation(), and PartitionAreaFractionsForTesting().

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

References std::abs(), VERTEX_SET::area(), VERTEX::next, VERTEX::prev, VERTEX::remove(), simplifyList(), TRIANGULATE_TRACE, VERTEX_SET::VERTEX, 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 112 of file vertex_set.cpp.

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

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

◆ sectorContainsSector()

bool POLYGON_TRIANGULATION::sectorContainsSector	(	const VERTEX *	m,
		const VERTEX *	p ) const

inlineprivate

Whether sector in vertex m contains sector in vertex p in the same coordinate frame.

Definition at line 1037 of file polygon_triangulation.h.

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

Referenced by findHoleBridge().

◆ SetBoundingBox()

void VERTEX_SET::SetBoundingBox ( const BOX2I & aBBox )

inherited

Definition at line 21 of file vertex_set.cpp.

References m_bbox.

Referenced by VERTEX_CONNECTOR::VERTEX_CONNECTOR().

◆ sign()

int POLYGON_TRIANGULATION::sign ( double aVal ) const

inlineconstexprprivate

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

References next(), VERTEX::next, VERTEX::prev, VERTEX::remove(), VECTOR2< T >::SquaredEuclideanNorm(), TRIANGULATE_TRACE, TRIANGULATESIMPLIFICATIONLEVEL, VERTEX_SET::VERTEX, VERTEX::x, and VERTEX::y.

Referenced by removeNullTriangles(), TesselatePolygon(), and TesselatePolygon().

◆ 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 1105 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, VERTEX::updateList(), and VERTEX_SET::VERTEX.

Referenced by earcutList().

◆ splitPolygonAtCoordinate()

bool POLYGON_TRIANGULATION::splitPolygonAtCoordinate	(	const SHAPE_LINE_CHAIN &	aPoly,
		bool	aVertical,
		int	aCut,
		std::array< SHAPE_LINE_CHAIN, 2 > &	aChildren,
		double &	aAreaA,
		double &	aAreaB ) const

inlineprivate

Definition at line 303 of file polygon_triangulation.h.

References std::abs(), collectScanlineHits(), createSplitChild(), SHAPE_LINE_CHAIN::Find(), and SHAPE_LINE_CHAIN::Split().

Referenced by splitPolygonBalanced().

◆ splitPolygonBalanced()

bool POLYGON_TRIANGULATION::splitPolygonBalanced	(	const SHAPE_LINE_CHAIN &	aPoly,
		std::array< SHAPE_LINE_CHAIN, 2 > &	aChildren ) const

inlineprivate

Definition at line 333 of file polygon_triangulation.h.

References std::abs(), SHAPE_LINE_CHAIN::Area(), SHAPE_LINE_CHAIN::BBox(), cut, BOX2< Vec >::GetBottom(), BOX2< Vec >::GetHeight(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetWidth(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), splitPolygonAtCoordinate(), and totalArea.

Referenced by partitionPolygonBalanced().

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

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

Referenced by earcutList().

◆ suggestedPartitionLeafCount()

size_t POLYGON_TRIANGULATION::suggestedPartitionLeafCount ( const SHAPE_LINE_CHAIN & aPoly ) const

inlineprivate

Definition at line 425 of file polygon_triangulation.h.

References SHAPE_LINE_CHAIN::PointCount().

Referenced by SHAPE_POLY_SET::cacheTriangulation().

◆ TesselatePolygon() [1/2]

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 hint data, we can skip the tesselation process as long as the hint source did not need to subdivide the polygon. Hint triangle indices refer to the original vertex list stored in m_result, not the simplified working ring used internally during triangulation.

Definition at line 163 of file polygon_triangulation.h.

References VERTEX::area(), SHAPE_LINE_CHAIN::BBox(), SHAPE_LINE_CHAIN::CPoints(), VERTEX_SET::createList(), earcutList(), logRemaining(), VERTEX_SET::m_bbox, m_result, VERTEX_SET::m_vertices, m_vertices_original_size, VERTEX::next, VERTEX::prev, simplifyList(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::Triangles(), TRIANGULATE_TRACE, VERTEX::updateList(), VERTEX_SET::VERTEX, and SHAPE_POLY_SET::TRIANGULATED_POLYGON::Vertices().

◆ TesselatePolygon() [2/2]

bool POLYGON_TRIANGULATION::TesselatePolygon	(	const SHAPE_POLY_SET::POLYGON &	aPolygon,
		SHAPE_POLY_SET::TRIANGULATED_POLYGON *	aHintData )

inline

Triangulate a polygon with holes by bridging holes directly into the outer ring's VERTEX linked list, avoiding the Fracture() intermediate step.

Definition at line 88 of file polygon_triangulation.h.

References SHAPE_LINE_CHAIN::BBox(), chain, createRing(), earcutList(), eliminateHoles(), logRemaining(), VERTEX_SET::m_bbox, m_result, VERTEX_SET::m_vertices, m_vertices_original_size, VERTEX::next, SHAPE_LINE_CHAIN::PointCount(), VERTEX::prev, simplifyList(), TesselatePolygon(), TRIANGULATE_TRACE, VERTEX::updateList(), and VERTEX_SET::VERTEX.

Referenced by BOOST_AUTO_TEST_CASE(), SHAPE_POLY_SET::cacheTriangulation(), and TesselatePolygon().

◆ triArea()

static double POLYGON_TRIANGULATION::triArea	(	double	ax,
		double	ay,
		double	bx,
		double	by,
		double	cx,
		double	cy )

inlinestaticprivate

Signed area of triangle (ax,ay), (bx,by), (cx,cy).

Definition at line 1027 of file polygon_triangulation.h.

Referenced by findHoleBridge().

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

References m_bbox.

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

Friends And Related Symbol Documentation

◆ POLYGON_TRIANGULATION_TEST_ACCESS

friend struct POLYGON_TRIANGULATION_TEST_ACCESS

friend

Definition at line 236 of file polygon_triangulation.h.

References POLYGON_TRIANGULATION_TEST_ACCESS.

Referenced by POLYGON_TRIANGULATION_TEST_ACCESS.

◆ SHAPE_POLY_SET

friend class SHAPE_POLY_SET

friend

Definition at line 237 of file polygon_triangulation.h.

References SHAPE_POLY_SET.

Referenced by SHAPE_POLY_SET.

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(), SetBoundingBox(), POLYGON_TRIANGULATION::TesselatePolygon(), POLYGON_TRIANGULATION::TesselatePolygon(), and zOrder().

◆ m_result

SHAPE_POLY_SET::TRIANGULATED_POLYGON& POLYGON_TRIANGULATION::m_result

private

Definition at line 1309 of file polygon_triangulation.h.

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

◆ m_simplificationLevel

VECTOR2I::extended_type VERTEX_SET::m_simplificationLevel

protectedinherited

Definition at line 344 of file vertex_set.h.

Referenced by createList(), POLYGON_TRIANGULATION::createRing(), and 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(), insertVertex(), POLYGON_TRIANGULATION::intersectsPolygon(), POLYGON_TEST::isSubstantial(), POLYGON_TRIANGULATION::logRemaining(), POLYGON_TRIANGULATION::TesselatePolygon(), and POLYGON_TRIANGULATION::TesselatePolygon().

◆ m_vertices_original_size

size_t POLYGON_TRIANGULATION::m_vertices_original_size

private

Definition at line 1308 of file polygon_triangulation.h.

Referenced by intersectsPolygon(), POLYGON_TRIANGULATION(), TesselatePolygon(), and TesselatePolygon().

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

polygon_triangulation.h

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ POLYGON_TRIANGULATION()

Member Function Documentation

◆ area()

◆ collectScanlineHits()

◆ createList()

◆ createRing()

◆ createSplitChild()

◆ earcutList()

◆ earScore()

◆ eliminateHoles()

◆ filterPoints()

◆ findHoleBridge()

◆ getNextOutlineVertex()

◆ getPrevOutlineVertex()

◆ goodSplit()

◆ insertTriVertex()

◆ insertVertex()

◆ intersects()

◆ intersectsPolygon()

◆ isTooSmall()

◆ locallyInside()

◆ logRemaining()

◆ logVertices()

◆ middleInside()

◆ overlapping()

◆ PartitionAreaFractionsForTesting()

◆ partitionPolygonBalanced()

◆ removeNullTriangles()

◆ same_point()

◆ sectorContainsSector()

◆ SetBoundingBox()

◆ sign()

◆ simplifyList()

◆ splitPolygon()

◆ splitPolygonAtCoordinate()

◆ splitPolygonBalanced()

◆ subdividePolygon()

◆ suggestedPartitionLeafCount()

◆ TesselatePolygon() [1/2]

◆ TesselatePolygon() [2/2]

◆ triArea()

◆ zOrder()

Friends And Related Symbol Documentation

◆ POLYGON_TRIANGULATION_TEST_ACCESS

◆ SHAPE_POLY_SET

Member Data Documentation

◆ m_bbox

◆ m_result

◆ m_simplificationLevel

◆ m_vertices

◆ m_vertices_original_size