KiCad PCB EDA Suite
convert_drawsegment_list_to_polygon.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) 2017 Jean-Pierre Charras, jp.charras at wanadoo.fr
5  * Copyright (C) 2015 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
6  * Copyright (C) 1992-2017 KiCad Developers, see AUTHORS.txt for contributors.
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
32 #include <trigo.h>
33 #include <macros.h>
34 
35 #include <class_drawsegment.h>
36 #include <base_units.h>
38 
39 
52 static unsigned close_ness( const wxPoint& aLeft, const wxPoint& aRight )
53 {
54  // Don't need an accurate distance calculation, just something
55  // approximating it, for relative ordering.
56  return unsigned( std::abs( aLeft.x - aRight.x ) + abs( aLeft.y - aRight.y ) );
57 }
58 
68 inline bool close_enough( const wxPoint& aLeft, const wxPoint& aRight, unsigned aLimit )
69 {
70  // We don't use an accurate distance calculation, just something
71  // approximating it, since aLimit is non-exact anyway except when zero.
72  return close_ness( aLeft, aRight ) <= aLimit;
73 }
74 
84 inline bool close_st( const wxPoint& aReference, const wxPoint& aFirst, const wxPoint& aSecond )
85 {
86  // We don't use an accurate distance calculation, just something
87  // approximating to find the closest to the reference.
88  return close_ness( aReference, aFirst ) <= close_ness( aReference, aSecond );
89 }
90 
91 
101 static DRAWSEGMENT* findPoint( const wxPoint& aPoint, std::vector< DRAWSEGMENT* >& aList, unsigned aLimit )
102 {
103  unsigned min_d = INT_MAX;
104  int ndx_min = 0;
105 
106  // find the point closest to aPoint and perhaps exactly matching aPoint.
107  for( size_t i = 0; i < aList.size(); ++i )
108  {
109  DRAWSEGMENT* graphic = aList[i];
110  unsigned d;
111 
112  switch( graphic->GetShape() )
113  {
114  case S_ARC:
115  if( aPoint == graphic->GetArcStart() || aPoint == graphic->GetArcEnd() )
116  {
117  aList.erase( aList.begin() + i );
118  return graphic;
119  }
120 
121  d = close_ness( aPoint, graphic->GetArcStart() );
122  if( d < min_d )
123  {
124  min_d = d;
125  ndx_min = i;
126  }
127 
128  d = close_ness( aPoint, graphic->GetArcEnd() );
129  if( d < min_d )
130  {
131  min_d = d;
132  ndx_min = i;
133  }
134  break;
135 
136  default:
137  if( aPoint == graphic->GetStart() || aPoint == graphic->GetEnd() )
138  {
139  aList.erase( aList.begin() + i );
140  return graphic;
141  }
142 
143  d = close_ness( aPoint, graphic->GetStart() );
144  if( d < min_d )
145  {
146  min_d = d;
147  ndx_min = i;
148  }
149 
150  d = close_ness( aPoint, graphic->GetEnd() );
151  if( d < min_d )
152  {
153  min_d = d;
154  ndx_min = i;
155  }
156  }
157  }
158 
159  if( min_d <= aLimit )
160  {
161  DRAWSEGMENT* graphic = aList[ndx_min];
162  aList.erase( aList.begin() + ndx_min );
163  return graphic;
164  }
165 
166  return NULL;
167 }
168 
169 
180 bool ConvertOutlineToPolygon( std::vector< DRAWSEGMENT* >& aSegList,
181  SHAPE_POLY_SET& aPolygons, int aSegmentsByCircle,
182  wxString* aErrorText )
183 {
184 
185  if( aSegList.size() == 0 )
186  return true;
187 
188  wxString msg;
189 
190  // Make a working copy of aSegList, because the list is modified during calculations
191  std::vector< DRAWSEGMENT* > segList = aSegList;
192 
193  unsigned prox; // a proximity BIU metric, not an accurate distance
194  DRAWSEGMENT* graphic;
195  wxPoint prevPt;
196 
197  // Find edge point with minimum x, this should be in the outer polygon
198  // which will define the perimeter Edge.Cuts polygon.
199  wxPoint xmin = wxPoint( INT_MAX, 0 );
200  int xmini = 0;
201 
202  for( size_t i = 0; i < segList.size(); i++ )
203  {
204  graphic = (DRAWSEGMENT*) segList[i];
205 
206  switch( graphic->GetShape() )
207  {
208  case S_SEGMENT:
209  {
210  if( graphic->GetStart().x < xmin.x )
211  {
212  xmin = graphic->GetStart();
213  xmini = i;
214  }
215 
216  if( graphic->GetEnd().x < xmin.x )
217  {
218  xmin = graphic->GetEnd();
219  xmini = i;
220  }
221  }
222  break;
223 
224  case S_ARC:
225  // Freerouter does not yet understand arcs, so approximate
226  // an arc with a series of short lines and put those
227  // line segments into the !same! PATH.
228  {
229  wxPoint pstart = graphic->GetArcStart();
230  wxPoint center = graphic->GetCenter();
231  double angle = -graphic->GetAngle();
232  int steps = aSegmentsByCircle * fabs(angle) /3600.0;
233 
234  if( steps == 0 )
235  steps = 1;
236 
237  wxPoint pt;
238 
239  for( int step = 1; step<=steps; ++step )
240  {
241  double rotation = ( angle * step ) / steps;
242 
243  pt = pstart;
244 
245  RotatePoint( &pt, center, rotation );
246 
247  if( pt.x < xmin.x )
248  {
249  xmin = pt;
250  xmini = i;
251  }
252  }
253  }
254  break;
255 
256  case S_CIRCLE:
257  {
258  wxPoint pt = graphic->GetCenter();
259 
260  // pt has minimum x point
261  pt.x -= graphic->GetRadius();
262 
263  // when the radius <= 0, this is a mal-formed circle. Skip it
264  if( graphic->GetRadius() > 0 && pt.x < xmin.x )
265  {
266  xmin = pt;
267  xmini = i;
268  }
269  }
270  break;
271 
272  default:
273  break;
274  }
275  }
276 
277  // Grab the left most point, assume its on the board's perimeter, and see if we
278  // can put enough graphics together by matching endpoints to formulate a cohesive
279  // polygon.
280 
281  graphic = (DRAWSEGMENT*) segList[xmini];
282 
283  // The first DRAWSEGMENT is in 'graphic', ok to remove it from 'items'
284  segList.erase( segList.begin() + xmini );
285 
286  // Set maximum proximity threshold for point to point nearness metric for
287  // board perimeter only, not interior keepouts yet.
288  prox = Millimeter2iu( 0.01 ); // should be enough to fix rounding issues
289  // is arc start and end point calculations
290 
291  // Output the Edge.Cuts perimeter as circle or polygon.
292  if( graphic->GetShape() == S_CIRCLE )
293  {
294  TransformCircleToPolygon( aPolygons, graphic->GetCenter(),
295  graphic->GetRadius(), aSegmentsByCircle );
296  }
297  else
298  {
299  // Polygon start point. Arbitrarily chosen end of the
300  // segment and build the poly from here.
301 
302  wxPoint startPt = wxPoint( graphic->GetEnd() );
303  prevPt = graphic->GetEnd();
304  aPolygons.NewOutline();
305  aPolygons.Append( prevPt );
306 
307  // Do not append the other end point yet of this 'graphic', this first
308  // 'graphic' might be an arc.
309 
310  for(;;)
311  {
312  switch( graphic->GetShape() )
313  {
314  case S_SEGMENT:
315  {
316  wxPoint nextPt;
317 
318  // Use the line segment end point furthest away from
319  // prevPt as we assume the other end to be ON prevPt or
320  // very close to it.
321 
322  if( close_st( prevPt, graphic->GetStart(), graphic->GetEnd() ) )
323  {
324  nextPt = graphic->GetEnd();
325  }
326  else
327  {
328  nextPt = graphic->GetStart();
329  }
330 
331  aPolygons.Append( nextPt );
332  prevPt = nextPt;
333  }
334  break;
335 
336  case S_ARC:
337  // We do not support arcs in polygons, so approximate
338  // an arc with a series of short lines and put those
339  // line segments into the !same! PATH.
340  {
341  wxPoint pstart = graphic->GetArcStart();
342  wxPoint pend = graphic->GetArcEnd();
343  wxPoint pcenter = graphic->GetCenter();
344  double angle = -graphic->GetAngle();
345  int steps = aSegmentsByCircle * fabs(angle) /3600.0;
346 
347  if( steps == 0 )
348  steps = 1;
349 
350  if( !close_enough( prevPt, pstart, prox ) )
351  {
352  wxASSERT( close_enough( prevPt, graphic->GetArcEnd(), prox ) );
353 
354  angle = -angle;
355  std::swap( pstart, pend );
356  }
357 
358  wxPoint nextPt;
359 
360  for( int step = 1; step<=steps; ++step )
361  {
362  double rotation = ( angle * step ) / steps;
363  nextPt = pstart;
364  RotatePoint( &nextPt, pcenter, rotation );
365 
366  aPolygons.Append( nextPt );
367  }
368 
369  prevPt = nextPt;
370  }
371  break;
372 
373  default:
374  if( aErrorText )
375  {
376  msg.Printf( _( "Unsupported DRAWSEGMENT type %s" ),
377  GetChars( BOARD_ITEM::ShowShape( graphic->GetShape() ) ) );
378 
379  *aErrorText << msg << "\n";
380  }
381 
382  return false;
383  }
384 
385  // Get next closest segment.
386 
387  graphic = findPoint( prevPt, segList, prox );
388 
389  // If there are no more close segments, check if the board
390  // outline polygon can be closed.
391 
392  if( !graphic )
393  {
394  if( close_enough( startPt, prevPt, prox ) )
395  {
396  // Close the polygon back to start point
397  // aPolygons.Append( startPt ); // not needed
398  }
399  else
400  {
401  if( aErrorText )
402  {
403  msg.Printf(
404  _( "Unable to find the next boundary segment with an endpoint of (%s mm, %s mm). "
405  "graphic outline must form a contiguous, closed polygon." ),
406  GetChars( FROM_UTF8( BOARD_ITEM::FormatInternalUnits( prevPt.x ).c_str() ) ),
407  GetChars( FROM_UTF8( BOARD_ITEM::FormatInternalUnits( prevPt.y ).c_str() ) )
408  );
409 
410  *aErrorText << msg << "\n";
411  }
412 
413  return false;
414  }
415  break;
416  }
417  }
418  }
419 
420  // Output the interior Edge.Cuts graphics as keepouts, using same nearness
421  // metric as the board edge as otherwise we have trouble completing complex
422  // polygons.
423  prox = Millimeter2iu( 0.05 );
424 
425  while( segList.size() )
426  {
427  // emit a signal layers keepout for every interior polygon left...
428  int hole = aPolygons.NewHole();
429 
430  graphic = (DRAWSEGMENT*) segList[0];
431  segList.erase( segList.begin() );
432 
433  if( graphic->GetShape() == S_CIRCLE )
434  {
435  // make a circle by segments;
436  wxPoint center = graphic->GetCenter();
437  double angle = 3600.0;
438  wxPoint start = center;
439  int radius = graphic->GetRadius();
440  start.x += radius;
441 
442  wxPoint nextPt;
443 
444  for( int step = 0; step<aSegmentsByCircle; ++step )
445  {
446  double rotation = ( angle * step ) / aSegmentsByCircle;
447  nextPt = start;
448  RotatePoint( &nextPt.x, &nextPt.y, center.x, center.y, rotation );
449  aPolygons.Append( nextPt, -1, hole );
450  }
451  }
452  else
453  {
454  // Polygon start point. Arbitrarily chosen end of the
455  // segment and build the poly from here.
456 
457  wxPoint startPt( graphic->GetEnd() );
458  prevPt = graphic->GetEnd();
459  aPolygons.Append( prevPt, -1, hole );
460 
461  // do not append the other end point yet, this first 'graphic' might be an arc
462  for(;;)
463  {
464  switch( graphic->GetShape() )
465  {
466  case S_SEGMENT:
467  {
468  wxPoint nextPt;
469 
470  // Use the line segment end point furthest away from
471  // prevPt as we assume the other end to be ON prevPt or
472  // very close to it.
473 
474  if( close_st( prevPt, graphic->GetStart(), graphic->GetEnd() ) )
475  {
476  nextPt = graphic->GetEnd();
477  }
478  else
479  {
480  nextPt = graphic->GetStart();
481  }
482 
483  prevPt = nextPt;
484  aPolygons.Append( prevPt, -1, hole );
485  }
486  break;
487 
488  case S_ARC:
489  // Freerouter does not yet understand arcs, so approximate
490  // an arc with a series of short lines and put those
491  // line segments into the !same! PATH.
492  {
493  wxPoint pstart = graphic->GetArcStart();
494  wxPoint pend = graphic->GetArcEnd();
495  wxPoint pcenter = graphic->GetCenter();
496  double angle = -graphic->GetAngle();
497  int steps = aSegmentsByCircle * fabs(angle) /3600.0;
498 
499  if( steps == 0 )
500  steps = 1;
501 
502  if( !close_enough( prevPt, pstart, prox ) )
503  {
504  wxASSERT( close_enough( prevPt, graphic->GetArcEnd(), prox ) );
505 
506  angle = -angle;
507  std::swap( pstart, pend );
508  }
509 
510  wxPoint nextPt;
511 
512  for( int step = 1; step <= steps; ++step )
513  {
514  double rotation = ( angle * step ) / steps;
515 
516  nextPt = pstart;
517  RotatePoint( &nextPt, pcenter, rotation );
518 
519  aPolygons.Append( nextPt, -1, hole );
520  }
521 
522  prevPt = nextPt;
523  }
524  break;
525 
526  default:
527  if( aErrorText )
528  {
529  msg.Printf(
530  _( "Unsupported DRAWSEGMENT type %s" ),
531  GetChars( BOARD_ITEM::ShowShape( graphic->GetShape() ) ) );
532 
533  *aErrorText << msg << "\n";
534  }
535 
536  return false;
537  }
538 
539  // Get next closest segment.
540 
541  graphic = findPoint( prevPt, segList, prox );
542 
543  // If there are no more close segments, check if polygon
544  // can be closed.
545 
546  if( !graphic )
547  {
548  if( close_enough( startPt, prevPt, prox ) )
549  {
550  // Close the polygon back to start point
551  // aPolygons.Append( startPt, -1, hole ); // not needed
552  }
553  else
554  {
555  if( aErrorText )
556  {
557  msg.Printf(
558  _( "Unable to find the next graphic segment with an endpoint of (%s mm, %s mm).\n"
559  "Edit graphics, making them contiguous polygons each." ),
560  GetChars( FROM_UTF8( BOARD_ITEM::FormatInternalUnits( prevPt.x ).c_str() ) ),
561  GetChars( FROM_UTF8( BOARD_ITEM::FormatInternalUnits( prevPt.y ).c_str() ) )
562  );
563 
564  *aErrorText << msg << "\n";
565  }
566 
567  return false;
568  }
569  break;
570  }
571  }
572  }
573  }
574 
575  return true;
576 }
577 
578 #include <class_board.h>
579 #include <collectors.h>
580 
581 /* This function is used to extract a board outlines (3D view, automatic zones build ...)
582  * Any closed outline inside the main outline is a hole
583  * All contours should be closed, i.e. valid closed polygon vertices
584  */
586  SHAPE_POLY_SET& aOutlines,
587  wxString* aErrorText )
588 {
589  PCB_TYPE_COLLECTOR items;
590 
591  // Get all the DRAWSEGMENTS and module graphics into 'items',
592  // then keep only those on layer == Edge_Cuts.
593  static const KICAD_T scan_graphics[] = { PCB_LINE_T, PCB_MODULE_EDGE_T, EOT };
594  items.Collect( aBoard, scan_graphics );
595 
596  // Make a working copy of aSegList, because the list is modified during calculations
597  std::vector< DRAWSEGMENT* > segList;
598 
599  for( int ii = 0; ii < items.GetCount(); ii++ )
600  {
601  if( items[ii]->GetLayer() == Edge_Cuts )
602  segList.push_back( static_cast< DRAWSEGMENT* >( items[ii] ) );
603  }
604 
605  const int STEPS = 36; // for a segmentation of an arc of 360 degrees
606  bool success = ConvertOutlineToPolygon( segList, aOutlines, STEPS, aErrorText );
607 
608  if( !success || !aOutlines.OutlineCount() )
609  {
610  // Creates a valid polygon outline is not possible.
611  // So uses the board edge cuts bounding box to create a
612  // rectangular outline
613  // When no edge cuts items, build a contour
614  // from global bounding box
615 
616  EDA_RECT bbbox = aBoard->GetBoardEdgesBoundingBox();
617 
618  // If null area, uses the global bounding box.
619  if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
620  bbbox = aBoard->ComputeBoundingBox();
621 
622  // Ensure non null area. If happen, gives a minimal size.
623  if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
624  bbbox.Inflate( Millimeter2iu( 1.0 ) );
625 
626  aOutlines.RemoveAllContours();
627  aOutlines.NewOutline();
628 
629  wxPoint corner;
630  aOutlines.Append( bbbox.GetOrigin() );
631 
632  corner.x = bbbox.GetOrigin().x;
633  corner.y = bbbox.GetEnd().y;
634  aOutlines.Append( corner );
635 
636  aOutlines.Append( bbbox.GetEnd() );
637 
638  corner.x = bbbox.GetEnd().x;
639  corner.y = bbbox.GetOrigin().y;
640  aOutlines.Append( corner );
641  }
642 
643  return success;
644 }
int GetCount() const
Function GetCount returns the number of objects in the list.
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
static wxString ShowShape(STROKE_T aShape)
Function ShowShape converts the enum STROKE_T integer value to a wxString.
const wxPoint GetOrigin() const
static wxString FROM_UTF8(const char *cstring)
function FROM_UTF8 converts a UTF8 encoded C string to a wxString for all wxWidgets build modes...
Definition: macros.h:53
Implementation of conversion functions that require both schematic and board internal units...
const wxPoint GetCenter() const override
Function GetCenter()
void TransformCircleToPolygon(SHAPE_POLY_SET &aCornerBuffer, wxPoint aCenter, int aRadius, int aCircleToSegmentsCount)
Function TransformCircleToPolygon convert a circle to a polygon, using multiple straight lines...
EDA_RECT ComputeBoundingBox(bool aBoardEdgesOnly=false) const
Function ComputeBoundingBox calculates the bounding box containing all board items (or board edge seg...
Class BOARD to handle a board.
int GetHeight() const
usual segment : line with rounded ends
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:317
int OutlineCount() const
Returns the number of outlines in the set
#define abs(a)
Definition: auxiliary.h:84
static unsigned close_ness(const wxPoint &aLeft, const wxPoint &aRight)
Function close_ness is a non-exact distance (also called Manhattan distance) used to approximate the ...
class EDGE_MODULE, a footprint edge
Definition: typeinfo.h:94
search types array terminator (End Of Types)
Definition: typeinfo.h:82
KICAD_T
Enum KICAD_T is the set of class identification values, stored in EDA_ITEM::m_StructType.
Definition: typeinfo.h:78
static std::string FormatInternalUnits(int aValue)
Function FormatInternalUnits converts aValue from board internal units to a string appropriate for wr...
bool ConvertOutlineToPolygon(std::vector< DRAWSEGMENT * > &aSegList, SHAPE_POLY_SET &aPolygons, int aSegmentsByCircle, wxString *aErrorText)
Function ConvertOutlineToPolygon build a polygon (with holes) from a DRAWSEGMENT list, which is expected to be a outline, therefore a closed main outline with perhaps closed inner outlines.
bool close_st(const wxPoint &aReference, const wxPoint &aFirst, const wxPoint &aSecond)
Function close_st is a local method of qualifying if either the start of end point of a segment is cl...
This file contains miscellaneous commonly used macros and functions.
const wxPoint & GetArcStart() const
const EDA_RECT GetBoardEdgesBoundingBox() const
Function GetBoardEdgesBoundingBox Returns the board bounding box calculated using exclusively the boa...
Definition: class_board.h:797
bool BuildBoardPolygonOutlines(BOARD *aBoard, SHAPE_POLY_SET &aOutlines, wxString *aErrorText)
STROKE_T GetShape() const
const wxPoint & GetEnd() const
Function GetEnd returns the ending point of the graphic.
Class SHAPE_POLY_SET.
Arcs (with rounded ends)
bool close_enough(const wxPoint &aLeft, const wxPoint &aRight, unsigned aLimit)
Function close_enough is a local and tunable method of qualifying the proximity of two points...
int NewOutline()
Creates a new empty polygon in the set and returns its index
void Collect(BOARD_ITEM *aBoard, const KICAD_T aScanList[])
Collect BOARD_ITEM objects using this class's Inspector method, which does the collection.
Definition: collectors.cpp:475
const wxPoint GetEnd() const
static const wxChar * GetChars(const wxString &s)
Function GetChars returns a wxChar* to the actual wxChar* data within a wxString, and is helpful for ...
Definition: macros.h:92
double GetAngle() const
Class to handle a graphic segment.
Class BOARD holds information pertinent to a Pcbnew printed circuit board.
Definition: class_board.h:169
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
const wxPoint GetArcEnd() const
static DRAWSEGMENT * findPoint(const wxPoint &aPoint, std::vector< DRAWSEGMENT * > &aList, unsigned aLimit)
Searches for a DRAWSEGMENT matching a given end point or start point in a list, and if found...
Class EDA_RECT handles the component boundary box.
int GetWidth() const
static bool GetLayer(MODEL_VRML &aModel, LAYER_NUM layer, VRML_LAYER **vlayer)
Collect all BOARD_ITEM objects of a given set of KICAD_T type(s).
Definition: collectors.h:544
class DRAWSEGMENT, a segment not on copper layers
Definition: typeinfo.h:91
const wxPoint & GetStart() const
Function GetStart returns the starting point of the graphic.
int GetRadius() const
Function GetRadius returns the radius of this item Has meaning only for arc and circle.
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
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) ...