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-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 <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 cant 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  // calculate the right common area coordinate:
165  int right = std::min( me.m_pos.x + me.m_size.x, rect.m_pos.x + rect.m_size.x );
166  // calculate the upper common area coordinate:
167  int top = std::max( me.m_pos.y, aRect.m_pos.y );
168  // calculate the lower common area coordinate:
169  int bottom = std::min( me.m_pos.y + me.m_size.y, rect.m_pos.y + rect.m_size.y );
170 
171  // if a common area exists, it must have a positive (null accepted) size
172  if( left <= right && top <= bottom )
173  rc = true;
174  else
175  rc = false;
176 
177  return rc;
178 }
179 
180 
181 bool EDA_RECT::Intersects( const EDA_RECT& aRect, double aRot ) const
182 {
183  if( !m_init )
184  return false;
185 
186  /* Most rectangles will be axis aligned.
187  * It is quicker to check for this case and pass the rect
188  * to the simpler intersection test
189  */
190 
191  // Prevent floating point comparison errors
192  static const double ROT_EPS = 0.000000001;
193 
194  static const double ROT_PARALLEL[] = { -3600, -1800, 0, 1800, 3600 };
195  static const double ROT_PERPENDICULAR[] = { -2700, -900, 0, 900, 2700 };
196 
197  NORMALIZE_ANGLE_POS<double>( aRot );
198 
199  // Test for non-rotated rectangle
200  for( int ii = 0; ii < 5; ii++ )
201  {
202  if( std::fabs( aRot - ROT_PARALLEL[ii] ) < ROT_EPS )
203  {
204  return Intersects( aRect );
205  }
206  }
207 
208  // Test for rectangle rotated by multiple of 90 degrees
209  for( int jj = 0; jj < 4; jj++ )
210  {
211  if( std::fabs( aRot - ROT_PERPENDICULAR[jj] ) < ROT_EPS )
212  {
213  EDA_RECT rotRect;
214 
215  // Rotate the supplied rect by 90 degrees
216  rotRect.SetOrigin( aRect.Centre() );
217  rotRect.Inflate( aRect.GetHeight(), aRect.GetWidth() );
218  return Intersects( rotRect );
219  }
220  }
221 
222  /* There is some non-orthogonal rotation.
223  * There are three cases to test:
224  * A) One point of this rect is inside the rotated rect
225  * B) One point of the rotated rect is inside this rect
226  * C) One of the sides of the rotated rect intersect this
227  */
228 
229  wxPoint corners[4];
230 
231  /* Test A : Any corners exist in rotated rect? */
232 
233  corners[0] = m_pos;
234  corners[1] = m_pos + wxPoint( m_size.x, 0 );
235  corners[2] = m_pos + wxPoint( m_size.x, m_size.y );
236  corners[3] = m_pos + wxPoint( 0, m_size.y );
237 
238  wxPoint rCentre = aRect.Centre();
239 
240  for( int i = 0; i < 4; i++ )
241  {
242  wxPoint delta = corners[i] - rCentre;
243  RotatePoint( &delta, -aRot );
244  delta += rCentre;
245 
246  if( aRect.Contains( delta ) )
247  {
248  return true;
249  }
250  }
251 
252  /* Test B : Any corners of rotated rect exist in this one? */
253  int w = aRect.GetWidth() / 2;
254  int h = aRect.GetHeight() / 2;
255 
256  // Construct corners around center of shape
257  corners[0] = wxPoint( -w, -h );
258  corners[1] = wxPoint( w, -h );
259  corners[2] = wxPoint( w, h );
260  corners[3] = wxPoint( -w, h );
261 
262  // Rotate and test each corner
263  for( int j = 0; j < 4; j++ )
264  {
265  RotatePoint( &corners[j], aRot );
266  corners[j] += rCentre;
267 
268  if( Contains( corners[j] ) )
269  {
270  return true;
271  }
272  }
273 
274  /* Test C : Any sides of rotated rect intersect this */
275 
276  if( Intersects( corners[0], corners[1] ) || Intersects( corners[1], corners[2] )
277  || Intersects( corners[2], corners[3] ) || Intersects( corners[3], corners[0] ) )
278  {
279  return true;
280  }
281 
282 
283  return false;
284 }
285 
286 
287 const wxPoint EDA_RECT::ClosestPointTo( const wxPoint& aPoint ) const
288 {
289  EDA_RECT me( *this );
290 
291  me.Normalize(); // ensure size is >= 0
292 
293  // Determine closest point to the circle centre within this rect
294  int nx = std::max( me.GetLeft(), std::min( aPoint.x, me.GetRight() ) );
295  int ny = std::max( me.GetTop(), std::min( aPoint.y, me.GetBottom() ) );
296 
297  return wxPoint( nx, ny );
298 }
299 
300 
301 const wxPoint EDA_RECT::FarthestPointTo( const wxPoint& aPoint ) const
302 {
303  EDA_RECT me( *this );
304 
305  me.Normalize(); // ensure size is >= 0
306 
307  int fx = std::max( std::abs( aPoint.x - me.GetLeft() ), std::abs( aPoint.x - me.GetRight() ) );
308  int fy = std::max( std::abs( aPoint.y - me.GetTop() ), std::abs( aPoint.y - me.GetBottom() ) );
309 
310  return wxPoint( fx, fy );
311 }
312 
313 
314 bool EDA_RECT::IntersectsCircle( const wxPoint& aCenter, const int aRadius ) const
315 {
316  if( !m_init )
317  return false;
318 
319  wxPoint closest = ClosestPointTo( aCenter );
320 
321  double dx = static_cast<double>( aCenter.x ) - closest.x;
322  double dy = static_cast<double>( aCenter.y ) - closest.y;
323 
324  double r = static_cast<double>( aRadius );
325 
326  return ( dx * dx + dy * dy ) <= ( r * r );
327 }
328 
329 
331  const wxPoint& aCenter, const int aRadius, const int aWidth ) const
332 {
333  if( !m_init )
334  return false;
335 
336  EDA_RECT me( *this );
337  me.Normalize(); // ensure size is >= 0
338 
339  // Test if the circle intersects at all
340  if( !IntersectsCircle( aCenter, aRadius + aWidth / 2 ) )
341  {
342  return false;
343  }
344 
345  wxPoint farpt = FarthestPointTo( aCenter );
346  // Farthest point must be further than the inside of the line
347  double fx = (double) farpt.x;
348  double fy = (double) farpt.y;
349 
350  double r = (double) aRadius - (double) aWidth / 2;
351 
352  return ( fx * fx + fy * fy ) > ( r * r );
353 }
354 
355 
357 {
358  Inflate( aDelta, aDelta );
359  return *this;
360 }
361 
362 
363 EDA_RECT& EDA_RECT::Inflate( wxCoord dx, wxCoord dy )
364 {
365  if( m_size.x >= 0 )
366  {
367  if( m_size.x < -2 * dx )
368  {
369  // Don't allow deflate to eat more width than we have,
370  m_pos.x += m_size.x / 2;
371  m_size.x = 0;
372  }
373  else
374  {
375  // The inflate is valid.
376  m_pos.x -= dx;
377  m_size.x += 2 * dx;
378  }
379  }
380  else // size.x < 0:
381  {
382  if( m_size.x > -2 * dx )
383  {
384  // Don't allow deflate to eat more width than we have,
385  m_pos.x -= m_size.x / 2;
386  m_size.x = 0;
387  }
388  else
389  {
390  // The inflate is valid.
391  m_pos.x += dx;
392  m_size.x -= 2 * dx; // m_Size.x <0: inflate when dx > 0
393  }
394  }
395 
396  if( m_size.y >= 0 )
397  {
398  if( m_size.y < -2 * dy )
399  {
400  // Don't allow deflate to eat more height than we have,
401  m_pos.y += m_size.y / 2;
402  m_size.y = 0;
403  }
404  else
405  {
406  // The inflate is valid.
407  m_pos.y -= dy;
408  m_size.y += 2 * dy;
409  }
410  }
411  else // size.y < 0:
412  {
413  if( m_size.y > 2 * dy )
414  {
415  // Don't allow deflate to eat more height than we have,
416  m_pos.y -= m_size.y / 2;
417  m_size.y = 0;
418  }
419  else
420  {
421  // The inflate is valid.
422  m_pos.y += dy;
423  m_size.y -= 2 * dy; // m_Size.y <0: inflate when dy > 0
424  }
425  }
426 
427  return *this;
428 }
429 
430 
431 void EDA_RECT::Merge( const EDA_RECT& aRect )
432 {
433  if( !m_init )
434  {
435  if( aRect.IsValid() )
436  {
437  m_pos = aRect.GetPosition();
438  m_size = aRect.GetSize();
439  m_init = true;
440  }
441  return;
442  }
443 
444  Normalize(); // ensure width and height >= 0
445  EDA_RECT rect = aRect;
446  rect.Normalize(); // ensure width and height >= 0
447  wxPoint end = GetEnd();
448  wxPoint rect_end = rect.GetEnd();
449 
450  // Change origin and size in order to contain the given rect
451  m_pos.x = std::min( m_pos.x, rect.m_pos.x );
452  m_pos.y = std::min( m_pos.y, rect.m_pos.y );
453  end.x = std::max( end.x, rect_end.x );
454  end.y = std::max( end.y, rect_end.y );
455  SetEnd( end );
456 }
457 
458 
459 void EDA_RECT::Merge( const wxPoint& aPoint )
460 {
461  if( !m_init )
462  {
463  m_pos = aPoint;
464  m_size = wxSize( 0, 0 );
465  m_init = true;
466  return;
467  }
468 
469  Normalize(); // ensure width and height >= 0
470 
471  wxPoint end = GetEnd();
472  // Change origin and size in order to contain the given rect
473  m_pos.x = std::min( m_pos.x, aPoint.x );
474  m_pos.y = std::min( m_pos.y, aPoint.y );
475  end.x = std::max( end.x, aPoint.x );
476  end.y = std::max( end.y, aPoint.y );
477  SetEnd( end );
478 }
479 
480 
481 double EDA_RECT::GetArea() const
482 {
483  return (double) GetWidth() * (double) GetHeight();
484 }
485 
486 
487 EDA_RECT EDA_RECT::Common( const EDA_RECT& aRect ) const
488 {
489  EDA_RECT r;
490 
491  if( Intersects( aRect ) )
492  {
493  wxPoint originA(
494  std::min( GetOrigin().x, GetEnd().x ), std::min( GetOrigin().y, GetEnd().y ) );
495  wxPoint originB( std::min( aRect.GetOrigin().x, aRect.GetEnd().x ),
496  std::min( aRect.GetOrigin().y, aRect.GetEnd().y ) );
497  wxPoint endA(
498  std::max( GetOrigin().x, GetEnd().x ), std::max( GetOrigin().y, GetEnd().y ) );
499  wxPoint endB( std::max( aRect.GetOrigin().x, aRect.GetEnd().x ),
500  std::max( aRect.GetOrigin().y, aRect.GetEnd().y ) );
501 
502  r.SetOrigin(
503  wxPoint( std::max( originA.x, originB.x ), std::max( originA.y, originB.y ) ) );
504  r.SetEnd( wxPoint( std::min( endA.x, endB.x ), std::min( endA.y, endB.y ) ) );
505  }
506 
507  return r;
508 }
509 
510 
511 const EDA_RECT EDA_RECT::GetBoundingBoxRotated( wxPoint aRotCenter, double aAngle ) const
512 {
513  wxPoint corners[4];
514 
515  // Build the corners list
516  corners[0] = GetOrigin();
517  corners[2] = GetEnd();
518  corners[1].x = corners[0].x;
519  corners[1].y = corners[2].y;
520  corners[3].x = corners[2].x;
521  corners[3].y = corners[0].y;
522 
523  // Rotate all corners, to find the bounding box
524  for( int ii = 0; ii < 4; ii++ )
525  RotatePoint( &corners[ii], aRotCenter, aAngle );
526 
527  // Find the corners bounding box
528  wxPoint start = corners[0];
529  wxPoint end = corners[0];
530 
531  for( int ii = 1; ii < 4; ii++ )
532  {
533  start.x = std::min( start.x, corners[ii].x );
534  start.y = std::min( start.y, corners[ii].y );
535  end.x = std::max( end.x, corners[ii].x );
536  end.y = std::max( end.y, corners[ii].y );
537  }
538 
539  EDA_RECT bbox;
540  bbox.SetOrigin( start );
541  bbox.SetEnd( end );
542 
543  return bbox;
544 }
void Move(const wxPoint &aMoveVector)
Function Move moves the rectangle by the aMoveVector.
Definition: eda_rect.cpp:51
void Merge(const EDA_RECT &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect.
Definition: eda_rect.cpp:431
const EDA_RECT GetBoundingBoxRotated(wxPoint aRotCenter, double aAngle) const
Function GetBoundingBoxRotated.
Definition: eda_rect.cpp:511
int GetTop() const
Definition: eda_rect.h:123
int GetLeft() const
Definition: eda_rect.h:122
int GetWidth() const
Definition: eda_rect.h:119
bool IntersectsCircle(const wxPoint &aCenter, const int aRadius) const
Function IntersectsCircle tests for a common area between a circle and this rectangle.
Definition: eda_rect.cpp:314
void SetOrigin(const wxPoint &pos)
Definition: eda_rect.h:131
bool IntersectsCircleEdge(const wxPoint &aCenter, const int aRadius, const int aWidth) const
IntersectsCircleEdge Tests for intersection between this rect and the edge (radius) of a circle.
Definition: eda_rect.cpp:330
EDA_RECT Common(const EDA_RECT &aRect) const
Function Common returns the area that is common with another rectangle.
Definition: eda_rect.cpp:487
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:208
bool Contains(const wxPoint &aPoint) const
Function Contains.
Definition: eda_rect.cpp:57
int GetBottom() const
Definition: eda_rect.h:124
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:116
const wxPoint GetOrigin() const
Definition: eda_rect.h:114
void SetEnd(int x, int y)
Definition: eda_rect.h:192
const wxPoint GetPosition() const
Definition: eda_rect.h:115
const wxPoint FarthestPointTo(const wxPoint &aPoint) const
Return the point in this rect that is farthest from the provided point.
Definition: eda_rect.cpp:301
int GetRight() const
Definition: eda_rect.h:121
double GetArea() const
Function GetArea returns the area of the rectangle.
Definition: eda_rect.cpp:481
int GetHeight() const
Definition: eda_rect.h:120
void Normalize()
Function Normalize ensures that the height ant width are positive.
Definition: eda_rect.cpp:35
wxPoint m_pos
Definition: eda_rect.h:47
wxSize m_size
Definition: eda_rect.h:48
bool m_init
Definition: eda_rect.h:49
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
wxPoint Centre() const
Definition: eda_rect.h:62
bool Intersects(const EDA_RECT &aRect) const
Function Intersects tests for a common area between rectangles.
Definition: eda_rect.cpp:150
bool IsValid() const
Definition: eda_rect.h:126
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:363
const wxSize GetSize() const
Definition: eda_rect.h:103
const wxPoint ClosestPointTo(const wxPoint &aPoint) const
Return the point in this rect that is closest to the provided point.
Definition: eda_rect.cpp:287