#include <vertex_set.h>

Inheritance diagram for VERTEX_SET:

Public Member Functions
	VERTEX_SET (int aSimplificationLevel)

	~VERTEX_SET ()

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

Friends
class	VERTEX

Detailed Description

Definition at line 253 of file vertex_set.h.

Constructor & Destructor Documentation

◆ VERTEX_SET()

VERTEX_SET::VERTEX_SET ( int aSimplificationLevel )

inline

Definition at line 258 of file vertex_set.h.

References m_simplificationLevel.

◆ ~VERTEX_SET()

VERTEX_SET::~VERTEX_SET ( )

inline

Definition at line 262 of file vertex_set.h.

Member Function Documentation

◆ area()

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

protected

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 POLYGON_TRIANGULATION::earcutList(), POLYGON_TRIANGULATION::goodSplit(), POLYGON_TRIANGULATION::intersects(), VERTEX::isEar(), locallyInside(), POLYGON_TRIANGULATION::removeNullTriangles(), and POLYGON_TRIANGULATION::splitPolygon().

◆ createList()

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

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

◆ getNextOutlineVertex()

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

protected

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, same_point(), and VERTEX::y.

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

◆ getPrevOutlineVertex()

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

protected

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, same_point(), and VERTEX::y.

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

◆ insertVertex()

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

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 m_vertices, VERTEX::next, VERTEX::prev, VECTOR2< T >::x, and VECTOR2< T >::y.

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

◆ locallyInside()

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

protected

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 area(), getNextOutlineVertex(), and getPrevOutlineVertex().

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

◆ middleInside()

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

protected

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 POLYGON_TRIANGULATION::goodSplit().

◆ same_point()

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

protected

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 getNextOutlineVertex(), getPrevOutlineVertex(), and POLYGON_TEST::isSubstantial().

◆ SetBoundingBox()

void VERTEX_SET::SetBoundingBox ( const BOX2I & aBBox )

Definition at line 3 of file vertex_set.cpp.

References m_bbox.

Referenced by VERTEX_CONNECTOR::VERTEX_CONNECTOR().

◆ zOrder()

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

protected

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

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

Friends And Related Function Documentation

◆ VERTEX

friend class VERTEX

friend

Definition at line 255 of file vertex_set.h.

Member Data Documentation

◆ m_bbox

BOX2I VERTEX_SET::m_bbox

protected

Definition at line 342 of file vertex_set.h.

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

◆ m_simplificationLevel

VECTOR2I::extended_type VERTEX_SET::m_simplificationLevel

protected

Definition at line 344 of file vertex_set.h.

Referenced by createList(), and VERTEX_SET().

◆ m_vertices

std::deque<VERTEX> VERTEX_SET::m_vertices

protected

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

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

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ VERTEX_SET()

◆ ~VERTEX_SET()

Member Function Documentation

◆ area()

◆ createList()

◆ getNextOutlineVertex()

◆ getPrevOutlineVertex()

◆ insertVertex()

◆ locallyInside()

◆ middleInside()

◆ same_point()

◆ SetBoundingBox()

◆ zOrder()

Friends And Related Function Documentation

◆ VERTEX

Member Data Documentation

◆ m_bbox

◆ m_simplificationLevel

◆ m_vertices