KiCad PCB EDA Suite
eda_rect.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 Jean-Pierre Charras, jaen-pierre.charras@gipsa-lab.inpg.com
5  * Copyright (C) 1992-2021 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 <algorithm>
30 #include <deque>
31 
32 #include <eda_rect.h>
33 #include <trigo.h>
34 
36 {
37  if( m_size.y < 0 )
38  {
39  m_size.y = -m_size.y;
40  m_pos.y -= m_size.y;
41  }
42 
43  if( m_size.x < 0 )
44  {
45  m_size.x = -m_size.x;
46  m_pos.x -= m_size.x;
47  }
48 }
49 
50 
51 void EDA_RECT::Move( const wxPoint& aMoveVector )
52 {
53  m_pos += aMoveVector;
54 }
55 
56 
57 bool EDA_RECT::Contains( const wxPoint& aPoint ) const
58 {
59  wxPoint rel_pos = aPoint - m_pos;
60  wxSize size = m_size;
61 
62  if( size.x < 0 )
63  {
64  size.x = -size.x;
65  rel_pos.x += size.x;
66  }
67 
68  if( size.y < 0 )
69  {
70  size.y = -size.y;
71  rel_pos.y += size.y;
72  }
73 
74  return ( rel_pos.x >= 0 ) && ( rel_pos.y >= 0 ) && ( rel_pos.y <= size.y )
75  && ( rel_pos.x <= size.x );
76 }
77 
78 
79 bool EDA_RECT::Contains( const EDA_RECT& aRect ) const
80 {
81  return Contains( aRect.GetOrigin() ) && Contains( aRect.GetEnd() );
82 }
83 
84 
85 bool EDA_RECT::Intersects( const wxPoint& aPoint1, const wxPoint& aPoint2 ) const
86 {
87  wxPoint point2, point4;
88 
89  if( Contains( aPoint1 ) || Contains( aPoint2 ) )
90  return true;
91 
92  point2.x = GetEnd().x;
93  point2.y = GetOrigin().y;
94  point4.x = GetOrigin().x;
95  point4.y = GetEnd().y;
96 
97  //Only need to test 3 sides since a straight line can't enter and exit on same side
98  if( SegmentIntersectsSegment( aPoint1, aPoint2, GetOrigin(), point2 ) )
99  return true;
100 
101  if( SegmentIntersectsSegment( aPoint1, aPoint2, point2, GetEnd() ) )
102  return true;
103 
104  if( SegmentIntersectsSegment( aPoint1, aPoint2, GetEnd(), point4 ) )
105  return true;
106 
107  return false;
108 }
109 
110 
111 bool EDA_RECT::Intersects( const wxPoint& aPoint1, const wxPoint& aPoint2, wxPoint* aIntersection1,
112  wxPoint* aIntersection2 ) const
113 {
114  wxPoint point2, point4;
115 
116  point2.x = GetEnd().x;
117  point2.y = GetOrigin().y;
118  point4.x = GetOrigin().x;
119  point4.y = GetEnd().y;
120 
121  bool intersects = false;
122 
123  wxPoint* aPointToFill = aIntersection1;
124 
125  if( SegmentIntersectsSegment( aPoint1, aPoint2, GetOrigin(), point2, aPointToFill ) )
126  intersects = true;
127 
128  if( intersects )
129  aPointToFill = aIntersection2;
130 
131  if( SegmentIntersectsSegment( aPoint1, aPoint2, point2, GetEnd(), aPointToFill ) )
132  intersects = true;
133 
134  if( intersects )
135  aPointToFill = aIntersection2;
136 
137  if( SegmentIntersectsSegment( aPoint1, aPoint2, GetEnd(), point4, aPointToFill ) )
138  intersects = true;
139 
140  if( intersects )
141  aPointToFill = aIntersection2;
142 
143  if( SegmentIntersectsSegment( aPoint1, aPoint2, point4, GetOrigin(), aPointToFill ) )
144  intersects = true;
145 
146  return intersects;
147 }
148 
149 
150 bool EDA_RECT::Intersects( const EDA_RECT& aRect ) const
151 {
152  if( !m_init )
153  return false;
154 
155  // this logic taken from wxWidgets' geometry.cpp file:
156  bool rc;
157  EDA_RECT me( *this );
158  EDA_RECT rect( aRect );
159  me.Normalize(); // ensure size is >= 0
160  rect.Normalize(); // ensure size is >= 0
161 
162  // calculate the left common area coordinate:
163  int left = std::max( me.m_pos.x, rect.m_pos.x );
164 
165  // calculate the right common area coordinate:
166  int right = std::min( me.m_pos.x + me.m_size.x, rect.m_pos.x + rect.m_size.x );
167 
168  // calculate the upper common area coordinate:
169  int top = std::max( me.m_pos.y, aRect.m_pos.y );
170 
171  // calculate the lower common area coordinate:
172  int bottom = std::min( me.m_pos.y + me.m_size.y, rect.m_pos.y + rect.m_size.y );
173 
174  // if a common area exists, it must have a positive (null accepted) size
175  if( left <= right && top <= bottom )
176  rc = true;
177  else
178  rc = false;
179 
180  return rc;
181 }
182 
183 
184 bool EDA_RECT::Intersects( const EDA_RECT& aRect, double aRot ) const
185 {
186  if( !m_init )
187  return false;
188 
189  /* Most rectangles will be axis aligned.
190  * It is quicker to check for this case and pass the rect
191  * to the simpler intersection test
192  */
193 
194  // Prevent floating point comparison errors
195  static const double ROT_EPS = 0.000000001;
196 
197  static const double ROT_PARALLEL[] = { -3600, -1800, 0, 1800, 3600 };
198  static const double ROT_PERPENDICULAR[] = { -2700, -900, 0, 900, 2700 };
199 
200  NORMALIZE_ANGLE_POS<double>( aRot );
201 
202  // Test for non-rotated rectangle
203  for( int ii = 0; ii < 5; ii++ )
204  {
205  if( std::fabs( aRot - ROT_PARALLEL[ii] ) < ROT_EPS )
206  {
207  return Intersects( aRect );
208  }
209  }
210 
211  // Test for rectangle rotated by multiple of 90 degrees
212  for( int jj = 0; jj < 4; jj++ )
213  {
214  if( std::fabs( aRot - ROT_PERPENDICULAR[jj] ) < ROT_EPS )
215  {
216  EDA_RECT rotRect;
217 
218  // Rotate the supplied rect by 90 degrees
219  rotRect.SetOrigin( aRect.Centre() );
220  rotRect.Inflate( aRect.GetHeight(), aRect.GetWidth() );
221  return Intersects( rotRect );
222  }
223  }
224 
225  /* There is some non-orthogonal rotation.
226  * There are three cases to test:
227  * A) One point of this rect is inside the rotated rect
228  * B) One point of the rotated rect is inside this rect
229  * C) One of the sides of the rotated rect intersect this
230  */
231 
232  wxPoint corners[4];
233 
234  /* Test A : Any corners exist in rotated rect? */
235  corners[0] = m_pos;
236  corners[1] = m_pos + wxPoint( m_size.x, 0 );
237  corners[2] = m_pos + wxPoint( m_size.x, m_size.y );
238  corners[3] = m_pos + wxPoint( 0, m_size.y );
239 
240  wxPoint rCentre = aRect.Centre();
241 
242  for( int i = 0; i < 4; i++ )
243  {
244  wxPoint delta = corners[i] - rCentre;
245  RotatePoint( &delta, -aRot );
246  delta += rCentre;
247 
248  if( aRect.Contains( delta ) )
249  {
250  return true;
251  }
252  }
253 
254  /* Test B : Any corners of rotated rect exist in this one? */
255  int w = aRect.GetWidth() / 2;
256  int h = aRect.GetHeight() / 2;
257 
258  // Construct corners around center of shape
259  corners[0] = wxPoint( -w, -h );
260  corners[1] = wxPoint( w, -h );
261  corners[2] = wxPoint( w, h );
262  corners[3] = wxPoint( -w, h );
263 
264  // Rotate and test each corner
265  for( int j = 0; j < 4; j++ )
266  {
267  RotatePoint( &corners[j], aRot );
268  corners[j] += rCentre;
269 
270  if( Contains( corners[j] ) )
271  {
272  return true;
273  }
274  }
275 
276  /* Test C : Any sides of rotated rect intersect this */
277  if( Intersects( corners[0], corners[1] ) || Intersects( corners[1], corners[2] )
278  || Intersects( corners[2], corners[3] ) || Intersects( corners[3], corners[0] ) )
279  {
280  return true;
281  }
282 
283 
284  return false;
285 }
286 
287 
288 const wxPoint EDA_RECT::ClosestPointTo( const wxPoint& aPoint ) const
289 {
290  EDA_RECT me( *this );
291 
292  me.Normalize(); // ensure size is >= 0
293 
294  // Determine closest point to the circle centre within this rect
295  int nx = std::max( me.GetLeft(), std::min( aPoint.x, me.GetRight() ) );
296  int ny = std::max( me.GetTop(), std::min( aPoint.y, me.GetBottom() ) );
297 
298  return wxPoint( nx, ny );
299 }
300 
301 
302 const wxPoint EDA_RECT::FarthestPointTo( const wxPoint& aPoint ) const
303 {
304  EDA_RECT me( *this );
305 
306  me.Normalize(); // ensure size is >= 0
307 
308  int fx = std::max( std::abs( aPoint.x - me.GetLeft() ), std::abs( aPoint.x - me.GetRight() ) );
309  int fy = std::max( std::abs( aPoint.y - me.GetTop() ), std::abs( aPoint.y - me.GetBottom() ) );
310 
311  return wxPoint( fx, fy );
312 }
313 
314 
315 bool EDA_RECT::IntersectsCircle( const wxPoint& aCenter, const int aRadius ) const
316 {
317  if( !m_init )
318  return false;
319 
320  wxPoint closest = ClosestPointTo( aCenter );
321 
322  double dx = static_cast<double>( aCenter.x ) - closest.x;
323  double dy = static_cast<double>( aCenter.y ) - closest.y;
324 
325  double r = static_cast<double>( aRadius );
326 
327  return ( dx * dx + dy * dy ) <= ( r * r );
328 }
329 
330 
331 bool EDA_RECT::IntersectsCircleEdge( const wxPoint& aCenter, const int aRadius,
332  const int aWidth ) const
333 {
334  if( !m_init )
335  return false;
336 
337  EDA_RECT me( *this );
338  me.Normalize(); // ensure size is >= 0
339 
340  // Test if the circle intersects at all
341  if( !IntersectsCircle( aCenter, aRadius + aWidth / 2 ) )
342  {
343  return false;
344  }
345 
346  wxPoint farpt = FarthestPointTo( aCenter );
347  // Farthest point must be further than the inside of the line
348  double fx = (double) farpt.x;
349  double fy = (double) farpt.y;
350 
351  double r = (double) aRadius - (double) aWidth / 2;
352 
353  return ( fx * fx + fy * fy ) > ( r * r );
354 }
355 
356 
358 {
359  Inflate( aDelta, aDelta );
360  return *this;
361 }
362 
363 
364 EDA_RECT& EDA_RECT::Inflate( wxCoord dx, wxCoord dy )
365 {
366  if( m_size.x >= 0 )
367  {
368  if( m_size.x < -2 * dx )
369  {
370  // Don't allow deflate to eat more width than we have,
371  m_pos.x += m_size.x / 2;
372  m_size.x = 0;
373  }
374  else
375  {
376  // The inflate is valid.
377  m_pos.x -= dx;
378  m_size.x += 2 * dx;
379  }
380  }
381  else // size.x < 0:
382  {
383  if( m_size.x > -2 * dx )
384  {
385  // Don't allow deflate to eat more width than we have,
386  m_pos.x -= m_size.x / 2;
387  m_size.x = 0;
388  }
389  else
390  {
391  // The inflate is valid.
392  m_pos.x += dx;
393  m_size.x -= 2 * dx; // m_Size.x <0: inflate when dx > 0
394  }
395  }
396 
397  if( m_size.y >= 0 )
398  {
399  if( m_size.y < -2 * dy )
400  {
401  // Don't allow deflate to eat more height than we have,
402  m_pos.y += m_size.y / 2;
403  m_size.y = 0;
404  }
405  else
406  {
407  // The inflate is valid.
408  m_pos.y -= dy;
409  m_size.y += 2 * dy;
410  }
411  }
412  else // size.y < 0:
413  {
414  if( m_size.y > 2 * dy )
415  {
416  // Don't allow deflate to eat more height than we have,
417  m_pos.y -= m_size.y / 2;
418  m_size.y = 0;
419  }
420  else
421  {
422  // The inflate is valid.
423  m_pos.y += dy;
424  m_size.y -= 2 * dy; // m_Size.y <0: inflate when dy > 0
425  }
426  }
427 
428  return *this;
429 }
430 
431 
432 void EDA_RECT::Merge( const EDA_RECT& aRect )
433 {
434  if( !m_init )
435  {
436  if( aRect.IsValid() )
437  {
438  m_pos = aRect.GetPosition();
439  m_size = aRect.GetSize();
440  m_init = true;
441  }
442  return;
443  }
444 
445  Normalize(); // ensure width and height >= 0
446  EDA_RECT rect = aRect;
447  rect.Normalize(); // ensure width and height >= 0
448  wxPoint end = GetEnd();
449  wxPoint rect_end = rect.GetEnd();
450 
451  // Change origin and size in order to contain the given rect
452  m_pos.x = std::min( m_pos.x, rect.m_pos.x );
453  m_pos.y = std::min( m_pos.y, rect.m_pos.y );
454  end.x = std::max( end.x, rect_end.x );
455  end.y = std::max( end.y, rect_end.y );
456  SetEnd( end );
457 }
458 
459 
460 void EDA_RECT::Merge( const wxPoint& aPoint )
461 {
462  if( !m_init )
463  {
464  m_pos = aPoint;
465  m_size = wxSize( 0, 0 );
466  m_init = true;
467  return;
468  }
469 
470  Normalize(); // ensure width and height >= 0
471 
472  wxPoint end = GetEnd();
473 
474  // Change origin and size in order to contain the given rect
475  m_pos.x = std::min( m_pos.x, aPoint.x );
476  m_pos.y = std::min( m_pos.y, aPoint.y );
477  end.x = std::max( end.x, aPoint.x );
478  end.y = std::max( end.y, aPoint.y );
479  SetEnd( end );
480 }
481 
482 
483 double EDA_RECT::GetArea() const
484 {
485  return (double) GetWidth() * (double) GetHeight();
486 }
487 
488 
489 EDA_RECT EDA_RECT::Common( const EDA_RECT& aRect ) const
490 {
491  EDA_RECT r;
492 
493  if( Intersects( aRect ) )
494  {
495  wxPoint originA(
496  std::min( GetOrigin().x, GetEnd().x ), std::min( GetOrigin().y, GetEnd().y ) );
497  wxPoint originB( std::min( aRect.GetOrigin().x, aRect.GetEnd().x ),
498  std::min( aRect.GetOrigin().y, aRect.GetEnd().y ) );
499  wxPoint endA(
500  std::max( GetOrigin().x, GetEnd().x ), std::max( GetOrigin().y, GetEnd().y ) );
501  wxPoint endB( std::max( aRect.GetOrigin().x, aRect.GetEnd().x ),
502  std::max( aRect.GetOrigin().y, aRect.GetEnd().y ) );
503 
504  r.SetOrigin(
505  wxPoint( std::max( originA.x, originB.x ), std::max( originA.y, originB.y ) ) );
506  r.SetEnd( wxPoint( std::min( endA.x, endB.x ), std::min( endA.y, endB.y ) ) );
507  }
508 
509  return r;
510 }
511 
512 
513 const EDA_RECT EDA_RECT::GetBoundingBoxRotated( const wxPoint& aRotCenter, double aAngle ) const
514 {
515  wxPoint corners[4];
516 
517  // Build the corners list
518  corners[0] = GetOrigin();
519  corners[2] = GetEnd();
520  corners[1].x = corners[0].x;
521  corners[1].y = corners[2].y;
522  corners[3].x = corners[2].x;
523  corners[3].y = corners[0].y;
524 
525  // Rotate all corners, to find the bounding box
526  for( int ii = 0; ii < 4; ii++ )
527  RotatePoint( &corners[ii], aRotCenter, aAngle );
528 
529  // Find the corners bounding box
530  wxPoint start = corners[0];
531  wxPoint end = corners[0];
532 
533  for( int ii = 1; ii < 4; ii++ )
534  {
535  start.x = std::min( start.x, corners[ii].x );
536  start.y = std::min( start.y, corners[ii].y );
537  end.x = std::max( end.x, corners[ii].x );
538  end.y = std::max( end.y, corners[ii].y );
539  }
540 
541  EDA_RECT bbox;
542  bbox.SetOrigin( start );
543  bbox.SetEnd( end );
544 
545  return bbox;
546 }
void Move(const wxPoint &aMoveVector)
Move the rectangle by the aMoveVector.
Definition: eda_rect.cpp:51
void Merge(const EDA_RECT &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: eda_rect.cpp:432
int GetTop() const
Definition: eda_rect.h:113
int GetLeft() const
Definition: eda_rect.h:112
int GetWidth() const
Definition: eda_rect.h:109
bool IntersectsCircle(const wxPoint &aCenter, const int aRadius) const
Test for a common area between a circle and this rectangle.
Definition: eda_rect.cpp:315
void SetOrigin(const wxPoint &pos)
Definition: eda_rect.h:121
bool IntersectsCircleEdge(const wxPoint &aCenter, const int aRadius, const int aWidth) const
Test for intersection between this rect and the edge (radius) of a circle.
Definition: eda_rect.cpp:331
EDA_RECT Common(const EDA_RECT &aRect) const
Return the area that is common with another rectangle.
Definition: eda_rect.cpp:489
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:228
bool Contains(const wxPoint &aPoint) const
Definition: eda_rect.cpp:57
int GetBottom() const
Definition: eda_rect.h:114
bool SegmentIntersectsSegment(const wxPoint &a_p1_l1, const wxPoint &a_p2_l1, const wxPoint &a_p1_l2, const wxPoint &a_p2_l2, wxPoint *aIntersectionPoint=nullptr)
Test if two lines intersect.
Definition: trigo.cpp:61
const wxPoint GetEnd() const
Definition: eda_rect.h:103
const wxPoint GetOrigin() const
Definition: eda_rect.h:101
void SetEnd(int x, int y)
Definition: eda_rect.h:182
const wxPoint GetPosition() const
Definition: eda_rect.h:102
const wxPoint FarthestPointTo(const wxPoint &aPoint) const
Return the point in this rect that is farthest from the provided point.
Definition: eda_rect.cpp:302
int GetRight() const
Definition: eda_rect.h:111
double GetArea() const
Return the area of the rectangle.
Definition: eda_rect.cpp:483
int GetHeight() const
Definition: eda_rect.h:110
void Normalize()
Ensures that the height ant width are positive.
Definition: eda_rect.cpp:35
wxPoint m_pos
Definition: eda_rect.h:348
wxSize m_size
Definition: eda_rect.h:349
bool m_init
Definition: eda_rect.h:350
Handle the component boundary box.
Definition: eda_rect.h:42
wxPoint Centre() const
Definition: eda_rect.h:55
bool Intersects(const EDA_RECT &aRect) const
Test for a common area between rectangles.
Definition: eda_rect.cpp:150
bool IsValid() const
Definition: eda_rect.h:116
const EDA_RECT GetBoundingBoxRotated(const wxPoint &aRotCenter, double aAngle) const
Useful to calculate bounding box of rotated items, when rotation if not k*90 degrees.
Definition: eda_rect.cpp:513
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:364
const wxSize GetSize() const
Definition: eda_rect.h:91
const wxPoint ClosestPointTo(const wxPoint &aPoint) const
Return the point in this rect that is closest to the provided point.
Definition: eda_rect.cpp:288