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  }
Vertex(size_t aIndex, double aX, double aY, PolygonTriangulation *aParent)
std::deque< Vertex > m_vertices

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 remove()
Remove the node from the linked list and z-ordered linked list.
void zSort()
Sort all vertices in this vertex's list by their Morton code.
Vertex(size_t aIndex, double aX, double aY, PolygonTriangulation *aParent)

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  }
Vertex(size_t aIndex, double aX, double aY, PolygonTriangulation *aParent)

References next, nextZ, prevZ, and z.

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(), updateOrder(), and zSort().


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