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 VECTOR2I last_pt{ std::numeric_limits<int>::max(), std::numeric_limits<int>::max() };
42
43 auto addVertex = [&]( int i )
44 {
45 const VECTOR2I& pt = points.CPoint( i );
46 VECTOR2I diff = pt - last_pt;
48 {
49 tail = insertVertex( i, pt, tail, aUserData );
50 last_pt = pt;
51 }
52 };
53
54 if( sum > 0.0 )
55 {
56 for( int i = points.PointCount() - 1; i >= 0; i-- )
57 addVertex( i );
58 }
59 else
60 {
61 for( int i = 0; i < points.PointCount(); i++ )
62 addVertex( i );
63 }
64
65 if( tail && ( *tail == *tail->next ) )
66 {
67 tail->next->remove();
68 }
69
70 return tail;
71}
72
73
79uint32_t VERTEX_SET::zOrder( const double aX, const double aY ) const
80{
81 double limit_x = std::clamp( ( aX - m_bbox.GetX() ) / m_bbox.GetWidth(), 0.0, 1.0 );
82 double limit_y = std::clamp( ( aY - m_bbox.GetY() ) / m_bbox.GetHeight(), 0.0, 1.0 );
83
84 uint32_t x = static_cast<uint32_t>( limit_x * 32767.0 );
85 uint32_t y = static_cast<uint32_t>( limit_y * 32767.0 );
86
87 x = ( x | ( x << 8 ) ) & 0x00FF00FF;
88 x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
89 x = ( x | ( x << 2 ) ) & 0x33333333;
90 x = ( x | ( x << 1 ) ) & 0x55555555;
91
92 y = ( y | ( y << 8 ) ) & 0x00FF00FF;
93 y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
94 y = ( y | ( y << 2 ) ) & 0x33333333;
95 y = ( y | ( y << 1 ) ) & 0x55555555;
96
97 return x | ( y << 1 );
98}
99
100
104double VERTEX_SET::area( const VERTEX* p, const VERTEX* q, const VERTEX* r ) const
105{
106 return ( q->y - p->y ) * ( r->x - q->x ) - ( q->x - p->x ) * ( r->y - q->y );
107}
108
109
110bool VERTEX_SET::same_point( const VERTEX* aA, const VERTEX* aB ) const
111{
112 return aA && aB && aA->x == aB->x && aA->y == aB->y;
113}
114
116{
117 VERTEX* nz = aPt->nextZ;
118 VERTEX* pz = aPt->prevZ;
119
120 // If we hit a fracture point, we want to continue around the
121 // edge we are working on and not switch to the pair edge
122 // However, this will depend on which direction the initial
123 // fracture hit is. If we find that we skip directly to
124 // a new fracture point, then we know that we are proceeding
125 // in the wrong direction from the fracture and should
126 // fall through to the next point
127 if( same_point( aPt, nz ) && same_point( aPt->next, nz->prev )
128 && aPt->y == aPt->next->y )
129 {
130 return nz->next;
131 }
132
133 if( same_point( aPt, pz ) && same_point( aPt->next, pz->prev )
134 && aPt->y == aPt->next->y )
135 {
136 return pz->next;
137 }
138
139 return aPt->next;
140}
141
143{
144 VERTEX* nz = aPt->nextZ;
145 VERTEX* pz = aPt->prevZ;
146
147 // If we hit a fracture point, we want to continue around the
148 // edge we are working on and not switch to the pair edge
149 // However, this will depend on which direction the initial
150 // fracture hit is. If we find that we skip directly to
151 // a new fracture point, then we know that we are proceeding
152 // in the wrong direction from the fracture and should
153 // fall through to the next point
154 if( same_point( aPt, nz )
155 && aPt->y == aPt->prev->y)
156 {
157 return nz->prev;
158 }
159
160 if( same_point( aPt, pz )
161 && aPt->y == aPt->prev->y )
162 {
163 return pz->prev;
164 }
165
166 return aPt->prev;
167
168}
169
170
171bool VERTEX_SET::locallyInside( const VERTEX* a, const VERTEX* b ) const
172{
173 const VERTEX* an = getNextOutlineVertex( a );
174 const VERTEX* ap = getPrevOutlineVertex( a );
175
176 if( area( ap, a, an ) < 0 )
177 return area( a, b, an ) >= 0 && area( a, ap, b ) >= 0;
178 else
179 return area( a, b, ap ) < 0 || area( a, an, b ) < 0;
180}
181
182
183bool VERTEX_SET::middleInside( const VERTEX* a, const VERTEX* b ) const
184{
185 const VERTEX* p = a;
186 bool inside = false;
187 double px = ( a->x + b->x ) / 2;
188 double py = ( a->y + b->y ) / 2;
189
190 do
191 {
192 if( ( ( p->y > py ) != ( p->next->y > py ) )
193 && ( px < ( p->next->x - p->x ) * ( py - p->y ) / ( p->next->y - p->y ) + p->x ) )
194 inside = !inside;
195
196 p = p->next;
197 } while( p != a );
198
199 return inside;
200}
201
208VERTEX* VERTEX_SET::insertVertex( int aIndex, const VECTOR2I& pt, VERTEX* last, void* aUserData )
209{
210 m_vertices.emplace_back( aIndex, pt.x, pt.y, this, aUserData );
211
212 VERTEX* p = &m_vertices.back();
213
214 if( !last )
215 {
216 p->prev = p;
217 p->next = p;
218 }
219 else
220 {
221 p->next = last->next;
222 p->prev = last;
223 last->next->prev = p;
224 last->next = p;
225 }
226 return p;
227}
228
229
231{
232 parent->m_vertices.emplace_back( i, x, y, parent, m_userData );
233 VERTEX* a2 = parent->insertVertex( i, VECTOR2I( x, y ), nullptr, m_userData );
234 parent->m_vertices.emplace_back( b->i, b->x, b->y, parent, m_userData );
235 VERTEX* b2 = &parent->m_vertices.back();
236 VERTEX* an = next;
237 VERTEX* bp = b->prev;
238
239 next = b;
240 b->prev = this;
241
242 a2->next = an;
243 an->prev = a2;
244
245 b2->next = a2;
246 a2->prev = b2;
247
248 bp->next = b2;
249 b2->prev = bp;
250
251 return b2;
252}
253
254
256{
257 if( !z )
258 z = parent->zOrder( x, y );
259}
260
261
262bool VERTEX::isEar( bool aMatchUserData ) const
263{
264 const VERTEX* a = prev;
265 const VERTEX* b = this;
266 const VERTEX* c = next;
267
268 if( aMatchUserData )
269 {
270 while( a->GetUserData() != m_userData )
271 a = a->prev;
272
273 while( c->GetUserData() != m_userData )
274 c = c->next;
275 }
276
277 // If the area >=0, then the three points for a concave sequence
278 // with b as the reflex point
279 if( parent->area( a, b, c ) >= 0 )
280 return false;
281
282 // triangle bbox
283 const double minTX = std::min( a->x, std::min( b->x, c->x ) );
284 const double minTY = std::min( a->y, std::min( b->y, c->y ) );
285 const double maxTX = std::max( a->x, std::max( b->x, c->x ) );
286 const double maxTY = std::max( a->y, std::max( b->y, c->y ) );
287
288 // z-order range for the current triangle bounding box
289 const uint32_t minZ = parent->zOrder( minTX, minTY );
290 const uint32_t maxZ = parent->zOrder( maxTX, maxTY );
291
292 // first look for points inside the triangle in increasing z-order
293 VERTEX* p = nextZ;
294
295 while( p && p->z <= maxZ )
296 {
297 if( ( !aMatchUserData || p->GetUserData() == m_userData )
298 && p != a && p != c
299 && p->inTriangle( *a, *b, *c )
300 && parent->area( p->prev, p, p->next ) >= 0 )
301 return false;
302
303 p = p->nextZ;
304 }
305
306 // then look for points in decreasing z-order
307 p = prevZ;
308
309 while( p && p->z >= minZ )
310 {
311 if( ( !aMatchUserData || p->GetUserData() == m_userData )
312 && p != a && p != c
313 && p->inTriangle( *a, *b, *c )
314 && parent->area( p->prev, p, p->next ) >= 0 )
315 return false;
316
317 p = p->prevZ;
318 }
319
320 return true;
321}
constexpr coord_type GetY() const
Definition: box2.h:208
constexpr size_type GetWidth() const
Definition: box2.h:214
constexpr coord_type GetX() const
Definition: box2.h:207
constexpr size_type GetHeight() const
Definition: box2.h:215
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 SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:307
std::deque< VERTEX > m_vertices
Definition: vertex_set.h:343
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:183
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:27
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:171
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.
Definition: vertex_set.cpp:142
void SetBoundingBox(const BOX2I &aBBox)
Definition: vertex_set.cpp:21
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:104
VERTEX * insertVertex(int aIndex, const VECTOR2I &pt, VERTEX *last, void *aUserData=nullptr)
Insert a vertex into the vertex set.
Definition: vertex_set.cpp:208
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.
Definition: vertex_set.cpp:115
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 ...
Definition: vertex_set.cpp:79
bool same_point(const VERTEX *aA, const VERTEX *aB) const
Check if two vertices are at the same point.
Definition: vertex_set.cpp:110
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:230
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
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.
Definition: vertex_set.cpp:262
const double y
Definition: vertex_set.h:236
void updateOrder()
Definition: vertex_set.cpp:255
VERTEX_SET * parent
Definition: vertex_set.h:237
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:695