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.

## ◆ Vertex()

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

Definition at line 68 of file polygon_triangulation.h.

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

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

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  }

References x, and y.

Referenced by PolygonTriangulation::isEar().

## ◆ operator!=()

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

Definition at line 79 of file polygon_triangulation.h.

79 { 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 75 of file polygon_triangulation.h.

76  {
77  return this->x == rhs.x && this->y == rhs.y;
78  }

References x, and y.

## ◆ remove()

 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.

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  }

References next, nextZ, prev, and prevZ.

## ◆ split()

 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.

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

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

Referenced by PolygonTriangulation::splitPolygon().

## ◆ updateList()

 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.

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

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....

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

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)

References next, nextZ, prevZ, and z.

Referenced by updateList().

## ◆ i

 const size_t PolygonTriangulation::Vertex::i

Definition at line 215 of file polygon_triangulation.h.

## ◆ next

 Vertex* PolygonTriangulation::Vertex::next = nullptr

## ◆ nextZ

 Vertex* PolygonTriangulation::Vertex::nextZ = nullptr

Definition at line 229 of file polygon_triangulation.h.

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

## ◆ parent

 PolygonTriangulation* PolygonTriangulation::Vertex::parent

Definition at line 218 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 228 of file polygon_triangulation.h.

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

## ◆ x

 const double PolygonTriangulation::Vertex::x

Definition at line 216 of file polygon_triangulation.h.

## ◆ y

 const double PolygonTriangulation::Vertex::y

Definition at line 217 of file polygon_triangulation.h.

## ◆ z

 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: