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 }
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()

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

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

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