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.

## ◆ 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  }

## ◆ 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

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.

## ◆ 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()
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().

## ◆ i

 const size_t PolygonTriangulation::Vertex::i

Definition at line 241 of file polygon_triangulation.h.

## ◆ next

 Vertex* PolygonTriangulation::Vertex::next = nullptr

## ◆ 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

 Vertex* PolygonTriangulation::Vertex::prev = nullptr

## ◆ 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

Definition at line 242 of file polygon_triangulation.h.

## ◆ y

 const double PolygonTriangulation::Vertex::y

Definition at line 243 of file polygon_triangulation.h.

## ◆ 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: