KiCad PCB EDA Suite
Loading...
Searching...
No Matches
shape_utils.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 The 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 2
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/old-licenses/gpl-2.0.html
19 * or you may search the http://www.gnu.org website for the version 2 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
25
26#include <geometry/circle.h>
27#include <geometry/seg.h>
28#include <geometry/half_line.h>
29#include <geometry/line.h>
32#include <geometry/shape_rect.h>
33
34
36{
37 if( LexicographicalCompare( aSeg.A, aSeg.B ) <= 0 )
38 {
39 return aSeg;
40 }
41 return aSeg.Reversed();
42}
43
44
45const VECTOR2I& KIGEOM::GetOtherEnd( const SEG& aSeg, const VECTOR2I& aPoint )
46{
47 return ( aSeg.A == aPoint ) ? aSeg.B : aSeg.A;
48}
49
50
51OPT_VECTOR2I KIGEOM::GetSharedEndpoint( const SEG& aSegA, const SEG& aSegB )
52{
53 if( aSegA.A == aSegB.A || aSegA.A == aSegB.B )
54 {
55 return aSegA.A;
56 }
57 else if( aSegA.B == aSegB.A || aSegA.B == aSegB.B )
58 {
59 return aSegA.B;
60 }
61
62 return std::nullopt;
63}
64
65
66std::array<SEG, 4> KIGEOM::BoxToSegs( const BOX2I& aBox )
67{
68 const std::array<VECTOR2I, 4> corners = {
69 VECTOR2I{ aBox.GetLeft(), aBox.GetTop() },
70 VECTOR2I{ aBox.GetRight(), aBox.GetTop() },
71 VECTOR2I{ aBox.GetRight(), aBox.GetBottom() },
72 VECTOR2I{ aBox.GetLeft(), aBox.GetBottom() },
73 };
74
75 return {
76 SEG{ corners[0], corners[1] },
77 SEG{ corners[1], corners[2] },
78 SEG{ corners[2], corners[3] },
79 SEG{ corners[3], corners[0] },
80 };
81}
82
83
84void KIGEOM::CollectBoxCorners( const BOX2I& aBox, std::vector<VECTOR2I>& aCorners )
85{
86 aCorners.push_back( { aBox.GetLeft(), aBox.GetTop() } );
87 aCorners.push_back( { aBox.GetRight(), aBox.GetTop() } );
88 aCorners.push_back( { aBox.GetRight(), aBox.GetBottom() } );
89 aCorners.push_back( { aBox.GetLeft(), aBox.GetBottom() } );
90}
91
92
93std::vector<SEG> KIGEOM::GetSegsInDirection( const BOX2I& aBox, DIRECTION_45::Directions aDir )
94{
95 // clang-format off
96 switch( aDir )
97 {
99 return { SEG{ { aBox.GetLeft(), aBox.GetTop() },
100 { aBox.GetRight(), aBox.GetTop() } } };
102 return { SEG{ { aBox.GetRight(), aBox.GetTop() },
103 { aBox.GetRight(), aBox.GetBottom() } } };
105 return { SEG{ { aBox.GetLeft(), aBox.GetBottom() },
106 { aBox.GetRight(), aBox.GetBottom() } } };
108 return { SEG{ { aBox.GetLeft(), aBox.GetTop() },
109 { aBox.GetLeft(), aBox.GetBottom() } } };
111 return { SEG{ { aBox.GetLeft(), aBox.GetTop() },
112 { aBox.GetRight(), aBox.GetTop() } },
113 SEG{ { aBox.GetRight(), aBox.GetTop() },
114 { aBox.GetRight(), aBox.GetBottom() } } };
116 return { SEG{ { aBox.GetLeft(), aBox.GetBottom() },
117 { aBox.GetRight(), aBox.GetBottom() } },
118 SEG{ { aBox.GetRight(), aBox.GetTop() },
119 { aBox.GetRight(), aBox.GetBottom() } } };
121 return { SEG{ { aBox.GetLeft(), aBox.GetBottom() },
122 { aBox.GetRight(), aBox.GetBottom() } },
123 SEG{ { aBox.GetLeft(), aBox.GetTop() },
124 { aBox.GetLeft(), aBox.GetBottom() } } };
126 return { SEG{ { aBox.GetLeft(), aBox.GetTop() },
127 { aBox.GetRight(), aBox.GetTop() } },
128 SEG{ { aBox.GetLeft(), aBox.GetTop() },
129 { aBox.GetLeft(), aBox.GetBottom() } } };
132 }
133 // clang-format on
134
135 wxASSERT( false );
136 return {};
137};
138
139
140std::optional<SEG> KIGEOM::ClipHalfLineToBox( const HALF_LINE& aRay, const BOX2I& aBox )
141{
142 // Do the naive implementation - if this really is done in a tight loop,
143 // the Cohen-Sutherland implementation in ClipLine could be faster, but
144 // needs to be adapted to work with half-lines.
145 const std::array<SEG, 4> boxSegs = KIGEOM::BoxToSegs( aBox );
146
147 std::optional<VECTOR2I> ptA, ptB;
148
149 for( const SEG& boxSeg : boxSegs )
150 {
151 OPT_VECTOR2I intersection = aRay.Intersect( boxSeg );
152
153 if( !intersection )
154 {
155 continue;
156 }
157
158 // Init the first point or eat it if it's the same
159 if( !ptA || *intersection == *ptA )
160 {
161 ptA = *intersection;
162 }
163 else
164 {
165 ptB = *intersection;
166 }
167 }
168
169 // If we have exactly two intersections, the ray crossed twice
170 // so take the segment between the two points
171 if( ptA && ptB )
172 {
173 return SEG( *ptA, *ptB );
174 }
175
176 // It only crosses once, so the start is in the box. Take the segment from
177 // the start point to the intersection
178 if( ptA && *ptA != aRay.GetStart() )
179 {
180 return SEG( aRay.GetStart(), *ptA );
181 }
182
183 // It didn't cross at all
184 return std::nullopt;
185}
186
187
188std::optional<SEG> KIGEOM::ClipLineToBox( const LINE& aLine, const BOX2I& aBox )
189{
190 // As above, maybe can be optimised?
191 const std::array<SEG, 4> boxSegs = KIGEOM::BoxToSegs( aBox );
192
193 std::optional<VECTOR2I> ptA, ptB;
194
195 for( const SEG& boxSeg : boxSegs )
196 {
197 OPT_VECTOR2I intersection = aLine.Intersect( boxSeg );
198
199 // Reject intersections that are not on the actual box boundary
200 if( intersection && boxSeg.Contains( *intersection ) )
201 {
202 // Init the first point or eat it if it's the same
203 if( !ptA || *intersection == *ptA )
204 {
205 ptA = *intersection;
206 }
207 else
208 {
209 ptB = *intersection;
210 }
211 }
212 }
213
214 // If we have exactly two intersections, we have a segment
215 // (zero is no intersection, and one is a just crossing a corner exactly)
216 if( ptA && ptB )
217 {
218 return SEG( *ptA, *ptB );
219 }
220
221 return std::nullopt;
222}
223
224
226{
227 switch( aDir )
228 {
229 case DIRECTION_45::NW:
230 return SHAPE_ARC{
231 aCenter,
232 aCenter + VECTOR2I( -aRadius, 0 ),
233 ANGLE_90,
234 };
235 case DIRECTION_45::NE:
236 return SHAPE_ARC{
237 aCenter,
238 aCenter + VECTOR2I( 0, -aRadius ),
239 ANGLE_90,
240 };
241 case DIRECTION_45::SW:
242 return SHAPE_ARC{
243 aCenter,
244 aCenter + VECTOR2I( 0, aRadius ),
245 ANGLE_90,
246 };
247 case DIRECTION_45::SE:
248 return SHAPE_ARC{
249 aCenter,
250 aCenter + VECTOR2I( aRadius, 0 ),
251 ANGLE_90,
252 };
253 default: wxFAIL_MSG( "Invalid direction" ); return SHAPE_ARC();
254 }
255}
256
257
258SHAPE_ARC KIGEOM::MakeArcCw180( const VECTOR2I& aCenter, int aRadius,
260{
261 switch( aDir )
262 {
263 case DIRECTION_45::N:
264 return SHAPE_ARC{
265 aCenter,
266 aCenter + VECTOR2I( -aRadius, 0 ),
267 ANGLE_180,
268 };
269 case DIRECTION_45::E:
270 return SHAPE_ARC{
271 aCenter,
272 aCenter + VECTOR2I( 0, -aRadius ),
273 ANGLE_180,
274 };
275 case DIRECTION_45::S:
276 return SHAPE_ARC{
277 aCenter,
278 aCenter + VECTOR2I( aRadius, 0 ),
279 ANGLE_180,
280 };
281 case DIRECTION_45::W:
282 return SHAPE_ARC{
283 aCenter,
284 aCenter + VECTOR2I( 0, aRadius ),
285 ANGLE_180,
286 };
287 default: wxFAIL_MSG( "Invalid direction" );
288 }
289
290 return SHAPE_ARC();
291}
292
293
295{
296 const VECTOR2I nw = aRect.GetPosition();
297 switch( aDir )
298 {
299 // clang-format off
300 case DIRECTION_45::N:
301 return nw + VECTOR2I( aRect.GetWidth() / 2, -aOutset );
302 case DIRECTION_45::E:
303 return nw + VECTOR2I( aRect.GetWidth() + aOutset, aRect.GetHeight() / 2 );
304 case DIRECTION_45::S:
305 return nw + VECTOR2I( aRect.GetWidth() / 2, aRect.GetHeight() + aOutset );
306 case DIRECTION_45::W:
307 return nw + VECTOR2I( -aOutset, aRect.GetHeight() / 2 );
308 case DIRECTION_45::NW:
309 return nw + VECTOR2I( -aOutset, -aOutset );
310 case DIRECTION_45::NE:
311 return nw + VECTOR2I( aRect.GetWidth() + aOutset, -aOutset );
312 case DIRECTION_45::SW:
313 return nw + VECTOR2I( -aOutset, aRect.GetHeight() + aOutset );
314 case DIRECTION_45::SE:
315 return nw + VECTOR2I( aRect.GetWidth() + aOutset, aRect.GetHeight() + aOutset );
316 default:
317 wxFAIL_MSG( "Invalid direction" );
318 // clang-format on
319 }
320 return VECTOR2I();
321}
322
323
324std::vector<TYPED_POINT2I> KIGEOM::GetCircleKeyPoints( const CIRCLE& aCircle, bool aIncludeCenter )
325{
326 std::vector<TYPED_POINT2I> pts;
327
328 if( aIncludeCenter )
329 {
330 pts.emplace_back( VECTOR2I{ 0, 0 }, POINT_TYPE::PT_CENTER );
331 }
332
333 pts.emplace_back( VECTOR2I{ 0, aCircle.Radius }, POINT_TYPE::PT_QUADRANT );
334 pts.emplace_back( VECTOR2I{ aCircle.Radius, 0 }, POINT_TYPE::PT_QUADRANT );
335 pts.emplace_back( VECTOR2I{ 0, -aCircle.Radius }, POINT_TYPE::PT_QUADRANT );
336 pts.emplace_back( VECTOR2I{ -aCircle.Radius, 0 }, POINT_TYPE::PT_QUADRANT );
337
338 // Shift the points to the circle center
339 for( TYPED_POINT2I& pt : pts )
340 {
341 pt.m_point += aCircle.Center;
342 }
343
344 return pts;
345}
346
347
349{
350 SHAPE_LINE_CHAIN raOutline;
351
352 const auto handleSegment = [&]( const SEG& aSeg )
353 {
354 const VECTOR2I p0( aSeg.A.x, aSeg.B.y );
355 const VECTOR2I p1( aSeg.B.x, aSeg.A.y );
356
357 raOutline.Append( aSeg.A );
358 if( !aPoly.PointInside( p0 ) )
359 raOutline.Append( p0 );
360 else
361 raOutline.Append( p1 );
362 };
363
364 for( int i = 0; i < aPoly.SegmentCount(); i++ )
365 {
366 handleSegment( aPoly.CSegment( i ) );
367 }
368
369 // Manually handle the last segment if not closed
370 if( !aPoly.IsClosed() && aPoly.PointCount() >= 2 )
371 {
372 handleSegment( SEG( aPoly.CLastPoint(), aPoly.CPoint( 0 ) ) );
373 }
374
375 raOutline.SetClosed( true );
376 raOutline.Simplify();
377
378 return raOutline;
379}
380
381
383{
384 if( aHole.PointCount() < 3 || aHole.Area() == 0 )
385 {
386 return false;
387 }
388
389 aOutline.AddHole( std::move( aHole ) );
390 return true;
391}
392
393
394std::vector<VECTOR2I> KIGEOM::MakeRegularPolygonPoints( const VECTOR2I& aCenter, size_t aN,
395 const VECTOR2I& aPt0 )
396{
397 VECTOR2D pt0FromC = aPt0 - aCenter;
398 std::vector<VECTOR2I> pts;
399
400 for( size_t i = 0; i < aN; i++ )
401 {
402 VECTOR2D pt = GetRotated( pt0FromC, ( FULL_CIRCLE / double( aN ) ) * i );
403 pts.push_back( KiROUND( pt + aCenter ) );
404 }
405
406 return pts;
407}
408
409
410std::vector<VECTOR2I> KIGEOM::MakeRegularPolygonPoints( const VECTOR2I& aCenter, size_t aN,
411 int aRadius, bool aAcrossCorners,
412 EDA_ANGLE aAngle )
413{
414 if( !aAcrossCorners )
415 {
416 // if across flats, increase the radius
417 aRadius = aRadius / ( FULL_CIRCLE / ( aN * 2 ) ).Cos();
418 }
419
420 const VECTOR2I pt0 = aCenter + GetRotated( VECTOR2I{ aRadius, 0 }, aAngle );
421 return KIGEOM::MakeRegularPolygonPoints( aCenter, aN, pt0 );
422}
423
424
425std::vector<SEG> KIGEOM::MakeCrossSegments( const VECTOR2I& aCenter, const VECTOR2I& aSize,
426 EDA_ANGLE aAngle )
427{
428 std::vector<SEG> segs;
429
430 VECTOR2I pt0 = aCenter - GetRotated( VECTOR2I{ aSize.x / 2, 0 }, aAngle );
431 segs.emplace_back( pt0, aCenter - ( pt0 - aCenter ) );
432
433 pt0 = aCenter - GetRotated( VECTOR2I{ 0, aSize.y / 2 }, aAngle );
434 segs.emplace_back( pt0, aCenter - ( pt0 - aCenter ) );
435
436 return segs;
437}
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
Definition: box2.h:990
constexpr coord_type GetLeft() const
Definition: box2.h:228
constexpr coord_type GetRight() const
Definition: box2.h:217
constexpr coord_type GetTop() const
Definition: box2.h:229
constexpr coord_type GetBottom() const
Definition: box2.h:222
Represent basic circle geometry with utility geometry functions.
Definition: circle.h:33
VECTOR2I Center
Public to make access simpler.
Definition: circle.h:130
int Radius
Public to make access simpler.
Definition: circle.h:129
Directions
Available directions, there are 8 of them, as on a rectilinear map (north = up) + an extra undefined ...
Definition: direction45.h:49
OPT_VECTOR2I Intersect(const SEG &aSeg) const
Definition: half_line.cpp:57
const VECTOR2I & GetStart() const
Get the start point of the ray.
Definition: half_line.h:57
Definition: line.h:36
OPT_VECTOR2I Intersect(const SEG &aOther) const
Definition: line.cpp:22
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I B
Definition: seg.h:50
SEG Reversed() const
Returns the center point of the line.
Definition: seg.h:373
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
bool IsClosed() const override
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Simplify(int aTolerance=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
int SegmentCount() const
Return the number of segments in this line chain.
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
Represent a set of closed polygons.
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index.
const VECTOR2I & GetPosition() const
Definition: shape_rect.h:160
int GetWidth() const
Definition: shape_rect.h:176
int GetHeight() const
Definition: shape_rect.h:184
static constexpr EDA_ANGLE ANGLE_90
Definition: eda_angle.h:413
static constexpr EDA_ANGLE FULL_CIRCLE
Definition: eda_angle.h:409
static constexpr EDA_ANGLE ANGLE_180
Definition: eda_angle.h:415
bool AddHoleIfValid(SHAPE_POLY_SET &aOutline, SHAPE_LINE_CHAIN &&aHole)
Adds a hole to a polygon if it is valid (i.e.
VECTOR2I GetPoint(const SHAPE_RECT &aRect, DIRECTION_45::Directions aDir, int aOutset=0)
Get the point on a rectangle that corresponds to a given direction.
std::vector< TYPED_POINT2I > GetCircleKeyPoints(const CIRCLE &aCircle, bool aIncludeCenter)
Get key points of an CIRCLE.
std::vector< VECTOR2I > MakeRegularPolygonPoints(const VECTOR2I &aCenter, size_t aN, const VECTOR2I &aPt0)
Get the corners of a regular polygon from the centre, one point and the number of sides.
OPT_VECTOR2I GetSharedEndpoint(const SEG &aSegA, const SEG &aSegB)
Get the shared endpoint of two segments, if it exists, or std::nullopt if the segments are not connec...
Definition: shape_utils.cpp:51
std::vector< SEG > GetSegsInDirection(const BOX2I &aBox, DIRECTION_45::Directions aDir)
Get the segments of a box that are in the given direction.
Definition: shape_utils.cpp:93
SEG NormalisedSeg(const SEG &aSeg)
Returns a SEG such that the start point is smaller or equal in x and y compared to the end point.
Definition: shape_utils.cpp:35
std::vector< SEG > MakeCrossSegments(const VECTOR2I &aCenter, const VECTOR2I &aSize, EDA_ANGLE aAngle)
Create the two segments for a cross.
std::array< SEG, 4 > BoxToSegs(const BOX2I &aBox)
Decompose a BOX2 into four segments.
Definition: shape_utils.cpp:66
std::optional< SEG > ClipHalfLineToBox(const HALF_LINE &aRay, const BOX2I &aBox)
Get the segment of a half-line that is inside a box, if any.
std::optional< SEG > ClipLineToBox(const LINE &aLine, const BOX2I &aBox)
Get the segment of a line that is inside a box, if any.
SHAPE_ARC MakeArcCw180(const VECTOR2I &aCenter, int aRadius, DIRECTION_45::Directions aDir)
Get a SHAPE_ARC representing a 180-degree arc in the clockwise direction with the midpoint in the giv...
SHAPE_LINE_CHAIN RectifyPolygon(const SHAPE_LINE_CHAIN &aPoly)
SHAPE_ARC MakeArcCw90(const VECTOR2I &aCenter, int aRadius, DIRECTION_45::Directions aDir)
Get a SHAPE_ARC representing a 90-degree arc in the clockwise direction with the midpoint in the give...
void CollectBoxCorners(const BOX2I &aBox, std::vector< VECTOR2I > &aCorners)
Add the 4 corners of a BOX2I to a vector.
Definition: shape_utils.cpp:84
const VECTOR2I & GetOtherEnd(const SEG &aSeg, const VECTOR2I &aPoint)
Get the end point of the segment that is not the given point.
Definition: shape_utils.cpp:45
@ PT_CENTER
The point is the center of something.
Definition: point_types.h:46
@ PT_QUADRANT
The point is on a quadrant of a circle (N, E, S, W points).
Definition: point_types.h:58
std::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
Utility functions for working with shapes.
VECTOR2I GetRotated(const VECTOR2I &aVector, const EDA_ANGLE &aAngle)
Return a new VECTOR2I that is the result of rotating aVector by aAngle.
Definition: trigo.h:77
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:695
constexpr int LexicographicalCompare(const VECTOR2< T > &aA, const VECTOR2< T > &aB)
Definition: vector2d.h:644