KiCad PCB EDA Suite
zone_filling_algorithm.cpp File Reference

: Algorithms used to fill a zone defined by a polygon and a filling starting point. More...

#include <algorithm>
#include <fctsys.h>
#include <trigo.h>
#include <wxPcbStruct.h>
#include <convert_basic_shapes_to_polygon.h>
#include <class_zone.h>
#include <pcbnew.h>
#include <zones.h>

Go to the source code of this file.

Functions

bool fillPolygonWithHorizontalSegments (const SHAPE_LINE_CHAIN &aPolygon, std::vector< SEGMENT > &aFillSegmList, int aStep)
 Helper function fillPolygonWithHorizontalSegments fills a polygon with horizontal segments. More...
 

Detailed Description

: Algorithms used to fill a zone defined by a polygon and a filling starting point.

Definition in file zone_filling_algorithm.cpp.

Function Documentation

bool fillPolygonWithHorizontalSegments ( const SHAPE_LINE_CHAIN aPolygon,
std::vector< SEGMENT > &  aFillSegmList,
int  aStep 
)

Helper function fillPolygonWithHorizontalSegments fills a polygon with horizontal segments.

It can be used for any angle, if the zone outline to fill is rotated by this angle and the result is rotated by -angle

Parameters
aPolygon= a SHAPE_LINE_CHAIN polygon to fill
aFillSegmList= a std::vector <SEGMENT> which will be populated by filling segments
aStep= the horizontal grid size

Definition at line 222 of file zone_filling_algorithm.cpp.

References SHAPE_LINE_CHAIN::BBox(), SHAPE_LINE_CHAIN::CPoint(), BOX2< Vec >::GetBottom(), BOX2< Vec >::GetY(), SHAPE_LINE_CHAIN::PointCount(), wxPoint::x, VECTOR2< T >::x, wxPoint::y, and VECTOR2< T >::y.

Referenced by ZONE_CONTAINER::FillZoneAreasWithSegments().

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 }
coord_type GetY() const
Definition: box2.h:179
int PointCount() const
Function PointCount()
const BOX2I BBox(int aClearance=0) const override
Function BBox()
coord_type GetBottom() const
Definition: box2.h:188
Class SHAPE_LINE_CHAIN.
Struct SEGMENT is a simple container used when filling areas with segments.
Definition: class_zone.h:57
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()