KiCad PCB EDA Suite
Loading...
Searching...
No Matches
vertex_set.h
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright The KiCad Developers, see AUTHORS.TXT for contributors.
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 3
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, you may find one here:
18 * http://www.gnu.org/licenses/gpl-3.0.html
19 * or you may search the http://www.gnu.org website for the version 3 license,
20 * or you may write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
22 *
23 * Based on Uniform Plane Subdivision algorithm from Lamot, Marko, and Borut Žalik.
24 * "A fast polygon triangulation algorithm based on uniform plane subdivision."
25 * Computers & graphics 27, no. 2 (2003): 239-253.
26 *
27 * Code derived from:
28 * K-3D which is Copyright (c) 2005-2006, Romain Behar, GPL-2, license above
29 * earcut which is Copyright (c) 2016, Mapbox, ISC
30 *
31 * ISC License:
32 * Permission to use, copy, modify, and/or distribute this software for any purpose
33 * with or without fee is hereby granted, provided that the above copyright notice
34 * and this permission notice appear in all copies.
35 *
36 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
37 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
38 * FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
39 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
40 * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
41 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
42 * THIS SOFTWARE.
43 *
44 */
45
46#ifndef VERTEX_SET_H
47#define VERTEX_SET_H
48
49#include <algorithm>
50#include <deque>
51
52#include <math/box2.h>
54
55class VERTEX_SET;
56
57class VERTEX
58{
59 public:
60
61 VERTEX( int aIndex, double aX, double aY, VERTEX_SET* aParent, void* aUserData = nullptr ) :
62 i( aIndex ),
63 x( aX ),
64 y( aY ),
65 parent( aParent ),
66 m_userData( aUserData )
67 {
68 }
69
70 VERTEX& operator=( const VERTEX& ) = delete;
71 VERTEX& operator=( VERTEX&& ) = delete;
72
73 bool operator==( const VERTEX& rhs ) const
74 {
75 return this->x == rhs.x && this->y == rhs.y;
76 }
77 bool operator!=( const VERTEX& rhs ) const { return !( *this == rhs ); }
78
79 void* GetUserData() const { return m_userData; }
80
84 void remove()
85 {
86 next->prev = prev;
87 prev->next = next;
88
89 if( prevZ )
90 prevZ->nextZ = nextZ;
91
92 if( nextZ )
93 nextZ->prevZ = prevZ;
94
95 next = nullptr;
96 prev = nullptr;
97 nextZ = nullptr;
98 prevZ = nullptr;
99 }
100
101
102
113 VERTEX* split( VERTEX* b );
114
115 void updateOrder();
116
122 {
123 VERTEX* p = next;
124
125 while( p != this )
126 {
130 if( *p == *p->next )
131 {
132 p = p->prev;
133 p->next->remove();
134
135 if( p == p->next )
136 break;
137 }
138
139 p->updateOrder();
140 p = p->next;
141 };
142
143 updateOrder();
144 zSort();
145 }
146
150 void zSort()
151 {
152 std::deque<VERTEX*> queue;
153
154 queue.push_back( this );
155
156 for( VERTEX* p = next; p && p != this; p = p->next )
157 queue.push_back( p );
158
159 std::sort( queue.begin(), queue.end(), []( const VERTEX* a, const VERTEX* b )
160 {
161 if( a->z != b->z )
162 return a->z < b->z;
163
164 if( a->x != b->x )
165 return a->x < b->x;
166
167 if( a->y != b->y )
168 return a->y < b->y;
169
170 return a->i < b->i;
171 } );
172
173 VERTEX* prev_elem = nullptr;
174
175 for( VERTEX* elem : queue )
176 {
177 if( prev_elem )
178 prev_elem->nextZ = elem;
179
180 elem->prevZ = prev_elem;
181 prev_elem = elem;
182 }
183
184 prev_elem->nextZ = nullptr;
185 }
186
187
191 bool inTriangle( const VERTEX& a, const VERTEX& b, const VERTEX& c )
192 {
193 return ( c.x - x ) * ( a.y - y ) - ( a.x - x ) * ( c.y - y ) >= 0
194 && ( a.x - x ) * ( b.y - y ) - ( b.x - x ) * ( a.y - y ) >= 0
195 && ( b.x - x ) * ( c.y - y ) - ( c.x - x ) * ( b.y - y ) >= 0;
196 }
197
202 double area( const VERTEX* aEnd = nullptr ) const
203 {
204 const VERTEX* p = this;
205 double a = 0.0;
206
207 do
208 {
209 a += ( p->x + p->next->x ) * ( p->next->y - p->y );
210 p = p->next;
211 } while( p != this && p != aEnd );
212
213 if( p != this )
214 a += ( p->x + x ) * ( y - p->y );
215
216 return a / 2;
217 }
218
232 bool isEar( bool aMatchUserData = false ) const;
233
234 const int i;
235 const double x;
236 const double y;
238
239 // previous and next vertices nodes in a polygon ring
240 VERTEX* prev = nullptr;
241 VERTEX* next = nullptr;
242
243 // z-order curve value
244 uint32_t z = 0;
245
246 // previous and next nodes in z-order
247 VERTEX* prevZ = nullptr;
248 VERTEX* nextZ = nullptr;
249
250 void* m_userData = nullptr;
251};
252
254{
255 friend class VERTEX;
256
257public:
258 VERTEX_SET( int aSimplificationLevel )
259 {
260 m_simplificationLevel = aSimplificationLevel * ( VECTOR2I::extended_type ) aSimplificationLevel;
261 }
263
264 void SetBoundingBox( const BOX2I& aBBox );
265
274 VERTEX* insertVertex( int aIndex, const VECTOR2I& pt, VERTEX* last, void* aUserData = nullptr );
275
283 VERTEX* createList( const SHAPE_LINE_CHAIN& points, VERTEX* aTail = nullptr, void* aUserData = nullptr );
284
285protected:
286
293 VERTEX* getNextOutlineVertex( const VERTEX* aPt ) const;
294
301 VERTEX* getPrevOutlineVertex( const VERTEX* aPt ) const;
302
312 bool locallyInside( const VERTEX* a, const VERTEX* b ) const;
313
320 bool middleInside( const VERTEX* a, const VERTEX* b ) const;
321
328 bool same_point( const VERTEX* aA, const VERTEX* aB ) const;
329
335 uint32_t zOrder( const double aX, const double aY ) const;
336
340 double area( const VERTEX* p, const VERTEX* q, const VERTEX* r ) const;
341
343 std::deque<VERTEX> m_vertices;
345};
346
347
348
349#endif // VERTEX_SET_H
BOX2< VECTOR2I > BOX2I
Definition box2.h:922
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
VECTOR2_TRAITS< int32_t >::extended_type extended_type
Definition vector2d.h:73
std::deque< VERTEX > m_vertices
Definition vertex_set.h:343
friend class VERTEX
Definition vertex_set.h:255
bool middleInside(const VERTEX *a, const VERTEX *b) const
Check if the middle of the segment from a to b is inside the polygon.
VERTEX * createList(const SHAPE_LINE_CHAIN &points, VERTEX *aTail=nullptr, void *aUserData=nullptr)
Create a list of vertices from a line chain.
bool locallyInside(const VERTEX *a, const VERTEX *b) const
Check whether the segment from vertex a -> vertex b is inside the polygon around the immediate area o...
BOX2I m_bbox
Definition vertex_set.h:342
VERTEX * getPrevOutlineVertex(const VERTEX *aPt) const
Get the previous vertex in the outline, avoiding steiner points and points that overlap with splits.
void SetBoundingBox(const BOX2I &aBBox)
double area(const VERTEX *p, const VERTEX *q, const VERTEX *r) const
Return the twice the signed area of the triangle formed by vertices p, q, and r.
VERTEX * insertVertex(int aIndex, const VECTOR2I &pt, VERTEX *last, void *aUserData=nullptr)
Insert a vertex into the vertex set.
VERTEX_SET(int aSimplificationLevel)
Definition vertex_set.h:258
VECTOR2I::extended_type m_simplificationLevel
Definition vertex_set.h:344
VERTEX * getNextOutlineVertex(const VERTEX *aPt) const
Get the next vertex in the outline, avoiding steiner points and points that overlap with splits.
uint32_t zOrder(const double aX, const double aY) const
Note that while the inputs are doubles, these are scaled by the size of the bounding box to fit into ...
bool same_point(const VERTEX *aA, const VERTEX *aB) const
Check if two vertices are at the same point.
void zSort()
Sort all vertices in this vertex's list by their Morton code.
Definition vertex_set.h:150
VERTEX * split(VERTEX *b)
Split the referenced polygon between the reference point and vertex b, assuming they are in the same ...
VERTEX & operator=(const VERTEX &)=delete
const double x
Definition vertex_set.h:235
bool operator!=(const VERTEX &rhs) const
Definition vertex_set.h:77
VERTEX * next
Definition vertex_set.h:241
VERTEX * prevZ
Definition vertex_set.h:247
void updateList()
After inserting or changing nodes, this function should be called to remove duplicate vertices and en...
Definition vertex_set.h:121
bool inTriangle(const VERTEX &a, const VERTEX &b, const VERTEX &c)
Check to see if triangle surrounds our current vertex.
Definition vertex_set.h:191
VERTEX * nextZ
Definition vertex_set.h:248
VERTEX * prev
Definition vertex_set.h:240
const int i
Definition vertex_set.h:234
bool operator==(const VERTEX &rhs) const
Definition vertex_set.h:73
void * GetUserData() const
Definition vertex_set.h:79
void * m_userData
Definition vertex_set.h:250
void remove()
Remove the node from the linked list and z-ordered linked list.
Definition vertex_set.h:84
VERTEX(int aIndex, double aX, double aY, VERTEX_SET *aParent, void *aUserData=nullptr)
Definition vertex_set.h:61
VERTEX & operator=(VERTEX &&)=delete
double area(const VERTEX *aEnd=nullptr) const
Returns the signed area of the polygon connected to the current vertex, optionally ending at a specif...
Definition vertex_set.h:202
uint32_t z
Definition vertex_set.h:244
bool isEar(bool aMatchUserData=false) const
Check whether the given vertex is in the middle of an ear.
const double y
Definition vertex_set.h:236
void updateOrder()
VERTEX_SET * parent
Definition vertex_set.h:237
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:695