KiCad PCB EDA Suite
round_segment_2d.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) 2015-2016 Mario Luzeiro <[email protected]>
5  * Copyright (C) 1992-2020 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 
29 #include "round_segment_2d.h"
30 #include <wx/debug.h>
31 
32 
33 ROUND_SEGMENT_2D::ROUND_SEGMENT_2D( const SFVEC2F& aStart, const SFVEC2F& aEnd, float aWidth,
34  const BOARD_ITEM& aBoardItem ) :
35  OBJECT_2D( OBJECT_2D_TYPE::ROUNDSEG, aBoardItem ),
36  m_segment( aStart, aEnd )
37 {
38  wxASSERT( aStart != aEnd );
39 
40  m_radius = (aWidth / 2.0f);
42  m_width = aWidth;
43 
44  SFVEC2F leftRadiusOffset( -m_segment.m_Dir.y * m_radius, m_segment.m_Dir.x * m_radius );
45 
46  m_leftStart = aStart + leftRadiusOffset;
47  m_leftEnd = aEnd + leftRadiusOffset;
49  m_leftDir = glm::normalize( m_leftEndMinusStart );
50 
51  SFVEC2F rightRadiusOffset( -leftRadiusOffset.x, -leftRadiusOffset.y );
52  m_rightStart = aEnd + rightRadiusOffset;
53  m_rightEnd = aStart + rightRadiusOffset;
55  m_rightDir = glm::normalize( m_rightEndMinusStart );
56 
57  m_bbox.Reset();
58  m_bbox.Set( aStart, aEnd );
63 
64  wxASSERT( m_bbox.IsInitialized() );
65 }
66 
67 
68 bool ROUND_SEGMENT_2D::Intersects( const BBOX_2D& aBBox ) const
69 {
70  if( !m_bbox.Intersects( aBBox ) )
71  return false;
72 
73  if( ( aBBox.Max().x > m_bbox.Max().x ) && ( aBBox.Max().y > m_bbox.Max().y )
74  && ( aBBox.Min().x < m_bbox.Min().x ) && ( aBBox.Min().y < m_bbox.Min().y ) )
75  return true;
76 
77  SFVEC2F v[4];
78 
79  v[0] = aBBox.Min();
80  v[1] = SFVEC2F( aBBox.Min().x, aBBox.Max().y );
81  v[2] = aBBox.Max();
82  v[3] = SFVEC2F( aBBox.Max().x, aBBox.Min().y );
83 
84  // Test against the main rectangle segment
85  if( IntersectSegment( m_leftStart, m_leftEndMinusStart, v[0], v[1] - v[0] ) )
86  return true;
87 
88  if( IntersectSegment( m_leftStart, m_leftEndMinusStart, v[1], v[2] - v[1] ) )
89  return true;
90 
91  if( IntersectSegment( m_leftStart, m_leftEndMinusStart, v[2], v[3] - v[2] ) )
92  return true;
93 
94  if( IntersectSegment( m_leftStart, m_leftEndMinusStart, v[3], v[0] - v[3] ) )
95  return true;
96 
97  if( IntersectSegment( m_rightStart, m_rightEndMinusStart, v[0], v[1] - v[0] ) )
98  return true;
99 
100  if( IntersectSegment( m_rightStart, m_rightEndMinusStart, v[1], v[2] - v[1] ) )
101  return true;
102 
103  if( IntersectSegment( m_rightStart, m_rightEndMinusStart, v[2], v[3] - v[2] ) )
104  return true;
105 
106  if( IntersectSegment( m_rightStart, m_rightEndMinusStart, v[3], v[0] - v[3] ) )
107  return true;
108 
109  // Test the two circles
111  return true;
112 
114  return true;
115 
116  return false;
117 }
118 
119 
120 bool ROUND_SEGMENT_2D::Overlaps( const BBOX_2D& aBBox ) const
121 {
122  // NOT IMPLEMENTED
123  return false;
124 }
125 
126 
127 bool ROUND_SEGMENT_2D::Intersect( const RAYSEG2D& aSegRay, float* aOutT, SFVEC2F* aNormalOut ) const
128 {
129  const bool start_is_inside = IsPointInside( aSegRay.m_Start );
130  const bool end_is_inside = IsPointInside( aSegRay.m_End );
131 
132  // If segment if inside there are no hits
133  if( start_is_inside && end_is_inside )
134  return false;
135 
136  bool hitted = false;
137 
138  float closerHitT = FLT_MAX;
139  float farHitT = FLT_MAX;
140 
141  SFVEC2F closerHitNormal;
142  SFVEC2F farHitNormal;
143 
144  float leftSegT;
145  const bool leftSegmentHit =
146  aSegRay.IntersectSegment( m_leftStart, m_leftEndMinusStart, &leftSegT );
147 
148  if( leftSegmentHit )
149  {
150  hitted = true;
151  closerHitT = leftSegT;
152  farHitT = leftSegT;
153 
154  closerHitNormal = SFVEC2F( -m_leftDir.y, m_leftDir.x );
155  farHitNormal = SFVEC2F( -m_leftDir.y, m_leftDir.x );
156  }
157 
158  float rightSegT;
159  const bool rightSegmentHit =
160  aSegRay.IntersectSegment( m_rightStart, m_rightEndMinusStart, &rightSegT );
161 
162  if( rightSegmentHit )
163  {
164  if( !start_is_inside )
165  {
166  if( ( hitted == false ) || ( rightSegT < closerHitT ) )
167  {
168  closerHitT = rightSegT;
169  closerHitNormal = SFVEC2F( -m_rightDir.y, m_rightDir.x );
170  }
171  }
172  else
173  {
174  if( ( hitted == false ) || ( rightSegT > farHitT ) )
175  {
176  farHitT = rightSegT;
177  farHitNormal = SFVEC2F( -m_rightDir.y, m_rightDir.x );
178  }
179  }
180 
181  hitted = true;
182  }
183 
184  float circleStart_T0;
185  float circleStart_T1;
186  SFVEC2F circleStart_N0;
187  SFVEC2F circleStart_N1;
188 
189  const bool startCircleHit = aSegRay.IntersectCircle( m_segment.m_Start, m_radius,
190  &circleStart_T0, &circleStart_T1,
191  &circleStart_N0, &circleStart_N1 );
192 
193  if( startCircleHit )
194  {
195  if( circleStart_T0 > 0.0f )
196  {
197  if( !start_is_inside )
198  {
199  if( ( hitted == false ) || ( circleStart_T0 < closerHitT ) )
200  {
201  closerHitT = circleStart_T0;
202  closerHitNormal = circleStart_N0;
203  }
204  }
205  else
206  {
207  if( ( hitted == false ) || ( circleStart_T1 > farHitT ) )
208  {
209  farHitT = circleStart_T1;
210  farHitNormal = circleStart_N1;
211  }
212  }
213  }
214  else
215  {
216  // This can only happen if the ray starts inside
217  if( ( hitted == false ) || ( circleStart_T1 > farHitT ) )
218  {
219  farHitT = circleStart_T1;
220  farHitNormal = circleStart_N1;
221  }
222  }
223 
224  hitted = true;
225  }
226 
227  float circleEnd_T0;
228  float circleEnd_T1;
229  SFVEC2F circleEnd_N0;
230  SFVEC2F circleEnd_N1;
231 
232  const bool rightCircleHit = aSegRay.IntersectCircle( m_segment.m_End, m_radius,
233  &circleEnd_T0, &circleEnd_T1,
234  &circleEnd_N0, &circleEnd_N1 );
235  if( rightCircleHit )
236  {
237  if( circleEnd_T0 > 0.0f )
238  {
239  if( !start_is_inside )
240  {
241  if( ( hitted == false ) || ( circleEnd_T0 < closerHitT ) )
242  {
243  closerHitT = circleEnd_T0;
244  closerHitNormal = circleEnd_N0;
245  }
246  }
247  else
248  {
249  if( ( hitted == false ) || ( circleEnd_T1 > farHitT ) )
250  {
251  farHitT = circleEnd_T1;
252  farHitNormal = circleEnd_N1;
253  }
254  }
255  }
256  else
257  {
258  // This can only happen if the ray starts inside
259  if( ( hitted == false ) || ( circleEnd_T1 > farHitT ) )
260  {
261  farHitT = circleEnd_T1;
262  farHitNormal = circleEnd_N1;
263  }
264  }
265 
266  hitted = true;
267  }
268 
269  if( hitted )
270  {
271  if( !start_is_inside )
272  {
273  if( aOutT )
274  *aOutT = closerHitT;
275  //wxASSERT( (closerHitT > 0.0f) && (closerHitT <= 1.0f) );
276 
277  if( aNormalOut )
278  *aNormalOut = closerHitNormal;
279  }
280  else
281  {
282  wxASSERT( (farHitT >= 0.0f) && (farHitT <= 1.0f) );
283 
284  if( aOutT )
285  *aOutT = farHitT;
286 
287  if( aNormalOut )
288  *aNormalOut = -farHitNormal; // the normal started inside, so invert it
289  }
290  }
291 
292  return hitted;
293 }
294 
295 
297 {
298  if( !m_bbox.Intersects( aBBox ) )
300 
301  SFVEC2F v[4];
302 
303  v[0] = aBBox.Min();
304  v[1] = aBBox.Max();
305  v[2] = SFVEC2F( aBBox.Min().x, aBBox.Max().y );
306  v[3] = SFVEC2F( aBBox.Max().x, aBBox.Min().y );
307 
308  bool isInside[4];
309 
310  isInside[0] = IsPointInside( v[0] );
311  isInside[1] = IsPointInside( v[1] );
312  isInside[2] = IsPointInside( v[2] );
313  isInside[3] = IsPointInside( v[3] );
314 
315  // Check if all points are inside the circle
316  if( isInside[0] && isInside[1] && isInside[2] && isInside[3] )
318 
319  // Check if any point is inside the circle
320  if( isInside[0] || isInside[1] || isInside[2] || isInside[3] )
322 
324 }
325 
326 
327 bool ROUND_SEGMENT_2D::IsPointInside( const SFVEC2F& aPoint ) const
328 {
329  float dSquared = m_segment.DistanceToPointSquared( aPoint );
330 
331  if( dSquared <= m_radius_squared )
332  return true;
333 
334  return false;
335 }
BBOX_2D m_bbox
Definition: object_2d.h:110
bool Intersects(const BBOX_2D &aBBox) const override
a.Intersects(b) ⇔ !a.Disjoint(b) ⇔ !(a ∩ b = ∅)
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:49
SFVEC2F GetCenter() const
Definition: bbox_2d.cpp:119
void Set(const SFVEC2F &aPbMin, const SFVEC2F &aPbMax)
Set bounding box with new parameters.
Definition: bbox_2d.cpp:61
SFVEC2F m_rightEndMinusStart
bool IntersectCircle(const SFVEC2F &aCenter, float aRadius, float *aOutT0, float *aOutT1, SFVEC2F *aOutNormalT0, SFVEC2F *aOutNormalT1) const
Definition: ray.cpp:319
bool Overlaps(const BBOX_2D &aBBox) const override
Test if the box overlaps the object.
SFVEC2F m_Dir
Definition: ray.h:110
INTERSECTION_RESULT IsBBoxInside(const BBOX_2D &aBBox) const override
Test this object if it's completely outside, intersects, or is completely inside aBBox.
bool IsPointInside(const SFVEC2F &aPoint) const override
SFVEC2F m_centroid
Definition: object_2d.h:111
const SFVEC2F & Max() const
Definition: bbox_2d.h:172
glm::vec2 SFVEC2F
Definition: xv3d_types.h:42
INTERSECTION_RESULT
Definition: object_2d.h:36
void Reset()
Reset the bounding box to zero and uninitialize it.
Definition: bbox_2d.cpp:86
bool IntersectSegment(const SFVEC2F &aStart, const SFVEC2F &aEnd_minus_start, float *aOutT) const
Definition: ray.cpp:262
SFVEC2F m_End
Definition: ray.h:108
Manage a bounding box defined by two SFVEC2F min max points.
Definition: bbox_2d.h:41
SFVEC2F m_leftEndMinusStart
bool IntersectSegment(const SFVEC2F &aStartA, const SFVEC2F &aEnd_minus_startA, const SFVEC2F &aStartB, const SFVEC2F &aEnd_minus_startB)
Definition: ray.cpp:181
SFVEC2F m_Start
Definition: ray.h:107
const SFVEC2F & Min() const
Definition: bbox_2d.h:167
ROUND_SEGMENT_2D(const SFVEC2F &aStart, const SFVEC2F &aEnd, float aWidth, const BOARD_ITEM &aBoardItem)
bool Intersect(const RAYSEG2D &aSegRay, float *aOutT, SFVEC2F *aNormalOut) const override
float DistanceToPointSquared(const SFVEC2F &aPoint) const
Definition: ray.cpp:294
OBJECT_2D_TYPE
Definition: object_2d.h:44
bool Intersects(const BBOX_2D &aBBox) const
Test if a bounding box intersects this box.
Definition: bbox_2d.cpp:211
void ScaleNextUp()
Scale a bounding box to the next float representation making it larger.
Definition: bbox_2d.cpp:162
bool IsInitialized() const
Check if this bounding box is already initialized.
Definition: bbox_2d.cpp:79
Definition: ray.h:105