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)
 Function split Splits the referenced polygon between the reference point and vertex b, assuming they are in the same polygon. More...
 
void remove ()
 Function remove Removes the node from the linked list and z-ordered linked list. More...
 
void updateOrder ()
 
void updateList ()
 Function 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 66 of file polygon_triangulation.h.

Constructor & Destructor Documentation

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

Definition at line 68 of file polygon_triangulation.h.

References operator=().

68  :
69  i( aIndex ), x( aX ), y( aY ), parent( aParent )
70  {
71  }

Member Function Documentation

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

References x, and y.

Referenced by PolygonTriangulation::isEar().

209  {
210  return ( c.x - x ) * ( a.y - y ) - ( a.x - x ) * ( c.y - y ) >= 0
211  && ( a.x - x ) * ( b.y - y ) - ( b.x - x ) * ( a.y - y ) >= 0
212  && ( b.x - x ) * ( c.y - y ) - ( c.x - x ) * ( b.y - y ) >= 0;
213  }
bool PolygonTriangulation::Vertex::operator!= ( const Vertex rhs) const
inline

Definition at line 79 of file polygon_triangulation.h.

79 { return !( *this == rhs ); }
Vertex& PolygonTriangulation::Vertex::operator= ( const Vertex )
delete

Referenced by Vertex().

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

Definition at line 75 of file polygon_triangulation.h.

References x, and y.

76  {
77  return this->x == rhs.x && this->y == rhs.y;
78  }
void PolygonTriangulation::Vertex::remove ( )
inline

Function remove Removes the node from the linked list and z-ordered linked list.

Definition at line 121 of file polygon_triangulation.h.

References next, nextZ, prev, and prevZ.

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

122  {
123  next->prev = prev;
124  prev->next = next;
125 
126  if( prevZ )
127  prevZ->nextZ = nextZ;
128  if( nextZ )
129  nextZ->prevZ = prevZ;
130  next = NULL;
131  prev = NULL;
132  nextZ = NULL;
133  prevZ = NULL;
134  }
Vertex* PolygonTriangulation::Vertex::split ( Vertex b)
inline

Function split Splits 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 pointer to the newly created vertex in the polygon that does not include the reference vertex.

Definition at line 93 of file polygon_triangulation.h.

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

Referenced by PolygonTriangulation::splitPolygon().

94  {
95  parent->m_vertices.emplace_back( i, x, y, parent );
96  Vertex* a2 = &parent->m_vertices.back();
97  parent->m_vertices.emplace_back( b->i, b->x, b->y, parent );
98  Vertex* b2 = &parent->m_vertices.back();
99  Vertex* an = next;
100  Vertex* bp = b->prev;
101 
102  next = b;
103  b->prev = this;
104 
105  a2->next = an;
106  an->prev = a2;
107 
108  b2->next = a2;
109  a2->prev = b2;
110 
111  bp->next = b2;
112  b2->prev = bp;
113 
114  return b2;
115  }
Vertex(size_t aIndex, double aX, double aY, PolygonTriangulation *aParent)
std::deque< Vertex > m_vertices
void PolygonTriangulation::Vertex::updateList ( )
inline

Function updateList 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 148 of file polygon_triangulation.h.

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

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

149  {
150  Vertex* p = next;
151 
152  while( p != this )
153  {
157  if( *p == *p->next )
158  {
159  p = p->prev;
160  p->next->remove();
161 
162  if( p == p->next )
163  break;
164  }
165 
166  p->updateOrder();
167  p = p->next;
168  };
169 
170  updateOrder();
171  zSort();
172  }
void remove()
Function remove Removes the node from the linked list and z-ordered linked list.
void zSort()
Sort all vertices in this vertex&#39;s list by their Morton code.
Vertex(size_t aIndex, double aX, double aY, PolygonTriangulation *aParent)
void PolygonTriangulation::Vertex::updateOrder ( )
inline

Definition at line 137 of file polygon_triangulation.h.

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

Referenced by updateList().

138  {
139  if( !z )
140  z = parent->zOrder( x, y );
141  }
int32_t zOrder(const double aX, const double aY) const
Calculate the Morton code of the Vertex http://www.graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN.
void PolygonTriangulation::Vertex::zSort ( )
inline

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

Definition at line 177 of file polygon_triangulation.h.

References next, nextZ, prevZ, and z.

Referenced by updateList().

178  {
179  std::deque<Vertex*> queue;
180 
181  queue.push_back( this );
182 
183  for( auto p = next; p && p != this; p = p->next )
184  queue.push_back( p );
185 
186  std::sort( queue.begin(), queue.end(), []( const Vertex* a, const Vertex* b)
187  {
188  return a->z < b->z;
189  } );
190 
191  Vertex* prev_elem = nullptr;
192  for( auto elem : queue )
193  {
194  if( prev_elem )
195  prev_elem->nextZ = elem;
196 
197  elem->prevZ = prev_elem;
198  prev_elem = elem;
199  }
200 
201  prev_elem->nextZ = nullptr;
202  }
Vertex(size_t aIndex, double aX, double aY, PolygonTriangulation *aParent)

Member Data Documentation

Vertex* PolygonTriangulation::Vertex::nextZ = nullptr

Definition at line 229 of file polygon_triangulation.h.

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

PolygonTriangulation* PolygonTriangulation::Vertex::parent

Definition at line 218 of file polygon_triangulation.h.

Referenced by split(), and updateOrder().

Vertex* PolygonTriangulation::Vertex::prevZ = nullptr

Definition at line 228 of file polygon_triangulation.h.

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

const double PolygonTriangulation::Vertex::x
const double PolygonTriangulation::Vertex::y
int32_t PolygonTriangulation::Vertex::z = 0

Definition at line 225 of file polygon_triangulation.h.

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


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