KiCad PCB EDA Suite
Loading...
Searching...
No Matches
fix_board_shape.cpp
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) 2023 Alex Shvartzkop <[email protected]>
5 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, you may find one here:
19 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20 * or you may search the http://www.gnu.org website for the version 2 license,
21 * or you may write to the Free Software Foundation, Inc.,
22 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23 */
24
25#include "fix_board_shape.h"
26
27#include <vector>
28#include <algorithm>
29#include <limits>
30#include <pcb_shape.h>
31#include <geometry/circle.h>
32
33#include <nanoflann.hpp>
34
35
37{
38 std::vector<std::pair<VECTOR2I, PCB_SHAPE*>> endpoints;
39
40 PCB_SHAPE_ENDPOINTS_ADAPTOR( const std::vector<PCB_SHAPE*>& shapes )
41 {
42 endpoints.reserve( shapes.size() * 2 );
43
44 for( PCB_SHAPE* shape : shapes )
45 {
46 endpoints.emplace_back( shape->GetStart(), shape );
47 endpoints.emplace_back( shape->GetEnd(), shape );
48 }
49 }
50
51 // Required by nanoflann
52 size_t kdtree_get_point_count() const { return endpoints.size(); }
53
54 // Returns the dim'th component of the idx'th point
55 double kdtree_get_pt( const size_t idx, const size_t dim ) const
56 {
57 if( dim == 0 )
58 return static_cast<double>( endpoints[idx].first.x );
59 else
60 return static_cast<double>( endpoints[idx].first.y );
61 }
62
63 template <class BBOX>
64 bool kdtree_get_bbox( BBOX& ) const
65 {
66 return false;
67 }
68};
69
70using KDTree = nanoflann::KDTreeSingleIndexAdaptor<nanoflann::L2_Simple_Adaptor<double, PCB_SHAPE_ENDPOINTS_ADAPTOR>,
72 2 /* dim */ >;
73
74
85static PCB_SHAPE* findNext( PCB_SHAPE* aShape, const VECTOR2I& aPoint, const KDTree& kdTree,
86 const PCB_SHAPE_ENDPOINTS_ADAPTOR& adaptor, double aChainingEpsilon )
87{
88 const double query_pt[2] = { static_cast<double>( aPoint.x ), static_cast<double>( aPoint.y ) };
89
90 uint32_t indices[2];
91 double distances[2];
92 kdTree.knnSearch( query_pt, 2, indices, distances );
93
94 if( distances[0] == std::numeric_limits<double>::max() )
95 return nullptr;
96
97 // Find the closest valid candidate
98 PCB_SHAPE* closest_graphic = nullptr;
99 double closest_dist_sq = aChainingEpsilon * aChainingEpsilon;
100
101 for( size_t i = 0; i < 2; ++i )
102 {
103 if( distances[i] == std::numeric_limits<double>::max() )
104 continue;
105
106 PCB_SHAPE* candidate = adaptor.endpoints[indices[i]].second;
107
108 if( candidate == aShape )
109 continue;
110
111 if( candidate->GetFlags() & SKIP_STRUCT )
112 continue;
113
114 if( distances[i] < closest_dist_sq )
115 {
116 closest_dist_sq = distances[i];
117 closest_graphic = candidate;
118 }
119 }
120
121 return closest_graphic;
122}
123
124
125void ConnectBoardShapes( std::vector<PCB_SHAPE*>& aShapeList, int aChainingEpsilon )
126{
127 if( aShapeList.size() == 0 )
128 return;
129
130 // Pre-build KD-tree
131 PCB_SHAPE_ENDPOINTS_ADAPTOR adaptor( aShapeList );
132 KDTree kdTree( 2, adaptor );
133
134 auto closer_to_first = []( const VECTOR2I& aRef, const VECTOR2I& aFirst,
135 const VECTOR2I& aSecond ) -> bool
136 {
137 return ( aRef - aFirst ).SquaredEuclideanNorm() < ( aRef - aSecond ).SquaredEuclideanNorm();
138 };
139
140 auto min_distance_sq = []( const VECTOR2I& aRef, const VECTOR2I& aFirst,
141 const VECTOR2I& aSecond ) -> SEG::ecoord
142 {
143 return std::min( ( aRef - aFirst ).SquaredEuclideanNorm(),
144 ( aRef - aSecond ).SquaredEuclideanNorm() );
145 };
146
147 auto connectPair = [&]( PCB_SHAPE* aPrevShape, PCB_SHAPE* aShape )
148 {
149 bool success = false;
150
151 SHAPE_T shape0 = aPrevShape->GetShape();
152 SHAPE_T shape1 = aShape->GetShape();
153
154 if( shape0 == SHAPE_T::SEGMENT && shape1 == SHAPE_T::SEGMENT )
155 {
156 SEG seg0( aPrevShape->GetStart(), aPrevShape->GetEnd() );
157 SEG seg1( aShape->GetStart(), aShape->GetEnd() );
158 SEG::ecoord d[4];
159 d[0] = ( seg0.A - seg1.A ).SquaredEuclideanNorm();
160 d[1] = ( seg0.A - seg1.B ).SquaredEuclideanNorm();
161 d[2] = ( seg0.B - seg1.A ).SquaredEuclideanNorm();
162 d[3] = ( seg0.B - seg1.B ).SquaredEuclideanNorm();
163
164 int idx = std::min_element( d, d + 4 ) - d;
165 int i0 = idx / 2;
166 int i1 = idx % 2;
167
168 if( seg0.Intersects( seg1 ) || seg0.Angle( seg1 ) > ANGLE_45 )
169 {
170 if( OPT_VECTOR2I inter = seg0.IntersectLines( seg1 ) )
171 {
172 if( i0 == 0 )
173 aPrevShape->SetStart( *inter );
174 else
175 aPrevShape->SetEnd( *inter );
176
177 if( i1 == 0 )
178 aShape->SetStart( *inter );
179 else
180 aShape->SetEnd( *inter );
181
182 success = true;
183 }
184 }
185 }
186 else if( ( shape0 == SHAPE_T::ARC && shape1 == SHAPE_T::SEGMENT )
187 || ( shape0 == SHAPE_T::SEGMENT && shape1 == SHAPE_T::ARC ) )
188 {
189 PCB_SHAPE* arcShape = shape0 == SHAPE_T::ARC ? aPrevShape : aShape;
190 PCB_SHAPE* segShape = shape0 == SHAPE_T::SEGMENT ? aPrevShape : aShape;
191
192 VECTOR2I arcPts[2] = { arcShape->GetStart(), arcShape->GetEnd() };
193 VECTOR2I segPts[2] = { segShape->GetStart(), segShape->GetEnd() };
194
195 SEG::ecoord d[4];
196 d[0] = ( segPts[0] - arcPts[0] ).SquaredEuclideanNorm();
197 d[1] = ( segPts[0] - arcPts[1] ).SquaredEuclideanNorm();
198 d[2] = ( segPts[1] - arcPts[0] ).SquaredEuclideanNorm();
199 d[3] = ( segPts[1] - arcPts[1] ).SquaredEuclideanNorm();
200
201 int idx = std::min_element( d, d + 4 ) - d;
202
203 switch( idx )
204 {
205 case 0: segShape->SetStart( arcPts[0] ); break;
206 case 1: segShape->SetStart( arcPts[1] ); break;
207 case 2: segShape->SetEnd( arcPts[0] ); break;
208 case 3: segShape->SetEnd( arcPts[1] ); break;
209 }
210
211 success = true;
212 }
213 else if( shape0 == SHAPE_T::ARC && shape1 == SHAPE_T::ARC )
214 {
215 PCB_SHAPE* arc0 = aPrevShape;
216 PCB_SHAPE* arc1 = aShape;
217
218 VECTOR2I pts0[2] = { arc0->GetStart(), arc0->GetEnd() };
219 VECTOR2I pts1[2] = { arc1->GetStart(), arc1->GetEnd() };
220
221 SEG::ecoord d[4];
222 d[0] = ( pts0[0] - pts1[0] ).SquaredEuclideanNorm();
223 d[1] = ( pts0[0] - pts1[1] ).SquaredEuclideanNorm();
224 d[2] = ( pts0[1] - pts1[0] ).SquaredEuclideanNorm();
225 d[3] = ( pts0[1] - pts1[1] ).SquaredEuclideanNorm();
226
227 int idx = std::min_element( d, d + 4 ) - d;
228 int i0 = idx / 2;
229 int i1 = idx % 2;
230 VECTOR2I middle = ( pts0[i0] + pts1[i1] ) / 2;
231
232 if( i0 == 0 )
233 arc0->SetArcGeometry( middle, arc0->GetArcMid(), arc0->GetEnd() );
234 else
235 arc0->SetArcGeometry( arc0->GetStart(), arc0->GetArcMid(), middle );
236
237 if( i1 == 0 )
238 arc1->SetArcGeometry( middle, arc1->GetArcMid(), arc1->GetEnd() );
239 else
240 arc1->SetArcGeometry( arc1->GetStart(), arc1->GetArcMid(), middle );
241
242 success = true;
243 }
244 else if( ( shape0 == SHAPE_T::BEZIER && shape1 == SHAPE_T::ARC )
245 || ( shape0 == SHAPE_T::ARC && shape1 == SHAPE_T::BEZIER ) )
246 {
247 PCB_SHAPE* bezShape = shape0 == SHAPE_T::BEZIER ? aPrevShape : aShape;
248 PCB_SHAPE* arcShape = shape0 == SHAPE_T::ARC ? aPrevShape : aShape;
249
250 VECTOR2I bezPts[2] = { bezShape->GetStart(), bezShape->GetEnd() };
251 VECTOR2I arcPts[2] = { arcShape->GetStart(), arcShape->GetEnd() };
252
253 SEG::ecoord d[4];
254 d[0] = ( bezPts[0] - arcPts[0] ).SquaredEuclideanNorm();
255 d[1] = ( bezPts[0] - arcPts[1] ).SquaredEuclideanNorm();
256 d[2] = ( bezPts[1] - arcPts[0] ).SquaredEuclideanNorm();
257 d[3] = ( bezPts[1] - arcPts[1] ).SquaredEuclideanNorm();
258
259 int idx = std::min_element( d, d + 4 ) - d;
260
261 switch( idx )
262 {
263 case 0:
264 {
265 VECTOR2I delta = arcPts[0] - bezPts[0];
266 bezShape->SetStart( arcPts[0] );
267 bezShape->SetBezierC1( bezShape->GetBezierC1() + delta );
268 break;
269 }
270 case 1:
271 {
272 VECTOR2I delta = arcPts[1] - bezPts[0];
273 bezShape->SetStart( arcPts[1] );
274 bezShape->SetBezierC1( bezShape->GetBezierC1() + delta );
275 break;
276 }
277 case 2:
278 {
279 VECTOR2I delta = arcPts[0] - bezPts[1];
280 bezShape->SetEnd( arcPts[0] );
281 bezShape->SetBezierC2( bezShape->GetBezierC2() + delta );
282 break;
283 }
284 case 3:
285 {
286 VECTOR2I delta = arcPts[1] - bezPts[1];
287 bezShape->SetEnd( arcPts[1] );
288 bezShape->SetBezierC2( bezShape->GetBezierC2() + delta );
289 break;
290 }
291 }
292
293 success = true;
294 }
295 else if( ( shape0 == SHAPE_T::BEZIER && shape1 == SHAPE_T::SEGMENT )
296 || ( shape0 == SHAPE_T::SEGMENT && shape1 == SHAPE_T::BEZIER ) )
297 {
298 PCB_SHAPE* bezShape = shape0 == SHAPE_T::BEZIER ? aPrevShape : aShape;
299 PCB_SHAPE* segShape = shape0 == SHAPE_T::SEGMENT ? aPrevShape : aShape;
300
301 VECTOR2I bezPts[2] = { bezShape->GetStart(), bezShape->GetEnd() };
302 VECTOR2I segPts[2] = { segShape->GetStart(), segShape->GetEnd() };
303
304 SEG::ecoord d[4];
305 d[0] = ( segPts[0] - bezPts[0] ).SquaredEuclideanNorm();
306 d[1] = ( segPts[0] - bezPts[1] ).SquaredEuclideanNorm();
307 d[2] = ( segPts[1] - bezPts[0] ).SquaredEuclideanNorm();
308 d[3] = ( segPts[1] - bezPts[1] ).SquaredEuclideanNorm();
309
310 int idx = std::min_element( d, d + 4 ) - d;
311
312 switch( idx )
313 {
314 case 0: segShape->SetStart( bezPts[0] ); break;
315 case 1: segShape->SetStart( bezPts[1] ); break;
316 case 2: segShape->SetEnd( bezPts[0] ); break;
317 case 3: segShape->SetEnd( bezPts[1] ); break;
318 }
319
320 success = true;
321 }
322 else if( shape0 == SHAPE_T::BEZIER && shape1 == SHAPE_T::BEZIER )
323 {
324 PCB_SHAPE* bez0 = aPrevShape;
325 PCB_SHAPE* bez1 = aShape;
326
327 VECTOR2I pts0[2] = { bez0->GetStart(), bez0->GetEnd() };
328 VECTOR2I pts1[2] = { bez1->GetStart(), bez1->GetEnd() };
329
330 SEG::ecoord d[4];
331 d[0] = ( pts0[0] - pts1[0] ).SquaredEuclideanNorm();
332 d[1] = ( pts0[0] - pts1[1] ).SquaredEuclideanNorm();
333 d[2] = ( pts0[1] - pts1[0] ).SquaredEuclideanNorm();
334 d[3] = ( pts0[1] - pts1[1] ).SquaredEuclideanNorm();
335
336 int idx = std::min_element( d, d + 4 ) - d;
337 int i0 = idx / 2;
338 int i1 = idx % 2;
339 VECTOR2I middle = ( pts0[i0] + pts1[i1] ) / 2;
340
341 // Adjust first bezier curve
342 if( i0 == 0 )
343 {
344 VECTOR2I delta = middle - bez0->GetStart();
345 bez0->SetStart( middle );
346 bez0->SetBezierC1( bez0->GetBezierC1() + delta );
347 }
348 else
349 {
350 VECTOR2I delta = middle - bez0->GetEnd();
351 bez0->SetEnd( middle );
352 bez0->SetBezierC2( bez0->GetBezierC2() + delta );
353 }
354
355 // Adjust second bezier curve
356 if( i1 == 0 )
357 {
358 VECTOR2I delta = middle - bez1->GetStart();
359 bez1->SetStart( middle );
360 bez1->SetBezierC1( bez1->GetBezierC1() + delta );
361 }
362 else
363 {
364 VECTOR2I delta = middle - bez1->GetEnd();
365 bez1->SetEnd( middle );
366 bez1->SetBezierC2( bez1->GetBezierC2() + delta );
367 }
368
369 success = true;
370 }
371
372 return success;
373 };
374
375 PCB_SHAPE* graphic = nullptr;
376
377 std::set<PCB_SHAPE*> startCandidates;
378 for( PCB_SHAPE* shape : aShapeList )
379 {
380 if( shape->GetShape() == SHAPE_T::SEGMENT || shape->GetShape() == SHAPE_T::ARC
381 || shape->GetShape() == SHAPE_T::BEZIER )
382 {
383 shape->ClearFlags( SKIP_STRUCT );
384 startCandidates.emplace( shape );
385 }
386 }
387
388 while( startCandidates.size() )
389 {
390 graphic = *startCandidates.begin();
391
392 auto walkFrom = [&]( PCB_SHAPE* curr_graphic, VECTOR2I startPt )
393 {
394 VECTOR2I prevPt = startPt;
395
396 for( ;; )
397 {
398 // Get next closest segment.
399 PCB_SHAPE* nextGraphic =
400 findNext( curr_graphic, prevPt, kdTree, adaptor, aChainingEpsilon );
401
402 if( !nextGraphic )
403 break;
404
405 connectPair( curr_graphic, nextGraphic );
406
407 prevPt = closer_to_first( prevPt, nextGraphic->GetStart(), nextGraphic->GetEnd() )
408 ? nextGraphic->GetEnd()
409 : nextGraphic->GetStart();
410 curr_graphic = nextGraphic;
411 curr_graphic->SetFlags( SKIP_STRUCT );
412 startCandidates.erase( curr_graphic );
413 }
414 };
415
416 const VECTOR2I ptEnd = graphic->GetEnd();
417 const VECTOR2I ptStart = graphic->GetStart();
418
419 PCB_SHAPE* grAtEnd = findNext( graphic, ptEnd, kdTree, adaptor, aChainingEpsilon );
420 PCB_SHAPE* grAtStart = findNext( graphic, ptStart, kdTree, adaptor, aChainingEpsilon );
421
422 bool beginFromEndPt = true;
423
424 // We need to start walking from a point that is closest to a point of another shape.
425 if( grAtEnd && grAtStart )
426 {
427 SEG::ecoord dAtEnd = min_distance_sq( ptEnd, grAtEnd->GetStart(), grAtEnd->GetEnd() );
428
429 SEG::ecoord dAtStart =
430 min_distance_sq( ptStart, grAtStart->GetStart(), grAtStart->GetEnd() );
431
432 beginFromEndPt = dAtEnd <= dAtStart;
433 }
434 else if( grAtEnd )
435 beginFromEndPt = true;
436 else if( grAtStart )
437 beginFromEndPt = false;
438
439 if( beginFromEndPt )
440 {
441 // Do not inline GetEnd / GetStart as endpoints may update
442 walkFrom( graphic, graphic->GetEnd() );
443 walkFrom( graphic, graphic->GetStart() );
444 }
445 else
446 {
447 walkFrom( graphic, graphic->GetStart() );
448 walkFrom( graphic, graphic->GetEnd() );
449 }
450
451 startCandidates.erase( graphic );
452 }
453}
void SetFlags(EDA_ITEM_FLAGS aMask)
Definition eda_item.h:142
EDA_ITEM_FLAGS GetFlags() const
Definition eda_item.h:145
const VECTOR2I & GetBezierC2() const
Definition eda_shape.h:258
void SetBezierC2(const VECTOR2I &aPt)
Definition eda_shape.h:257
SHAPE_T GetShape() const
Definition eda_shape.h:168
const VECTOR2I & GetEnd() const
Return the ending point of the graphic.
Definition eda_shape.h:215
void SetStart(const VECTOR2I &aStart)
Definition eda_shape.h:177
const VECTOR2I & GetStart() const
Return the starting point of the graphic.
Definition eda_shape.h:173
void SetEnd(const VECTOR2I &aEnd)
Definition eda_shape.h:219
void SetBezierC1(const VECTOR2I &aPt)
Definition eda_shape.h:254
void SetArcGeometry(const VECTOR2I &aStart, const VECTOR2I &aMid, const VECTOR2I &aEnd)
Set the three controlling points for an arc.
const VECTOR2I & GetBezierC1() const
Definition eda_shape.h:255
VECTOR2I GetArcMid() const
Definition seg.h:42
VECTOR2I A
Definition seg.h:49
VECTOR2I::extended_type ecoord
Definition seg.h:44
VECTOR2I B
Definition seg.h:50
bool Intersects(const SEG &aSeg) const
Definition seg.cpp:431
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition seg.h:220
EDA_ANGLE Angle(const SEG &aOther) const
Determine the smallest angle between two segments.
Definition seg.cpp:102
nanoflann::KDTreeSingleIndexAdaptor< nanoflann::L2_Simple_Adaptor< double, PCB_SHAPE_ENDPOINTS_ADAPTOR >, PCB_SHAPE_ENDPOINTS_ADAPTOR, 2 > KDTree
static bool closer_to_first(VECTOR2I aRef, VECTOR2I aFirst, VECTOR2I aSecond)
Local method which qualifies whether the start or end point of a segment is closest to a point.
static constexpr EDA_ANGLE ANGLE_45
Definition eda_angle.h:412
#define SKIP_STRUCT
flag indicating that the structure should be ignored
SHAPE_T
Definition eda_shape.h:43
@ SEGMENT
Definition eda_shape.h:45
static PCB_SHAPE * findNext(PCB_SHAPE *aShape, const VECTOR2I &aPoint, const KDTree &kdTree, const PCB_SHAPE_ENDPOINTS_ADAPTOR &adaptor, double aChainingEpsilon)
Searches for a PCB_SHAPE matching a given end point or start point in a list.
void ConnectBoardShapes(std::vector< PCB_SHAPE * > &aShapeList, int aChainingEpsilon)
Connects shapes to each other, making continious contours (adjacent shapes will have a common vertex)...
std::optional< VECTOR2I > OPT_VECTOR2I
Definition seg.h:39
std::vector< std::pair< VECTOR2I, PCB_SHAPE * > > endpoints
bool kdtree_get_bbox(BBOX &) const
PCB_SHAPE_ENDPOINTS_ADAPTOR(const std::vector< PCB_SHAPE * > &shapes)
double kdtree_get_pt(const size_t idx, const size_t dim) const
int delta
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:695