KiCad PCB EDA Suite
Loading...
Searching...
No Matches
VERTEX_SET Class Reference

#include <vertex_set.h>

Inheritance diagram for VERTEX_SET:
POLYGON_TEST POLYGON_TRIANGULATION VERTEX_CONNECTOR

Public Member Functions

 VERTEX_SET (int aSimplificationLevel)
 
 ~VERTEX_SET ()
 
void SetBoundingBox (const BOX2I &aBBox)
 
VERTEXinsertVertex (int aIndex, const VECTOR2I &pt, VERTEX *last, void *aUserData=nullptr)
 Insert a vertex into the vertex set.
 
VERTEXcreateList (const SHAPE_LINE_CHAIN &points, VERTEX *aTail=nullptr, void *aUserData=nullptr)
 Create a list of vertices from a line chain.
 

Protected Member Functions

VERTEXgetNextOutlineVertex (const VERTEX *aPt) const
 Get the next vertex in the outline, avoiding steiner points and points that overlap with splits.
 
VERTEXgetPrevOutlineVertex (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.
 
int32_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< VERTEXm_vertices
 
VECTOR2I::extended_type m_simplificationLevel
 

Friends

class VERTEX
 

Detailed Description

Definition at line 249 of file vertex_set.h.

Constructor & Destructor Documentation

◆ VERTEX_SET()

VERTEX_SET::VERTEX_SET ( int  aSimplificationLevel)
inline

Definition at line 254 of file vertex_set.h.

References m_simplificationLevel.

◆ ~VERTEX_SET()

VERTEX_SET::~VERTEX_SET ( )
inline

Definition at line 258 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 83 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
pointsthe line chain to create the list from
aTailthe optional vertex to which to append the list
aUserDatauser 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
aPtthe current vertex
Returns
the next vertex in the outline

Definition at line 94 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
aPtthe current vertex
Returns
the previous vertex in the outline

Definition at line 121 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
aIndexthe index of the vertex
ptthe point to insert
lastthe last vertex in the list
aUserDatauser data to associate with the vertex
Returns
the newly inserted vertex
a pointer to the newly created vertex.

Definition at line 187 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 150 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
athe first vertex
bthe second vertex
Returns
true if the point is in the middle of the triangle

Definition at line 162 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
aAthe first vertex
aBthe second vertex
Returns
true if the vertices are at the same point

Definition at line 89 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()

int32_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 251 of file vertex_set.h.

Member Data Documentation

◆ m_bbox

BOX2I VERTEX_SET::m_bbox
protected

◆ m_simplificationLevel

VECTOR2I::extended_type VERTEX_SET::m_simplificationLevel
protected

Definition at line 340 of file vertex_set.h.

Referenced by createList(), and VERTEX_SET().

◆ m_vertices


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