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 (C) 2023 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 <pcb_shape.h>
29#include <geometry/circle.h>
30
31
41static PCB_SHAPE* findNext( PCB_SHAPE* aShape, const VECTOR2I& aPoint,
42 const std::vector<PCB_SHAPE*>& aList, unsigned aLimit )
43{
44 // Look for an unused, exact hit
45 for( PCB_SHAPE* graphic : aList )
46 {
47 if( graphic == aShape || ( graphic->GetFlags() & SKIP_STRUCT ) != 0 )
48 continue;
49
50 if( aPoint == graphic->GetStart() || aPoint == graphic->GetEnd() )
51 return graphic;
52 }
53
54 // Search again for anything that's close.
55 VECTOR2I pt( aPoint );
56 SEG::ecoord closest_dist_sq = SEG::Square( aLimit );
57 PCB_SHAPE* closest_graphic = nullptr;
58 SEG::ecoord d_sq;
59
60 for( PCB_SHAPE* graphic : aList )
61 {
62 if( graphic == aShape || ( graphic->GetFlags() & SKIP_STRUCT ) != 0 )
63 continue;
64
65 d_sq = ( pt - graphic->GetStart() ).SquaredEuclideanNorm();
66
67 if( d_sq < closest_dist_sq )
68 {
69 closest_dist_sq = d_sq;
70 closest_graphic = graphic;
71 }
72
73 d_sq = ( pt - graphic->GetEnd() ).SquaredEuclideanNorm();
74
75 if( d_sq < closest_dist_sq )
76 {
77 closest_dist_sq = d_sq;
78 closest_graphic = graphic;
79 }
80 }
81
82 return closest_graphic; // Note: will be nullptr if nothing within aLimit
83}
84
85
86void ConnectBoardShapes( std::vector<PCB_SHAPE*>& aShapeList,
87 std::vector<std::unique_ptr<PCB_SHAPE>>& aNewShapes, int aChainingEpsilon )
88{
89 if( aShapeList.size() == 0 )
90 return;
91
92#if 0
93 // Not used, but not removed, just in case
94 auto close_enough = []( const VECTOR2I& aLeft, const VECTOR2I& aRight, unsigned aLimit ) -> bool
95 {
96 return ( aLeft - aRight ).SquaredEuclideanNorm() <= SEG::Square( aLimit );
97 };
98#endif
99
100 auto closer_to_first = []( const VECTOR2I& aRef, const VECTOR2I& aFirst,
101 const VECTOR2I& aSecond ) -> bool
102 {
103 return ( aRef - aFirst ).SquaredEuclideanNorm() < ( aRef - aSecond ).SquaredEuclideanNorm();
104 };
105
106 auto min_distance_sq = []( const VECTOR2I& aRef, const VECTOR2I& aFirst,
107 const VECTOR2I& aSecond ) -> SEG::ecoord
108 {
109 return std::min( ( aRef - aFirst ).SquaredEuclideanNorm(),
110 ( aRef - aSecond ).SquaredEuclideanNorm() );
111 };
112
113 auto addSegment = [&]( const VECTOR2I start, const VECTOR2I end, int width, PCB_LAYER_ID layer )
114 {
115 // Ensure null shapes are not added
116 if( start == end )
117 return;
118
119 std::unique_ptr<PCB_SHAPE> seg = std::make_unique<PCB_SHAPE>( nullptr, SHAPE_T::SEGMENT );
120 seg->SetStart( start );
121 seg->SetEnd( end );
122 seg->SetWidth( width );
123 seg->SetLayer( layer );
124
125 aNewShapes.emplace_back( std::move( seg ) );
126 };
127
128 auto connectPair = [&]( PCB_SHAPE* aPrevShape, PCB_SHAPE* aShape )
129 {
130 bool success = false;
131
132 SHAPE_T shape0 = aPrevShape->GetShape();
133 SHAPE_T shape1 = aShape->GetShape();
134
135 if( shape0 == SHAPE_T::SEGMENT && shape1 == SHAPE_T::SEGMENT )
136 {
137 SEG seg0( aPrevShape->GetStart(), aPrevShape->GetEnd() );
138 SEG seg1( aShape->GetStart(), aShape->GetEnd() );
139
140 if( seg0.Intersects( seg1 ) || seg0.Angle( seg1 ) > ANGLE_45 )
141 {
142 if( OPT_VECTOR2I inter = seg0.IntersectLines( seg1 ) )
143 {
144 if( closer_to_first( *inter, seg0.A, seg0.B ) )
145 aPrevShape->SetStart( *inter );
146 else
147 aPrevShape->SetEnd( *inter );
148
149 if( closer_to_first( *inter, seg1.A, seg1.B ) )
150 aShape->SetStart( *inter );
151 else
152 aShape->SetEnd( *inter );
153
154 success = true;
155 }
156 }
157 }
158 else if( ( shape0 == SHAPE_T::ARC && shape1 == SHAPE_T::SEGMENT )
159 || ( shape0 == SHAPE_T::SEGMENT && shape1 == SHAPE_T::ARC ) )
160 {
161 PCB_SHAPE* arcShape = shape0 == SHAPE_T::ARC ? aPrevShape : aShape;
162 PCB_SHAPE* segShape = shape0 == SHAPE_T::SEGMENT ? aPrevShape : aShape;
163
164 SHAPE_ARC arc =
165 SHAPE_ARC( arcShape->GetStart(), arcShape->GetArcMid(), arcShape->GetEnd(), 0 );
166
167 EDA_ANGLE extAngle( 20, DEGREES_T );
168 if( arc.IsClockwise() )
169 extAngle = -extAngle;
170
171 VECTOR2D arcStart = arc.GetP0();
172 EDA_ANGLE arcAngle = arc.GetCentralAngle();
173
174 RotatePoint( arcStart, arc.GetCenter(), extAngle );
175 arcAngle += extAngle * 2;
176
177 arcAngle = std::clamp( arcAngle, -ANGLE_360, ANGLE_360 );
178
179 SHAPE_ARC extarc( arc.GetCenter(), arcStart, arcAngle );
180 SEG seg( segShape->GetStart(), segShape->GetEnd() );
181
182 std::vector<VECTOR2I> ips;
183 std::vector<VECTOR2I> onSeg;
184 extarc.IntersectLine( seg, &ips );
185
186 for( const VECTOR2I& ip : ips )
187 {
188 if( min_distance_sq( ip, segShape->GetStart(), segShape->GetEnd() ) <= 0
189 && min_distance_sq( ip, arcShape->GetStart(), arcShape->GetEnd() ) <= 0 )
190 {
191 // Already connected
192 continue;
193 }
194
195 if( seg.Distance( ip ) <= aChainingEpsilon )
196 {
197 if( closer_to_first( ip, seg.A, seg.B ) )
198 segShape->SetStart( ip );
199 else
200 segShape->SetEnd( ip );
201
202 // Move points in the actual PCB_SHAPE
203 if( closer_to_first( ip, arc.GetP0(), arc.GetP1() ) )
204 arcShape->SetArcGeometry( ip, arc.GetArcMid(), arc.GetP1() );
205 else
206 arcShape->SetArcGeometry( arc.GetP0(), arc.GetArcMid(), ip );
207
208 // Reconstruct the arc shape - we may have more than 1 intersection
209 arc = SHAPE_ARC( arcShape->GetStart(), arcShape->GetArcMid(),
210 arcShape->GetEnd(), 0 );
211
212 success = true;
213 break;
214 }
215 }
216
217 if( !success )
218 {
219 // Try to avoid acute angles
220 VECTOR2I lineProj = seg.LineProject( arc.GetCenter() );
221 bool intersectsPerp = seg.SquaredDistance( lineProj ) <= 0;
222
223 if( intersectsPerp )
224 {
225 if( closer_to_first( lineProj, seg.A, seg.B ) )
226 segShape->SetStart( lineProj );
227 else
228 segShape->SetEnd( lineProj );
229
230 CIRCLE circ( arc.GetCenter(), arc.GetRadius() );
231 VECTOR2I circProj = circ.NearestPoint( lineProj );
232
233 if( closer_to_first( circProj, arc.GetP0(), arc.GetP1() ) )
234 arcShape->SetArcGeometry( circProj, arc.GetArcMid(), arc.GetP1() );
235 else
236 arcShape->SetArcGeometry( arc.GetP0(), arc.GetArcMid(), circProj );
237
238 addSegment( circProj, lineProj, segShape->GetWidth(), segShape->GetLayer() );
239 success = true;
240 }
241 }
242 }
243
244 return success;
245 };
246
247 PCB_SHAPE* graphic = nullptr;
248
249 std::set<PCB_SHAPE*> startCandidates;
250 for( PCB_SHAPE* shape : aShapeList )
251 {
252 if( shape->GetShape() == SHAPE_T::SEGMENT || shape->GetShape() == SHAPE_T::ARC
253 || shape->GetShape() == SHAPE_T::BEZIER )
254 {
255 shape->ClearFlags( SKIP_STRUCT );
256 startCandidates.emplace( shape );
257 }
258 }
259
260 while( startCandidates.size() )
261 {
262 graphic = *startCandidates.begin();
263
264 auto walkFrom = [&]( PCB_SHAPE* curr_graphic, VECTOR2I startPt )
265 {
266 VECTOR2I prevPt = startPt;
267
268 for( ;; )
269 {
270 // Get next closest segment.
271 PCB_SHAPE* nextGraphic =
272 findNext( curr_graphic, prevPt, aShapeList, aChainingEpsilon );
273
274 if( !nextGraphic )
275 break;
276
277 VECTOR2I nstart = nextGraphic->GetStart();
278 VECTOR2I nend = nextGraphic->GetEnd();
279
280 if( !closer_to_first( prevPt, nstart, nend ) )
281 std::swap( nstart, nend );
282
283 if( !connectPair( curr_graphic, nextGraphic ) )
284 addSegment( prevPt, nstart, curr_graphic->GetWidth(),
285 curr_graphic->GetLayer() );
286
287 // Shape might've changed
288 nstart = nextGraphic->GetStart();
289 nend = nextGraphic->GetEnd();
290
291 if( !closer_to_first( prevPt, nstart, nend ) )
292 std::swap( nstart, nend );
293
294 prevPt = nend;
295 curr_graphic = nextGraphic;
296 curr_graphic->SetFlags( SKIP_STRUCT );
297 startCandidates.erase( curr_graphic );
298 }
299 };
300
301 const VECTOR2I ptEnd = graphic->GetEnd();
302 const VECTOR2I ptStart = graphic->GetStart();
303
304 PCB_SHAPE* grAtEnd = findNext( graphic, ptEnd, aShapeList, aChainingEpsilon );
305 PCB_SHAPE* grAtStart = findNext( graphic, ptStart, aShapeList, aChainingEpsilon );
306
307 bool beginFromEndPt = true;
308
309 // We need to start walking from a point that is closest to a point of another shape.
310 if( grAtEnd && grAtStart )
311 {
312 SEG::ecoord dAtEnd = min_distance_sq( ptEnd, grAtEnd->GetStart(), grAtEnd->GetEnd() );
313
314 SEG::ecoord dAtStart =
315 min_distance_sq( ptStart, grAtStart->GetStart(), grAtStart->GetEnd() );
316
317 beginFromEndPt = dAtEnd <= dAtStart;
318 }
319 else if( grAtEnd )
320 beginFromEndPt = true;
321 else if( grAtStart )
322 beginFromEndPt = false;
323
324 if( beginFromEndPt )
325 {
326 // Do not inline GetEnd / GetStart as endpoints may update
327 walkFrom( graphic, graphic->GetEnd() );
328 walkFrom( graphic, graphic->GetStart() );
329 }
330 else
331 {
332 walkFrom( graphic, graphic->GetStart() );
333 walkFrom( graphic, graphic->GetEnd() );
334 }
335
336 startCandidates.erase( graphic );
337 }
338}
Represent basic circle geometry with utility geometry functions.
Definition: circle.h:33
VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute the point on the circumference of the circle that is the closest to aP.
Definition: circle.cpp:197
void SetFlags(EDA_ITEM_FLAGS aMask)
Definition: eda_item.h:126
void ClearFlags(EDA_ITEM_FLAGS aMask=EDA_ITEM_ALL_FLAGS)
Definition: eda_item.h:128
SHAPE_T GetShape() const
Definition: eda_shape.h:125
const VECTOR2I & GetEnd() const
Return the ending point of the graphic.
Definition: eda_shape.h:167
void SetStart(const VECTOR2I &aStart)
Definition: eda_shape.h:134
const VECTOR2I & GetStart() const
Return the starting point of the graphic.
Definition: eda_shape.h:130
void SetEnd(const VECTOR2I &aEnd)
Definition: eda_shape.h:171
void SetArcGeometry(const VECTOR2I &aStart, const VECTOR2I &aMid, const VECTOR2I &aEnd)
Set the three controlling points for an arc.
Definition: eda_shape.cpp:651
VECTOR2I GetArcMid() const
Definition: eda_shape.cpp:589
int GetWidth() const override
Definition: pcb_shape.cpp:367
PCB_LAYER_ID GetLayer() const override
Return the primary layer this item is on.
Definition: pcb_shape.h:70
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:75
VECTOR2I::extended_type ecoord
Definition: seg.h:44
VECTOR2I B
Definition: seg.h:50
bool Intersects(const SEG &aSeg) const
Definition: seg.cpp:190
static SEG::ecoord Square(int a)
Definition: seg.h:123
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:210
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:329
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.cpp:312
EDA_ANGLE Angle(const SEG &aOther) const
Determine the smallest angle between two segments.
Definition: seg.cpp:97
EDA_ANGLE GetCentralAngle() const
Definition: shape_arc.cpp:520
const VECTOR2I & GetArcMid() const
Definition: shape_arc.h:115
bool IsClockwise() const
Definition: shape_arc.h:263
const VECTOR2I & GetP1() const
Definition: shape_arc.h:114
int IntersectLine(const SEG &aSeg, std::vector< VECTOR2I > *aIpsBuffer) const
Find intersection points between this arc and aSeg, treating aSeg as an infinite line.
Definition: shape_arc.cpp:295
double GetRadius() const
Definition: shape_arc.cpp:536
const VECTOR2I & GetP0() const
Definition: shape_arc.h:113
const VECTOR2I & GetCenter() const
Definition: shape_arc.cpp:505
static bool close_enough(VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit)
Local and tunable method of qualifying the proximity of two points.
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.
@ DEGREES_T
Definition: eda_angle.h:31
static constexpr EDA_ANGLE ANGLE_45
Definition: eda_angle.h:402
static constexpr EDA_ANGLE ANGLE_360
Definition: eda_angle.h:407
#define SKIP_STRUCT
flag indicating that the structure should be ignored
SHAPE_T
Definition: eda_shape.h:42
@ ARC
use RECTANGLE instead of RECT to avoid collision in a Windows header
static PCB_SHAPE * findNext(PCB_SHAPE *aShape, const VECTOR2I &aPoint, const std::vector< PCB_SHAPE * > &aList, unsigned aLimit)
Searches for a PCB_SHAPE matching a given end point or start point in a list.
void ConnectBoardShapes(std::vector< PCB_SHAPE * > &aShapeList, std::vector< std::unique_ptr< PCB_SHAPE > > &aNewShapes, int aChainingEpsilon)
Connects shapes to each other, making continious contours (adjacent shapes will have a common vertex)...
PCB_LAYER_ID
A quick note on layer IDs:
Definition: layer_ids.h:60
static bool addSegment(VRML_LAYER &model, IDF_SEGMENT *seg, int icont, int iseg)
std::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Calculate the new point of coord coord pX, pY, for a rotation center 0, 0.
Definition: trigo.cpp:228