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-2019 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 <stdint.h> // for int64_t
31 #include <algorithm> // for max, min
32 
33 #include <eda_rect.h>
35 #include <math/util.h> // for KiROUND
36 
37 // To approximate a circle by segments, a minimal seg count is mandatory
38 #define MIN_SEGCOUNT_FOR_CIRCLE 6
39 
40 int GetArcToSegmentCount( int aRadius, int aErrorMax, double aArcAngleDegree )
41 {
42  // calculate the number of segments to approximate a circle by segments
43  // given the max distance between the middle of a segment and the circle
44 
45  // avoid divide-by-zero
46  aRadius = std::max( 1, aRadius );
47 
48  // error relative to the radius value:
49  double rel_error = (double)aErrorMax / aRadius;
50  // minimal arc increment in degrees:
51  double arc_increment = 180 / M_PI * acos( 1.0 - rel_error ) * 2;
52 
53  // Ensure a minimal arc increment reasonable value for a circle
54  // (360.0 degrees). For very small radius values, this is mandatory.
55  arc_increment = std::min( 360.0/MIN_SEGCOUNT_FOR_CIRCLE, arc_increment );
56 
57  int segCount = KiROUND( fabs( aArcAngleDegree ) / arc_increment );
58 
59  // Ensure at least one segment is used (can happen for small arcs)
60  return std::max( segCount, 1 );
61 }
62 
63 // When creating polygons to create a clearance polygonal area, the polygon must
64 // be same or bigger than the original shape.
65 // Polygons are bigger if the original shape has arcs (round rectangles, ovals, circles...)
66 // In some cases (in fact only one: when building layer solder mask) modifying
67 // shapes when converting them to polygons is not acceptable (the modification
68 // can break calculations)
69 // so one can disable the shape expansion by calling KeepPolyInsideShape( true )
70 // Important: calling KeepPolyInsideShape( false ) after calculations is
71 // mandatory to break oher calculations
72 static bool s_disable_arc_correction = false;
73 
74 // Enable (aInside = false) or disable (aInside = true) polygonal shape expansion
75 // when converting pads shapes and other items shapes to polygons:
76 void DisableArcRadiusCorrection( bool aDisable )
77 {
78  s_disable_arc_correction = aDisable;
79 }
80 
81 double GetCircletoPolyCorrectionFactor( int aSegCountforCircle )
82 {
83  /* calculates the coeff to compensate radius reduction of circle
84  * due to the segment approx.
85  * For a circle the min radius is radius * cos( 2PI / aSegCountforCircle / 2)
86  * this is the distance between the center and the middle of the segment.
87  * therefore, to move the middle of the segment to the circle (distance = radius)
88  * the correctionFactor is 1 /cos( PI/aSegCountforCircle )
89  */
90  aSegCountforCircle = std::max( MIN_SEGCOUNT_FOR_CIRCLE, aSegCountforCircle );
91  return s_disable_arc_correction ? 1.0 : 1.0 / cos( M_PI / aSegCountforCircle );
92 }
93 
94 
95 /***
96  * Utility for the line clipping code, returns the boundary code of
97  * a point. Bit allocation is arbitrary
98  */
99 inline int clipOutCode( const EDA_RECT *aClipBox, int x, int y )
100 {
101  int code;
102 
103  if( y < aClipBox->GetY() )
104  code = 2;
105  else if( y > aClipBox->GetBottom() )
106  code = 1;
107  else
108  code = 0;
109 
110  if( x < aClipBox->GetX() )
111  code |= 4;
112  else if( x > aClipBox->GetRight() )
113  code |= 8;
114 
115  return code;
116 }
117 
118 
119 bool ClipLine( const EDA_RECT *aClipBox, int &x1, int &y1, int &x2, int &y2 )
120 {
121  // Stock Cohen-Sutherland algorithm; check *any* CG book for details
122  int outcode1 = clipOutCode( aClipBox, x1, y1 );
123  int outcode2 = clipOutCode( aClipBox, x2, y2 );
124 
125  while( outcode1 || outcode2 )
126  {
127  // Fast reject
128  if( outcode1 & outcode2 )
129  return true;
130 
131  // Choose a side to clip
132  int thisoutcode, x, y;
133 
134  if( outcode1 )
135  thisoutcode = outcode1;
136  else
137  thisoutcode = outcode2;
138 
139  /* One clip round
140  * Since we use the full range of 32 bit ints, the proportion
141  * computation has to be done in 64 bits to avoid horrible
142  * results */
143  if( thisoutcode & 1 ) // Clip the bottom
144  {
145  y = aClipBox->GetBottom();
146  x = x1 + (x2 - x1) * int64_t(y - y1) / (y2 - y1);
147  }
148  else if( thisoutcode & 2 ) // Clip the top
149  {
150  y = aClipBox->GetY();
151  x = x1 + (x2 - x1) * int64_t(y - y1) / (y2 - y1);
152  }
153  else if( thisoutcode & 8 ) // Clip the right
154  {
155  x = aClipBox->GetRight();
156  y = y1 + (y2 - y1) * int64_t(x - x1) / (x2 - x1);
157  }
158  else // if( thisoutcode & 4), obviously, clip the left
159  {
160  x = aClipBox->GetX();
161  y = y1 + (y2 - y1) * int64_t(x - x1) / (x2 - x1);
162  }
163 
164  // Put the result back and update the boundary code
165  // No ambiguity, otherwise it would have been a fast reject
166  if( thisoutcode == outcode1 )
167  {
168  x1 = x;
169  y1 = y;
170  outcode1 = clipOutCode( aClipBox, x1, y1 );
171  }
172  else
173  {
174  x2 = x;
175  y2 = y;
176  outcode2 = clipOutCode( aClipBox, x2, y2 );
177  }
178  }
179  return false;
180 }
181 
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
int clipOutCode(const EDA_RECT *aClipBox, int x, int y)
int GetX() const
Definition: eda_rect.h:111
int GetBottom() const
Definition: eda_rect.h:124
int GetRight() const
Definition: eda_rect.h:121
static bool s_disable_arc_correction
#define MIN_SEGCOUNT_FOR_CIRCLE
a few functions useful in geometry calculations.
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.
void DisableArcRadiusCorrection(bool aDisable)
When creating polygons to create a clearance polygonal area, the polygon must be same or bigger than ...
EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
int GetY() const
Definition: eda_rect.h:112
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: util.h:68
double GetCircletoPolyCorrectionFactor(int aSegCountforCircle)