KiCad PCB EDA Suite
PolygonTriangulation::Vertex Struct Reference

Public Member Functions

 Vertex (size_t aIndex, double aX, double aY, PolygonTriangulation *aParent)
 
Vertexoperator= (const Vertex &)=delete
 
Vertexoperator= (Vertex &&)=delete
 
bool operator== (const Vertex &rhs) const
 
bool operator!= (const Vertex &rhs) const
 
Vertexsplit (Vertex *b)
 Split the referenced polygon between the reference point and vertex b, assuming they are in the same polygon. More...
 
void remove ()
 Remove the node from the linked list and z-ordered linked list. More...
 
void updateOrder ()
 
void updateList ()
 After inserting or changing nodes, this function should be called to remove duplicate vertices and ensure z-ordering is correct. More...
 
void zSort ()
 Sort all vertices in this vertex's list by their Morton code. More...
 
bool inTriangle (const Vertex &a, const Vertex &b, const Vertex &c)
 Check to see if triangle surrounds our current vertex. More...
 

Public Attributes

const size_t i
 
const double x
 
const double y
 
PolygonTriangulationparent
 
Vertexprev = nullptr
 
Vertexnext = nullptr
 
int32_t z = 0
 
VertexprevZ = nullptr
 
VertexnextZ = nullptr
 

Detailed Description

Definition at line 89 of file polygon_triangulation.h.

Constructor & Destructor Documentation

◆ Vertex()

PolygonTriangulation::Vertex::Vertex ( size_t  aIndex,
double  aX,
double  aY,
PolygonTriangulation aParent 
)
inline

Definition at line 91 of file polygon_triangulation.h.

91 :
92 i( aIndex ),
93 x( aX ),
94 y( aY ),
95 parent( aParent )
96 {
97 }

Member Function Documentation

◆ inTriangle()

bool PolygonTriangulation::Vertex::inTriangle ( const Vertex a,
const Vertex b,
const Vertex c 
)
inline

Check to see if triangle surrounds our current vertex.

Definition at line 234 of file polygon_triangulation.h.

235 {
236 return ( c.x - x ) * ( a.y - y ) - ( a.x - x ) * ( c.y - y ) >= 0
237 && ( a.x - x ) * ( b.y - y ) - ( b.x - x ) * ( a.y - y ) >= 0
238 && ( b.x - x ) * ( c.y - y ) - ( c.x - x ) * ( b.y - y ) >= 0;
239 }

References x, and y.

Referenced by PolygonTriangulation::isEar().

◆ operator!=()

bool PolygonTriangulation::Vertex::operator!= ( const Vertex rhs) const
inline

Definition at line 106 of file polygon_triangulation.h.

106{ return !( *this == rhs ); }

◆ operator=() [1/2]

Vertex & PolygonTriangulation::Vertex::operator= ( const Vertex )
delete

◆ operator=() [2/2]

Vertex & PolygonTriangulation::Vertex::operator= ( Vertex &&  )
delete

◆ operator==()

bool PolygonTriangulation::Vertex::operator== ( const Vertex rhs) const
inline

Definition at line 102 of file polygon_triangulation.h.

103 {
104 return this->x == rhs.x && this->y == rhs.y;
105 }

References x, and y.

◆ remove()

void PolygonTriangulation::Vertex::remove ( )
inline

Remove the node from the linked list and z-ordered linked list.

Definition at line 146 of file polygon_triangulation.h.

147 {
148 next->prev = prev;
149 prev->next = next;
150
151 if( prevZ )
152 prevZ->nextZ = nextZ;
153
154 if( nextZ )
155 nextZ->prevZ = prevZ;
156
157 next = nullptr;
158 prev = nullptr;
159 nextZ = nullptr;
160 prevZ = nullptr;
161 }

References next, nextZ, prev, and prevZ.

Referenced by PolygonTriangulation::createList(), PolygonTriangulation::earcutList(), PolygonTriangulation::removeNullTriangles(), and updateList().

◆ split()

Vertex * PolygonTriangulation::Vertex::split ( Vertex b)
inline

Split the referenced polygon between the reference point and vertex b, assuming they are in the same polygon.

Notes that while we create a new vertex pointer for the linked list, we maintain the same vertex index value from the original polygon. In this way, we have two polygons that both share the same vertices.

Returns
the newly created vertex in the polygon that does not include the reference vertex.

Definition at line 119 of file polygon_triangulation.h.

120 {
121 parent->m_vertices.emplace_back( i, x, y, parent );
122 Vertex* a2 = &parent->m_vertices.back();
123 parent->m_vertices.emplace_back( b->i, b->x, b->y, parent );
124 Vertex* b2 = &parent->m_vertices.back();
125 Vertex* an = next;
126 Vertex* bp = b->prev;
127
128 next = b;
129 b->prev = this;
130
131 a2->next = an;
132 an->prev = a2;
133
134 b2->next = a2;
135 a2->prev = b2;
136
137 bp->next = b2;
138 b2->prev = bp;
139
140 return b2;
141 }
std::deque< Vertex > m_vertices
Vertex(size_t aIndex, double aX, double aY, PolygonTriangulation *aParent)

References i, PolygonTriangulation::m_vertices, next, parent, prev, x, and y.

Referenced by PolygonTriangulation::splitPolygon().

◆ updateList()

void PolygonTriangulation::Vertex::updateList ( )
inline

After inserting or changing nodes, this function should be called to remove duplicate vertices and ensure z-ordering is correct.

Remove duplicates

Definition at line 173 of file polygon_triangulation.h.

174 {
175 Vertex* p = next;
176
177 while( p != this )
178 {
182 if( *p == *p->next )
183 {
184 p = p->prev;
185 p->next->remove();
186
187 if( p == p->next )
188 break;
189 }
190
191 p->updateOrder();
192 p = p->next;
193 };
194
195 updateOrder();
196 zSort();
197 }
void zSort()
Sort all vertices in this vertex's list by their Morton code.
void remove()
Remove the node from the linked list and z-ordered linked list.

References next, prev, remove(), updateOrder(), and zSort().

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

◆ updateOrder()

void PolygonTriangulation::Vertex::updateOrder ( )
inline

Definition at line 163 of file polygon_triangulation.h.

164 {
165 if( !z )
166 z = parent->zOrder( x, y );
167 }
int32_t zOrder(const double aX, const double aY) const
Calculate the Morton code of the Vertex http://www.graphics.stanford.edu/~seander/bithacks....

References parent, x, y, z, and PolygonTriangulation::zOrder().

Referenced by updateList().

◆ zSort()

void PolygonTriangulation::Vertex::zSort ( )
inline

Sort all vertices in this vertex's list by their Morton code.

Definition at line 202 of file polygon_triangulation.h.

203 {
204 std::deque<Vertex*> queue;
205
206 queue.push_back( this );
207
208 for( auto p = next; p && p != this; p = p->next )
209 queue.push_back( p );
210
211 std::sort( queue.begin(), queue.end(), []( const Vertex* a, const Vertex* b )
212 {
213 return a->z < b->z;
214 } );
215
216 Vertex* prev_elem = nullptr;
217
218 for( auto elem : queue )
219 {
220 if( prev_elem )
221 prev_elem->nextZ = elem;
222
223 elem->prevZ = prev_elem;
224 prev_elem = elem;
225 }
226
227 prev_elem->nextZ = nullptr;
228 }

References next, nextZ, and prevZ.

Referenced by updateList().

Member Data Documentation

◆ i

◆ next

◆ nextZ

Vertex* PolygonTriangulation::Vertex::nextZ = nullptr

Definition at line 255 of file polygon_triangulation.h.

Referenced by PolygonTriangulation::isEar(), remove(), and zSort().

◆ parent

PolygonTriangulation* PolygonTriangulation::Vertex::parent

Definition at line 244 of file polygon_triangulation.h.

Referenced by split(), and updateOrder().

◆ prev

◆ prevZ

Vertex* PolygonTriangulation::Vertex::prevZ = nullptr

Definition at line 254 of file polygon_triangulation.h.

Referenced by PolygonTriangulation::isEar(), remove(), and zSort().

◆ x

const double PolygonTriangulation::Vertex::x

◆ y

const double PolygonTriangulation::Vertex::y

◆ z

int32_t PolygonTriangulation::Vertex::z = 0

Definition at line 251 of file polygon_triangulation.h.

Referenced by PolygonTriangulation::isEar(), and updateOrder().


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