KiCad PCB EDA Suite
Loading...
Searching...
No Matches
vertex_set.cpp
Go to the documentation of this file.
1/*
2 * This program is part of KiCad, a free EDA CAD application.
3 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19#include <geometry/vertex_set.h>
20
21void VERTEX_SET::SetBoundingBox( const BOX2I& aBBox ) { m_bbox = aBBox; }
22
23
27VERTEX* VERTEX_SET::createList( const SHAPE_LINE_CHAIN& points, VERTEX* aTail, void* aUserData )
28{
29 VERTEX* tail = aTail;
30 double sum = 0.0;
31
32 // Check for winding order
33 for( int i = 0; i < points.PointCount(); i++ )
34 {
35 VECTOR2D p1 = points.CPoint( i );
36 VECTOR2D p2 = points.CPoint( i + 1 );
37
38 sum += ( ( p2.x - p1.x ) * ( p2.y + p1.y ) );
39 }
40
41 VECTOR2L last_pt;
42 bool first = true;
43
44 auto addVertex = [&]( int i )
45 {
46 const VECTOR2I& pt = points.CPoint( i );
47
48 if( first || pt.SquaredDistance( last_pt ) > m_simplificationLevel )
49 {
50 tail = insertVertex( i, pt, tail, aUserData );
51 last_pt = pt;
52 first = false;
53 }
54 };
55
56 if( sum > 0.0 )
57 {
58 for( int i = points.PointCount() - 1; i >= 0; i-- )
59 addVertex( i );
60 }
61 else
62 {
63 for( int i = 0; i < points.PointCount(); i++ )
64 addVertex( i );
65 }
66
67 if( tail && ( *tail == *tail->next ) )
68 {
69 tail->next->remove();
70 }
71
72 return tail;
73}
74
75
81uint32_t VERTEX_SET::zOrder( const double aX, const double aY ) const
82{
83 double limit_x = std::clamp( ( aX - m_bbox.GetX() ) / m_bbox.GetWidth(), 0.0, 1.0 );
84 double limit_y = std::clamp( ( aY - m_bbox.GetY() ) / m_bbox.GetHeight(), 0.0, 1.0 );
85
86 uint32_t x = static_cast<uint32_t>( limit_x * 32767.0 );
87 uint32_t y = static_cast<uint32_t>( limit_y * 32767.0 );
88
89 x = ( x | ( x << 8 ) ) & 0x00FF00FF;
90 x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
91 x = ( x | ( x << 2 ) ) & 0x33333333;
92 x = ( x | ( x << 1 ) ) & 0x55555555;
93
94 y = ( y | ( y << 8 ) ) & 0x00FF00FF;
95 y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
96 y = ( y | ( y << 2 ) ) & 0x33333333;
97 y = ( y | ( y << 1 ) ) & 0x55555555;
98
99 return x | ( y << 1 );
100}
101
102
106double VERTEX_SET::area( const VERTEX* p, const VERTEX* q, const VERTEX* r ) const
107{
108 return ( q->y - p->y ) * ( r->x - q->x ) - ( q->x - p->x ) * ( r->y - q->y );
109}
110
111
112bool VERTEX_SET::same_point( const VERTEX* aA, const VERTEX* aB ) const
113{
114 return aA && aB && aA->x == aB->x && aA->y == aB->y;
115}
116
118{
119 VERTEX* nz = aPt->nextZ;
120 VERTEX* pz = aPt->prevZ;
121
122 // If we hit a fracture point, we want to continue around the
123 // edge we are working on and not switch to the pair edge
124 // However, this will depend on which direction the initial
125 // fracture hit is. If we find that we skip directly to
126 // a new fracture point, then we know that we are proceeding
127 // in the wrong direction from the fracture and should
128 // fall through to the next point
129 if( same_point( aPt, nz ) && same_point( aPt->next, nz->prev )
130 && aPt->y == aPt->next->y )
131 {
132 return nz->next;
133 }
134
135 if( same_point( aPt, pz ) && same_point( aPt->next, pz->prev )
136 && aPt->y == aPt->next->y )
137 {
138 return pz->next;
139 }
140
141 return aPt->next;
142}
143
145{
146 VERTEX* nz = aPt->nextZ;
147 VERTEX* pz = aPt->prevZ;
148
149 // If we hit a fracture point, we want to continue around the
150 // edge we are working on and not switch to the pair edge
151 // However, this will depend on which direction the initial
152 // fracture hit is. If we find that we skip directly to
153 // a new fracture point, then we know that we are proceeding
154 // in the wrong direction from the fracture and should
155 // fall through to the next point
156 if( same_point( aPt, nz )
157 && aPt->y == aPt->prev->y)
158 {
159 return nz->prev;
160 }
161
162 if( same_point( aPt, pz )
163 && aPt->y == aPt->prev->y )
164 {
165 return pz->prev;
166 }
167
168 return aPt->prev;
169
170}
171
172
173bool VERTEX_SET::locallyInside( const VERTEX* a, const VERTEX* b ) const
174{
175 const VERTEX* an = getNextOutlineVertex( a );
176 const VERTEX* ap = getPrevOutlineVertex( a );
177
178 if( area( ap, a, an ) < 0 )
179 return area( a, b, an ) >= 0 && area( a, ap, b ) >= 0;
180 else
181 return area( a, b, ap ) < 0 || area( a, an, b ) < 0;
182}
183
184
185bool VERTEX_SET::middleInside( const VERTEX* a, const VERTEX* b ) const
186{
187 const VERTEX* p = a;
188 bool inside = false;
189 double px = ( a->x + b->x ) / 2;
190 double py = ( a->y + b->y ) / 2;
191
192 do
193 {
194 if( ( ( p->y > py ) != ( p->next->y > py ) )
195 && ( px < ( p->next->x - p->x ) * ( py - p->y ) / ( p->next->y - p->y ) + p->x ) )
196 inside = !inside;
197
198 p = p->next;
199 } while( p != a );
200
201 return inside;
202}
203
210VERTEX* VERTEX_SET::insertVertex( int aIndex, const VECTOR2I& pt, VERTEX* last, void* aUserData )
211{
212 m_vertices.emplace_back( aIndex, pt.x, pt.y, this, aUserData );
213
214 VERTEX* p = &m_vertices.back();
215
216 if( !last )
217 {
218 p->prev = p;
219 p->next = p;
220 }
221 else
222 {
223 p->next = last->next;
224 p->prev = last;
225 last->next->prev = p;
226 last->next = p;
227 }
228 return p;
229}
230
231
233{
234 parent->m_vertices.emplace_back( i, x, y, parent, m_userData );
235 VERTEX* a2 = parent->insertVertex( i, VECTOR2I( x, y ), nullptr, m_userData );
236 parent->m_vertices.emplace_back( b->i, b->x, b->y, parent, m_userData );
237 VERTEX* b2 = &parent->m_vertices.back();
238 VERTEX* an = next;
239 VERTEX* bp = b->prev;
240
241 next = b;
242 b->prev = this;
243
244 a2->next = an;
245 an->prev = a2;
246
247 b2->next = a2;
248 a2->prev = b2;
249
250 bp->next = b2;
251 b2->prev = bp;
252
253 return b2;
254}
255
256
258{
259 if( !z )
260 z = parent->zOrder( x, y );
261}
262
263
264bool VERTEX::isEar( bool aMatchUserData ) const
265{
266 const VERTEX* a = prev;
267 const VERTEX* b = this;
268 const VERTEX* c = next;
269
270 if( aMatchUserData )
271 {
272 while( a->GetUserData() != m_userData )
273 a = a->prev;
274
275 while( c->GetUserData() != m_userData )
276 c = c->next;
277 }
278
279 // If the area >=0, then the three points for a concave sequence
280 // with b as the reflex point
281 if( parent->area( a, b, c ) >= 0 )
282 return false;
283
284 // triangle bbox
285 const double minTX = std::min( a->x, std::min( b->x, c->x ) );
286 const double minTY = std::min( a->y, std::min( b->y, c->y ) );
287 const double maxTX = std::max( a->x, std::max( b->x, c->x ) );
288 const double maxTY = std::max( a->y, std::max( b->y, c->y ) );
289
290 // z-order range for the current triangle bounding box
291 const uint32_t minZ = parent->zOrder( minTX, minTY );
292 const uint32_t maxZ = parent->zOrder( maxTX, maxTY );
293
294 // first look for points inside the triangle in increasing z-order
295 VERTEX* p = nextZ;
296
297 while( p && p->z <= maxZ )
298 {
299 if( ( !aMatchUserData || p->GetUserData() == m_userData )
300 && p != a && p != c
301 && p->inTriangle( *a, *b, *c )
302 && parent->area( p->prev, p, p->next ) >= 0 )
303 return false;
304
305 p = p->nextZ;
306 }
307
308 // then look for points in decreasing z-order
309 p = prevZ;
310
311 while( p && p->z >= minZ )
312 {
313 if( ( !aMatchUserData || p->GetUserData() == m_userData )
314 && p != a && p != c
315 && p->inTriangle( *a, *b, *c )
316 && parent->area( p->prev, p, p->next ) >= 0 )
317 return false;
318
319 p = p->prevZ;
320 }
321
322 return true;
323}
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...
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
constexpr extended_type SquaredDistance(const VECTOR2< T > &aVector) const
Compute the squared distance between two vectors.
Definition vector2d.h:569
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.
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.
VERTEX * split(VERTEX *b)
Split the referenced polygon between the reference point and vertex b, assuming they are in the same ...
const double x
Definition vertex_set.h:235
VERTEX * next
Definition vertex_set.h:241
VERTEX * prevZ
Definition vertex_set.h:247
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
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
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
VECTOR2< double > VECTOR2D
Definition vector2d.h:694
VECTOR2< int64_t > VECTOR2L
Definition vector2d.h:696