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 (C) 20218 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
228 bool isEar() const;
229
230 const int i;
231 const double x;
232 const double y;
234
235 // previous and next vertices nodes in a polygon ring
236 VERTEX* prev = nullptr;
237 VERTEX* next = nullptr;
238
239 // z-order curve value
240 int32_t z = 0;
241
242 // previous and next nodes in z-order
243 VERTEX* prevZ = nullptr;
244 VERTEX* nextZ = nullptr;
245
246 void* m_userData = nullptr;
247};
248
250{
251 friend class VERTEX;
252
253public:
254 VERTEX_SET( int aSimplificationLevel )
255 {
256 m_simplificationLevel = aSimplificationLevel * ( VECTOR2I::extended_type ) aSimplificationLevel;
257 }
259
260 void SetBoundingBox( const BOX2I& aBBox );
261
270 VERTEX* insertVertex( int aIndex, const VECTOR2I& pt, VERTEX* last, void* aUserData = nullptr );
271
279 VERTEX* createList( const SHAPE_LINE_CHAIN& points, VERTEX* aTail = nullptr, void* aUserData = nullptr );
280
281protected:
282
289 VERTEX* getNextOutlineVertex( const VERTEX* aPt ) const;
290
297 VERTEX* getPrevOutlineVertex( const VERTEX* aPt ) const;
298
308 bool locallyInside( const VERTEX* a, const VERTEX* b ) const;
309
316 bool middleInside( const VERTEX* a, const VERTEX* b ) const;
317
324 bool same_point( const VERTEX* aA, const VERTEX* aB ) const;
325
331 int32_t zOrder( const double aX, const double aY ) const;
332
336 double area( const VERTEX* p, const VERTEX* q, const VERTEX* r ) const;
337
339 std::deque<VERTEX> m_vertices;
341};
342
343
344
345#endif // VERTEX_SET_H
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:339
int32_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 ...
Definition: vertex_set.cpp:61
bool middleInside(const VERTEX *a, const VERTEX *b) const
Check if the middle of the segment from a to b is inside the polygon.
Definition: vertex_set.cpp:162
VERTEX * createList(const SHAPE_LINE_CHAIN &points, VERTEX *aTail=nullptr, void *aUserData=nullptr)
Create a list of vertices from a line chain.
Definition: vertex_set.cpp:9
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...
Definition: vertex_set.cpp:150
BOX2I m_bbox
Definition: vertex_set.h:338
VERTEX * getPrevOutlineVertex(const VERTEX *aPt) const
Get the previous vertex in the outline, avoiding steiner points and points that overlap with splits.
Definition: vertex_set.cpp:121
void SetBoundingBox(const BOX2I &aBBox)
Definition: vertex_set.cpp:3
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.
Definition: vertex_set.cpp:83
VERTEX * insertVertex(int aIndex, const VECTOR2I &pt, VERTEX *last, void *aUserData=nullptr)
Insert a vertex into the vertex set.
Definition: vertex_set.cpp:187
VERTEX_SET(int aSimplificationLevel)
Definition: vertex_set.h:254
VECTOR2I::extended_type m_simplificationLevel
Definition: vertex_set.h:340
VERTEX * getNextOutlineVertex(const VERTEX *aPt) const
Get the next vertex in the outline, avoiding steiner points and points that overlap with splits.
Definition: vertex_set.cpp:94
bool same_point(const VERTEX *aA, const VERTEX *aB) const
Check if two vertices are at the same point.
Definition: vertex_set.cpp:89
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 ...
Definition: vertex_set.cpp:209
VERTEX & operator=(const VERTEX &)=delete
const double x
Definition: vertex_set.h:231
bool operator!=(const VERTEX &rhs) const
Definition: vertex_set.h:77
VERTEX * next
Definition: vertex_set.h:237
VERTEX * prevZ
Definition: vertex_set.h:243
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:244
VERTEX * prev
Definition: vertex_set.h:236
const int i
Definition: vertex_set.h:230
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:246
void remove()
Remove the node from the linked list and z-ordered linked list.
Definition: vertex_set.h:84
int32_t z
Definition: vertex_set.h:240
VERTEX(int aIndex, double aX, double aY, VERTEX_SET *aParent, void *aUserData=nullptr)
Definition: vertex_set.h:61
VERTEX & operator=(VERTEX &&)=delete
bool isEar() const
Check whether the given vertex is in the middle of an ear.
Definition: vertex_set.cpp:241
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
const double y
Definition: vertex_set.h:232
void updateOrder()
Definition: vertex_set.cpp:234
VERTEX_SET * parent
Definition: vertex_set.h:233