KiCad PCB EDA Suite
zone_filling_algorithm.cpp
Go to the documentation of this file.
1 
5 /*
6  * This program source code file is part of KiCad, a free EDA CAD application.
7  *
8  * Copyright (C) 2016 Jean-Pierre Charras, jp.charras at wanadoo.fr
9  * Copyright (C) 1992-2016 KiCad Developers, see AUTHORS.txt for contributors.
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, you may find one here:
23  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
24  * or you may search the http://www.gnu.org website for the version 2 license,
25  * or you may write to the Free Software Foundation, Inc.,
26  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
27  */
28 
29 
30 #include <algorithm> // sort
31 
32 #include <fctsys.h>
33 #include <trigo.h>
34 #include <wxPcbStruct.h>
36 
37 #include <class_zone.h>
38 
39 #include <pcbnew.h>
40 #include <zones.h>
41 
42 /* Build the filled solid areas data from real outlines (stored in m_Poly)
43  * The solid areas can be more than one on copper layers, and do not have holes
44  ( holes are linked by overlapping segments to the main outline)
45  * aPcb: the current board (can be NULL for non copper zones)
46  * aCornerBuffer: A reference to a buffer to store polygon corners, or NULL
47  * if aCornerBuffer == NULL:
48  * - m_FilledPolysList is used to store solid areas polygons.
49  * - on copper layers, tracks and other items shapes of other nets are
50  * removed from solid areas
51  * if not null:
52  * Only the zone outline (with holes, if any) are stored in aCornerBuffer
53  * with holes linked. Therefore only one polygon is created
54  * This function calls AddClearanceAreasPolygonsToPolysList()
55  * to add holes for pads and tracks and other items not in net.
56  */
57 
59 {
60  /* convert outlines + holes to outlines without holes (adding extra segments if necessary)
61  * m_Poly data is expected normalized, i.e. NormalizeAreaOutlines was used after building
62  * this zone
63  */
64 
65  if( GetNumCorners() <= 2 ) // malformed zone. polygon calculations do not like it ...
66  return false;
67 
68  // Make a smoothed polygon out of the user-drawn polygon if required
69  if( m_smoothedPoly )
70  {
71  delete m_smoothedPoly;
72  m_smoothedPoly = NULL;
73  }
74 
75  switch( m_cornerSmoothingType )
76  {
80  break;
81 
85  break;
86 
87  default:
88  // Acute angles between adjacent edges can create issues in calculations,
89  // in inflate/deflate outlines transforms, especially when the angle is very small.
90  // We can avoid issues by creating a very small chamfer which remove acute angles,
91  // or left it without chamfer and use only CPOLYGONS_LIST::InflateOutline to create
92  // clearance areas
94  *m_smoothedPoly = m_Poly->Chamfer( Millimeter2iu( 0.0 ) );
95  break;
96  }
97 
98  if( aOutlineBuffer )
99  aOutlineBuffer->Append( *m_smoothedPoly );
100 
101  /* For copper layers, we now must add holes in the Polygon list.
102  * holes are pads and tracks with their clearance area
103  * For non copper layers, just recalculate the m_FilledPolysList
104  * with m_ZoneMinThickness taken in account
105  */
106  else
107  {
109 
110  if( IsOnCopperLayer() )
111  {
113 
114  if( m_FillMode ) // if fill mode uses segments, create them:
115  {
117  return false;
118  }
119  }
120  else
121  {
122  m_FillMode = 0; // Fill by segments is no more used in non copper layers
123  // force use solid polygons (usefull only for old boards)
125 
126  // The filled areas are deflated by -m_ZoneMinThickness / 2, because
127  // the outlines are drawn with a line thickness = m_ZoneMinThickness to
128  // give a good shape with the minimal thickness
131  }
132 
133  m_IsFilled = true;
134  }
135 
136  return true;
137 }
138 
139 
149  std::vector <SEGMENT>& aFillSegmList, int aStep );
150 
152 {
153  bool success = true;
154  // segments are on something like a grid. Give it a minimal size
155  // to avoid too many segments, and use the m_ZoneMinThickness when (this is usually the case)
156  // the size is > mingrid_size.
157  // This is not perfect, but the actual purpose of this code
158  // is to allow filling zones on a grid, with grid size > m_ZoneMinThickness,
159  // in order to have really a grid.
160  //
161  // Using a user selectable grid size is for future Kicad versions.
162  // For now the area is fully filled.
163  int mingrid_size = Millimeter2iu( 0.05 );
164  int grid_size = std::max( mingrid_size, m_ZoneMinThickness );
165  // Make segments slightly overlapping to ensure a good full filling
166  grid_size -= grid_size/20;
167 
168  // All filled areas are in m_FilledPolysList
169  // m_FillSegmList will contain the horizontal and vertical segments
170  // the segment width is m_ZoneMinThickness.
171  m_FillSegmList.clear();
172 
173  // Creates the horizontal segments
174  for ( int index = 0; index < m_FilledPolysList.OutlineCount(); index++ )
175  {
176  const SHAPE_LINE_CHAIN& outline0 = m_FilledPolysList.COutline( index );
177  success = fillPolygonWithHorizontalSegments( outline0, m_FillSegmList, grid_size );
178 
179  if( !success )
180  break;
181 
182  // Creates the vertical segments. Because the filling algo creates horizontal segments,
183  // to reuse the fillPolygonWithHorizontalSegments function, we rotate the polygons to fill
184  // then fill them, then inverse rotate the result
185  SHAPE_LINE_CHAIN outline90;
186  outline90.Append( outline0 );
187 
188  // Rotate 90 degrees the outline:
189  for( int ii = 0; ii < outline90.PointCount(); ii++ )
190  {
191  VECTOR2I& point = outline90.Point( ii );
192  std::swap( point.x, point.y );
193  point.y = -point.y;
194  }
195 
196  int first_point = m_FillSegmList.size();
197  success = fillPolygonWithHorizontalSegments( outline90, m_FillSegmList, grid_size );
198 
199  if( !success )
200  break;
201 
202  // Rotate -90 degrees the segments:
203  for( unsigned ii = first_point; ii < m_FillSegmList.size(); ii++ )
204  {
205  SEGMENT& segm = m_FillSegmList[ii];
206  std::swap( segm.m_Start.x, segm.m_Start.y );
207  std::swap( segm.m_End.x, segm.m_End.y );
208  segm.m_Start.x = - segm.m_Start.x;
209  segm.m_End.x = - segm.m_End.x;
210  }
211  }
212 
213  if( success )
214  m_IsFilled = true;
215  else
216  m_FillSegmList.clear();
217 
218  return success;
219 }
220 
221 
223  std::vector <SEGMENT>& aFillSegmList, int aStep )
224 {
225  std::vector <int> x_coordinates;
226  bool success = true;
227 
228  // Creates the horizontal segments
229  const SHAPE_LINE_CHAIN& outline = aPolygon;
230  const BOX2I& rect = outline.BBox();
231 
232  // Calculate the y limits of the zone
233  for( int refy = rect.GetY(), endy = rect.GetBottom(); refy < endy; refy += aStep )
234  {
235  // find all intersection points of an infinite line with polyline sides
236  x_coordinates.clear();
237 
238  for( int v = 0; v < outline.PointCount(); v++ )
239  {
240 
241  int seg_startX = outline.CPoint( v ).x;
242  int seg_startY = outline.CPoint( v ).y;
243  int seg_endX = outline.CPoint( v + 1 ).x;
244  int seg_endY = outline.CPoint( v + 1 ).y;
245 
246  /* Trivial cases: skip if ref above or below the segment to test */
247  if( ( seg_startY > refy ) && ( seg_endY > refy ) )
248  continue;
249 
250  // segment below ref point, or its Y end pos on Y coordinate ref point: skip
251  if( ( seg_startY <= refy ) && (seg_endY <= refy ) )
252  continue;
253 
254  /* at this point refy is between seg_startY and seg_endY
255  * see if an horizontal line at Y = refy is intersecting this segment
256  */
257  // calculate the x position of the intersection of this segment and the
258  // infinite line this is more easier if we move the X,Y axis origin to
259  // the segment start point:
260 
261  seg_endX -= seg_startX;
262  seg_endY -= seg_startY;
263  double newrefy = (double) ( refy - seg_startY );
264  double intersec_x;
265 
266  if ( seg_endY == 0 ) // horizontal segment on the same line: skip
267  continue;
268 
269  // Now calculate the x intersection coordinate of the horizontal line at
270  // y = newrefy and the segment from (0,0) to (seg_endX,seg_endY) with the
271  // horizontal line at the new refy position the line slope is:
272  // slope = seg_endY/seg_endX; and inv_slope = seg_endX/seg_endY
273  // and the x pos relative to the new origin is:
274  // intersec_x = refy/slope = refy * inv_slope
275  // Note: because horizontal segments are already tested and skipped, slope
276  // exists (seg_end_y not O)
277  double inv_slope = (double) seg_endX / seg_endY;
278  intersec_x = newrefy * inv_slope;
279  x_coordinates.push_back( (int) intersec_x + seg_startX );
280  }
281 
282  // A line scan is finished: build list of segments
283 
284  // Sort intersection points by increasing x value:
285  // So 2 consecutive points are the ends of a segment
286  sort( x_coordinates.begin(), x_coordinates.end() );
287 
288  // An even number of coordinates is expected, because a segment has 2 ends.
289  // An if this algorithm always works, it must always find an even count.
290  if( ( x_coordinates.size() & 1 ) != 0 )
291  {
292  success = false;
293  break;
294  }
295 
296  // Create segments having the same Y coordinate
297  int iimax = x_coordinates.size() - 1;
298 
299  for( int ii = 0; ii < iimax; ii += 2 )
300  {
301  wxPoint seg_start, seg_end;
302  seg_start.x = x_coordinates[ii];
303  seg_start.y = refy;
304  seg_end.x = x_coordinates[ii + 1];
305  seg_end.y = refy;
306  SEGMENT segment( seg_start, seg_end );
307  aFillSegmList.push_back( segment );
308  }
309  } // End examine segments in one area
310 
311  return success;
312 }
wxPoint m_End
Definition: class_zone.h:60
coord_type GetY() const
Definition: box2.h:179
int GetNumCorners(void) const
Access to m_Poly parameters.
Definition: class_zone.h:480
int PointCount() const
Function PointCount()
bool BuildFilledSolidAreasPolygons(BOARD *aPcb, SHAPE_POLY_SET *aOutlineBuffer=NULL)
Build the filled solid areas polygons from zone outlines (stored in m_Poly) The solid areas can be mo...
bool fillPolygonWithHorizontalSegments(const SHAPE_LINE_CHAIN &aPolygon, std::vector< SEGMENT > &aFillSegmList, int aStep)
Helper function fillPolygonWithHorizontalSegments fills a polygon with horizontal segments...
Classes to handle copper zones.
int OutlineCount() const
Returns the number of outlines in the set
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
SHAPE_POLY_SET * m_smoothedPoly
Definition: class_zone.h:742
int m_ArcToSegmentsCount
The number of segments to convert a circle to a polygon.
Definition: class_zone.h:772
const BOX2I BBox(int aClearance=0) const override
Function BBox()
void Inflate(int aFactor, int aCircleSegmentsCount)
Performs outline inflation/deflation, using round corners.
SHAPE_POLY_SET Fillet(int aRadius, int aSegments)
Function Fillet returns a filleted version of the polygon set.
Class SHAPE_POLY_SET.
bool m_IsFilled
True when a zone was filled, false after deleting the filled areas.
Definition: class_zone.h:775
int m_FillMode
How to fill areas: 0 => use filled polygons, 1 => fill with segments.
Definition: class_zone.h:785
SHAPE_POLY_SET * m_Poly
Outline of the zone.
Definition: class_zone.h:741
coord_type GetBottom() const
Definition: box2.h:188
int m_cornerSmoothingType
Definition: class_zone.h:743
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
SHAPE_POLY_SET m_FilledPolysList
Definition: class_zone.h:806
bool FillZoneAreasWithSegments()
Function FillZoneAreasWithSegments Fill sub areas in a zone with segments with m_ZoneMinThickness wid...
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
unsigned int m_cornerRadius
Definition: class_zone.h:744
void AddClearanceAreasPolygonsToPolysList_NG(BOARD *aPcb)
Function AddClearanceAreasPolygonsToPolysList Supports a min thickness area constraint.
bool IsOnCopperLayer() const
Function IsOnCopperLayer.
Definition: class_zone.cpp:188
int m_ZoneMinThickness
Minimum thickness value in filled areas.
Definition: class_zone.h:768
SHAPE_POLY_SET Chamfer(int aDistance)
Function Chamfer returns a chamfered version of the polygon set.
#define max(a, b)
Definition: auxiliary.h:86
Class BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:169
Class SHAPE_LINE_CHAIN.
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
Struct SEGMENT is a simple container used when filling areas with segments.
Definition: class_zone.h:57
VECTOR2I & Point(int aIndex)
Function Point()
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
wxPoint m_Start
Definition: class_zone.h:59
std::vector< SEGMENT > m_FillSegmList
Segments used to fill the zone (m_FillMode ==1 ), when fill zone by segment is used.
Definition: class_zone.h:796
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline) ...