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 (C) 2024 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>
31#include <geometry/shape_rect.h>
32
33
35{
36 if( LexicographicalCompare( aSeg.A, aSeg.B ) <= 0 )
37 {
38 return aSeg;
39 }
40 return aSeg.Reversed();
41}
42
43
44const VECTOR2I& KIGEOM::GetOtherEnd( const SEG& aSeg, const VECTOR2I& aPoint )
45{
46 return ( aSeg.A == aPoint ) ? aSeg.B : aSeg.A;
47}
48
49
50OPT_VECTOR2I KIGEOM::GetSharedEndpoint( const SEG& aSegA, const SEG& aSegB )
51{
52 if( aSegA.A == aSegB.A || aSegA.A == aSegB.B )
53 {
54 return aSegA.A;
55 }
56 else if( aSegA.B == aSegB.A || aSegA.B == aSegB.B )
57 {
58 return aSegA.B;
59 }
60
61 return std::nullopt;
62}
63
64
65std::array<SEG, 4> KIGEOM::BoxToSegs( const BOX2I& aBox )
66{
67 const std::array<VECTOR2I, 4> corners = {
68 VECTOR2I{ aBox.GetLeft(), aBox.GetTop() },
69 VECTOR2I{ aBox.GetRight(), aBox.GetTop() },
70 VECTOR2I{ aBox.GetRight(), aBox.GetBottom() },
71 VECTOR2I{ aBox.GetLeft(), aBox.GetBottom() },
72 };
73
74 return {
75 SEG{ corners[0], corners[1] },
76 SEG{ corners[1], corners[2] },
77 SEG{ corners[2], corners[3] },
78 SEG{ corners[3], corners[0] },
79 };
80}
81
82
83std::vector<SEG> KIGEOM::GetSegsInDirection( const BOX2I& aBox, DIRECTION_45::Directions aDir )
84{
85 // clang-format off
86 switch( aDir )
87 {
89 return { SEG{ { aBox.GetLeft(), aBox.GetTop() },
90 { aBox.GetRight(), aBox.GetTop() } } };
92 return { SEG{ { aBox.GetRight(), aBox.GetTop() },
93 { aBox.GetRight(), aBox.GetBottom() } } };
95 return { SEG{ { aBox.GetLeft(), aBox.GetBottom() },
96 { aBox.GetRight(), aBox.GetBottom() } } };
98 return { SEG{ { aBox.GetLeft(), aBox.GetTop() },
99 { aBox.GetLeft(), aBox.GetBottom() } } };
101 return { SEG{ { aBox.GetLeft(), aBox.GetTop() },
102 { aBox.GetRight(), aBox.GetTop() } },
103 SEG{ { aBox.GetRight(), aBox.GetTop() },
104 { aBox.GetRight(), aBox.GetBottom() } } };
106 return { SEG{ { aBox.GetLeft(), aBox.GetBottom() },
107 { aBox.GetRight(), aBox.GetBottom() } },
108 SEG{ { aBox.GetRight(), aBox.GetTop() },
109 { aBox.GetRight(), aBox.GetBottom() } } };
111 return { SEG{ { aBox.GetLeft(), aBox.GetBottom() },
112 { aBox.GetRight(), aBox.GetBottom() } },
113 SEG{ { aBox.GetLeft(), aBox.GetTop() },
114 { aBox.GetLeft(), aBox.GetBottom() } } };
116 return { SEG{ { aBox.GetLeft(), aBox.GetTop() },
117 { aBox.GetRight(), aBox.GetTop() } },
118 SEG{ { aBox.GetLeft(), aBox.GetTop() },
119 { aBox.GetLeft(), aBox.GetBottom() } } };
122 }
123 // clang-format on
124
125 wxASSERT( false );
126 return {};
127};
128
129
130std::optional<SEG> KIGEOM::ClipHalfLineToBox( const HALF_LINE& aRay, const BOX2I& aBox )
131{
132 // Do the naive implementation - if this really is done in a tight loop,
133 // the Cohen-Sutherland implementation in ClipLine could be faster, but
134 // needs to be adapted to work with half-lines.
135 const std::array<SEG, 4> boxSegs = KIGEOM::BoxToSegs( aBox );
136
137 std::optional<VECTOR2I> ptA, ptB;
138
139 for( const SEG& boxSeg : boxSegs )
140 {
141 OPT_VECTOR2I intersection = aRay.Intersect( boxSeg );
142
143 if( !intersection )
144 {
145 continue;
146 }
147
148 // Init the first point or eat it if it's the same
149 if( !ptA || *intersection == *ptA )
150 {
151 ptA = *intersection;
152 }
153 else
154 {
155 ptB = *intersection;
156 }
157 }
158
159 // If we have exactly two intersections, the ray crossed twice
160 // so take the segment between the two points
161 if( ptA && ptB )
162 {
163 return SEG( *ptA, *ptB );
164 }
165
166 // It only crosses once, so the start is in the box. Take the segment from
167 // the start point to the intersection
168 if( ptA && *ptA != aRay.GetStart() )
169 {
170 return SEG( aRay.GetStart(), *ptA );
171 }
172
173 // It didn't cross at all
174 return std::nullopt;
175}
176
177
178std::optional<SEG> KIGEOM::ClipLineToBox( const LINE& aLine, const BOX2I& aBox )
179{
180 // As above, maybe can be optimised?
181 const std::array<SEG, 4> boxSegs = KIGEOM::BoxToSegs( aBox );
182
183 std::optional<VECTOR2I> ptA, ptB;
184
185 for( const SEG& boxSeg : boxSegs )
186 {
187 OPT_VECTOR2I intersection = aLine.Intersect( boxSeg );
188
189 // Reject intersections that are not on the actual box boundary
190 if( intersection && boxSeg.Contains( *intersection ) )
191 {
192 // Init the first point or eat it if it's the same
193 if( !ptA || *intersection == *ptA )
194 {
195 ptA = *intersection;
196 }
197 else
198 {
199 ptB = *intersection;
200 }
201 }
202 }
203
204 // If we have exactly two intersections, we have a segment
205 // (zero is no intersection, and one is a just crossing a corner exactly)
206 if( ptA && ptB )
207 {
208 return SEG( *ptA, *ptB );
209 }
210
211 return std::nullopt;
212}
213
214
216{
217 switch( aDir )
218 {
219 case DIRECTION_45::NW:
220 return SHAPE_ARC{
221 aCenter,
222 aCenter + VECTOR2I( -aRadius, 0 ),
223 ANGLE_90,
224 };
225 case DIRECTION_45::NE:
226 return SHAPE_ARC{
227 aCenter,
228 aCenter + VECTOR2I( 0, -aRadius ),
229 ANGLE_90,
230 };
231 case DIRECTION_45::SW:
232 return SHAPE_ARC{
233 aCenter,
234 aCenter + VECTOR2I( 0, aRadius ),
235 ANGLE_90,
236 };
237 case DIRECTION_45::SE:
238 return SHAPE_ARC{
239 aCenter,
240 aCenter + VECTOR2I( aRadius, 0 ),
241 ANGLE_90,
242 };
243 default: wxFAIL_MSG( "Invalid direction" ); return SHAPE_ARC();
244 }
245}
246
247
248SHAPE_ARC KIGEOM::MakeArcCw180( const VECTOR2I& aCenter, int aRadius,
250{
251 switch( aDir )
252 {
253 case DIRECTION_45::N:
254 return SHAPE_ARC{
255 aCenter,
256 aCenter + VECTOR2I( -aRadius, 0 ),
257 ANGLE_180,
258 };
259 case DIRECTION_45::E:
260 return SHAPE_ARC{
261 aCenter,
262 aCenter + VECTOR2I( 0, -aRadius ),
263 ANGLE_180,
264 };
265 case DIRECTION_45::S:
266 return SHAPE_ARC{
267 aCenter,
268 aCenter + VECTOR2I( aRadius, 0 ),
269 ANGLE_180,
270 };
271 case DIRECTION_45::W:
272 return SHAPE_ARC{
273 aCenter,
274 aCenter + VECTOR2I( 0, aRadius ),
275 ANGLE_180,
276 };
277 default: wxFAIL_MSG( "Invalid direction" );
278 }
279
280 return SHAPE_ARC();
281}
282
283
285{
286 const VECTOR2I nw = aRect.GetPosition();
287 switch( aDir )
288 {
289 // clang-format off
290 case DIRECTION_45::N:
291 return nw + VECTOR2I( aRect.GetWidth() / 2, -aOutset );
292 case DIRECTION_45::E:
293 return nw + VECTOR2I( aRect.GetWidth() + aOutset, aRect.GetHeight() / 2 );
294 case DIRECTION_45::S:
295 return nw + VECTOR2I( aRect.GetWidth() / 2, aRect.GetHeight() + aOutset );
296 case DIRECTION_45::W:
297 return nw + VECTOR2I( -aOutset, aRect.GetHeight() / 2 );
298 case DIRECTION_45::NW:
299 return nw + VECTOR2I( -aOutset, -aOutset );
300 case DIRECTION_45::NE:
301 return nw + VECTOR2I( aRect.GetWidth() + aOutset, -aOutset );
302 case DIRECTION_45::SW:
303 return nw + VECTOR2I( -aOutset, aRect.GetHeight() + aOutset );
304 case DIRECTION_45::SE:
305 return nw + VECTOR2I( aRect.GetWidth() + aOutset, aRect.GetHeight() + aOutset );
306 default:
307 wxFAIL_MSG( "Invalid direction" );
308 // clang-format on
309 }
310 return VECTOR2I();
311}
312
313
314std::vector<TYPED_POINT2I> KIGEOM::GetCircleKeyPoints( const CIRCLE& aCircle, bool aIncludeCenter )
315{
316 std::vector<TYPED_POINT2I> pts;
317
318 if( aIncludeCenter )
319 {
320 pts.emplace_back( VECTOR2I{ 0, 0 }, POINT_TYPE::PT_CENTER );
321 }
322
323 pts.emplace_back( VECTOR2I{ 0, aCircle.Radius }, POINT_TYPE::PT_QUADRANT );
324 pts.emplace_back( VECTOR2I{ aCircle.Radius, 0 }, POINT_TYPE::PT_QUADRANT );
325 pts.emplace_back( VECTOR2I{ 0, -aCircle.Radius }, POINT_TYPE::PT_QUADRANT );
326 pts.emplace_back( VECTOR2I{ -aCircle.Radius, 0 }, POINT_TYPE::PT_QUADRANT );
327
328 // Shift the points to the circle center
329 for( TYPED_POINT2I& pt : pts )
330 {
331 pt.m_point += aCircle.Center;
332 }
333
334 return pts;
335}
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:363
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:403
static constexpr EDA_ANGLE ANGLE_180
Definition: eda_angle.h:405
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.
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:50
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:83
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:34
std::array< SEG, 4 > BoxToSegs(const BOX2I &aBox)
Decompose a BOX2 into four segments.
Definition: shape_utils.cpp:65
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_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...
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:44
@ 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.
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:691
constexpr int LexicographicalCompare(const VECTOR2< T > &aA, const VECTOR2< T > &aB)
Definition: vector2d.h:640