KiCad PCB EDA Suite
geometry_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) 2018 Jean-Pierre Charras, jp.charras at wanadoo.fr
5  * Copyright (C) 1992-2018 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 
30 #include <eda_rect.h>
32 
33 int GetArcToSegmentCount( int aRadius, int aErrorMax, double aArcAngleDegree )
34 {
35  // calculate the number of segments to approximate a circle by segments
36  // given the max distance between the middle of a segment and the circle
37 
38  // error relative to the radius value:
39  double rel_error = (double)aErrorMax / aRadius;
40  // minimal arc increment in degrees:
41  double step = 180 / M_PI * acos( 1.0 - rel_error ) * 2;
42  // the minimal seg count for a arc
43  int segCount = round_nearest( fabs( aArcAngleDegree ) / step );
44 
45  // Ensure at least one segment is used
46  return std::max( segCount, 1 );
47 }
48 
49 
50 double GetCircletoPolyCorrectionFactor( int aSegCountforCircle )
51 {
52  /* calculates the coeff to compensate radius reduction of circle
53  * due to the segment approx.
54  * For a circle the min radius is radius * cos( 2PI / aSegCountforCircle / 2)
55  * this is the distance between the center and the middle of the segment.
56  * therfore, to move the middle of the segment to the circle (distance = radius)
57  * the correctionFactor is 1 /cos( PI/aSegCountforCircle )
58  */
59  if( aSegCountforCircle < 6 )
60  aSegCountforCircle = 6;
61  if( 1 || aSegCountforCircle > 64 )
62  return 1.0 / cos( M_PI / aSegCountforCircle );
63 }
64 
65 
66 /***
67  * Utility for the line clipping code, returns the boundary code of
68  * a point. Bit allocation is arbitrary
69  */
70 inline int clipOutCode( const EDA_RECT *aClipBox, int x, int y )
71 {
72  int code;
73  if( y < aClipBox->GetY() )
74  code = 2;
75  else if( y > aClipBox->GetBottom() )
76  code = 1;
77  else
78  code = 0;
79  if( x < aClipBox->GetX() )
80  code |= 4;
81  else if( x > aClipBox->GetRight() )
82  code |= 8;
83  return code;
84 }
85 
86 
87 bool ClipLine( const EDA_RECT *aClipBox, int &x1, int &y1, int &x2, int &y2 )
88 {
89  // Stock Cohen-Sutherland algorithm; check *any* CG book for details
90  int outcode1 = clipOutCode( aClipBox, x1, y1 );
91  int outcode2 = clipOutCode( aClipBox, x2, y2 );
92 
93  while( outcode1 || outcode2 )
94  {
95  // Fast reject
96  if( outcode1 & outcode2 )
97  return true;
98 
99  // Choose a side to clip
100  int thisoutcode, x, y;
101  if( outcode1 )
102  thisoutcode = outcode1;
103  else
104  thisoutcode = outcode2;
105 
106  /* One clip round
107  * Since we use the full range of 32 bit ints, the proportion
108  * computation has to be done in 64 bits to avoid horrible
109  * results */
110  if( thisoutcode & 1 ) // Clip the bottom
111  {
112  y = aClipBox->GetBottom();
113  x = x1 + (x2 - x1) * int64_t(y - y1) / (y2 - y1);
114  }
115  else if( thisoutcode & 2 ) // Clip the top
116  {
117  y = aClipBox->GetY();
118  x = x1 + (x2 - x1) * int64_t(y - y1) / (y2 - y1);
119  }
120  else if( thisoutcode & 8 ) // Clip the right
121  {
122  x = aClipBox->GetRight();
123  y = y1 + (y2 - y1) * int64_t(x - x1) / (x2 - x1);
124  }
125  else // if( thisoutcode & 4), obviously, clip the left
126  {
127  x = aClipBox->GetX();
128  y = y1 + (y2 - y1) * int64_t(x - x1) / (x2 - x1);
129  }
130 
131  // Put the result back and update the boundary code
132  // No ambiguity, otherwise it would have been a fast reject
133  if( thisoutcode == outcode1 )
134  {
135  x1 = x;
136  y1 = y;
137  outcode1 = clipOutCode( aClipBox, x1, y1 );
138  }
139  else
140  {
141  x2 = x;
142  y2 = y;
143  outcode2 = clipOutCode( aClipBox, x2, y2 );
144  }
145  }
146  return false;
147 }
148 
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
int clipOutCode(const EDA_RECT *aClipBox, int x, int y)
static int round_nearest(double v)
Definition: math_util.h:56
a few functions useful in geometry calculations.
int GetBottom() const
Definition: eda_rect.h:122
int GetRight() const
Definition: eda_rect.h:119
bool ClipLine(const EDA_RECT *aClipBox, int &x1, int &y1, int &x2, int &y2)
Test if any part of a line falls within the bounds of a rectangle.
#define max(a, b)
Definition: auxiliary.h:86
Class EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
int GetX() const
Definition: eda_rect.h:109
int GetY() const
Definition: eda_rect.h:110
double GetCircletoPolyCorrectionFactor(int aSegCountforCircle)