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>
39 
40 
53 static unsigned close_ness( const wxPoint& aLeft, const wxPoint& aRight )
54 {
55  // Don't need an accurate distance calculation, just something
56  // approximating it, for relative ordering.
57  return unsigned( std::abs( aLeft.x - aRight.x ) + abs( aLeft.y - aRight.y ) );
58 }
59 
69 inline bool close_enough( const wxPoint& aLeft, const wxPoint& aRight, unsigned aLimit )
70 {
71  // We don't use an accurate distance calculation, just something
72  // approximating it, since aLimit is non-exact anyway except when zero.
73  return close_ness( aLeft, aRight ) <= aLimit;
74 }
75 
85 inline bool close_st( const wxPoint& aReference, const wxPoint& aFirst, const wxPoint& aSecond )
86 {
87  // We don't use an accurate distance calculation, just something
88  // approximating to find the closest to the reference.
89  return close_ness( aReference, aFirst ) <= close_ness( aReference, aSecond );
90 }
91 
92 
102 static DRAWSEGMENT* findPoint( const wxPoint& aPoint, std::vector< DRAWSEGMENT* >& aList, unsigned aLimit )
103 {
104  unsigned min_d = INT_MAX;
105  int ndx_min = 0;
106 
107  // find the point closest to aPoint and perhaps exactly matching aPoint.
108  for( size_t i = 0; i < aList.size(); ++i )
109  {
110  DRAWSEGMENT* graphic = aList[i];
111  unsigned d;
112 
113  switch( graphic->GetShape() )
114  {
115  case S_ARC:
116  if( aPoint == graphic->GetArcStart() || aPoint == graphic->GetArcEnd() )
117  {
118  aList.erase( aList.begin() + i );
119  return graphic;
120  }
121 
122  d = close_ness( aPoint, graphic->GetArcStart() );
123  if( d < min_d )
124  {
125  min_d = d;
126  ndx_min = i;
127  }
128 
129  d = close_ness( aPoint, graphic->GetArcEnd() );
130  if( d < min_d )
131  {
132  min_d = d;
133  ndx_min = i;
134  }
135  break;
136 
137  default:
138  if( aPoint == graphic->GetStart() || aPoint == graphic->GetEnd() )
139  {
140  aList.erase( aList.begin() + i );
141  return graphic;
142  }
143 
144  d = close_ness( aPoint, graphic->GetStart() );
145  if( d < min_d )
146  {
147  min_d = d;
148  ndx_min = i;
149  }
150 
151  d = close_ness( aPoint, graphic->GetEnd() );
152  if( d < min_d )
153  {
154  min_d = d;
155  ndx_min = i;
156  }
157  }
158  }
159 
160  if( min_d <= aLimit )
161  {
162  DRAWSEGMENT* graphic = aList[ndx_min];
163  aList.erase( aList.begin() + ndx_min );
164  return graphic;
165  }
166 
167  return NULL;
168 }
169 
170 
180 bool ConvertOutlineToPolygon( std::vector< DRAWSEGMENT* >& aSegList,
181  SHAPE_POLY_SET& aPolygons, wxString* aErrorText )
182 {
183 
184  if( aSegList.size() == 0 )
185  return true;
186 
187  wxString msg;
188 
189  // Make a working copy of aSegList, because the list is modified during calculations
190  std::vector< DRAWSEGMENT* > segList = aSegList;
191 
192  unsigned prox; // a proximity BIU metric, not an accurate distance
193  DRAWSEGMENT* graphic;
194  wxPoint prevPt;
195 
196  // Find edge point with minimum x, this should be in the outer polygon
197  // which will define the perimeter Edge.Cuts polygon.
198  wxPoint xmin = wxPoint( INT_MAX, 0 );
199  int xmini = 0;
200 
201  for( size_t i = 0; i < segList.size(); i++ )
202  {
203  graphic = (DRAWSEGMENT*) segList[i];
204 
205  switch( graphic->GetShape() )
206  {
207  case S_SEGMENT:
208  {
209  if( graphic->GetStart().x < xmin.x )
210  {
211  xmin = graphic->GetStart();
212  xmini = i;
213  }
214 
215  if( graphic->GetEnd().x < xmin.x )
216  {
217  xmin = graphic->GetEnd();
218  xmini = i;
219  }
220  }
221  break;
222 
223  case S_ARC:
224  // Freerouter does not yet understand arcs, so approximate
225  // an arc with a series of short lines and put those
226  // line segments into the !same! PATH.
227  {
228  wxPoint pstart = graphic->GetArcStart();
229  wxPoint center = graphic->GetCenter();
230  double angle = -graphic->GetAngle();
231  double radius = graphic->GetRadius();
232  int steps = GetArcToSegmentCount( radius, ARC_LOW_DEF, angle / 10.0 );
233  wxPoint pt;
234 
235  for( int step = 1; step<=steps; ++step )
236  {
237  double rotation = ( angle * step ) / steps;
238 
239  pt = pstart;
240 
241  RotatePoint( &pt, center, rotation );
242 
243  if( pt.x < xmin.x )
244  {
245  xmin = pt;
246  xmini = i;
247  }
248  }
249  }
250  break;
251 
252  case S_CIRCLE:
253  {
254  wxPoint pt = graphic->GetCenter();
255 
256  // pt has minimum x point
257  pt.x -= graphic->GetRadius();
258 
259  // when the radius <= 0, this is a mal-formed circle. Skip it
260  if( graphic->GetRadius() > 0 && pt.x < xmin.x )
261  {
262  xmin = pt;
263  xmini = i;
264  }
265  }
266  break;
267 
268  default:
269  break;
270  }
271  }
272 
273  // Grab the left most point, assume its on the board's perimeter, and see if we
274  // can put enough graphics together by matching endpoints to formulate a cohesive
275  // polygon.
276 
277  graphic = (DRAWSEGMENT*) segList[xmini];
278 
279  // The first DRAWSEGMENT is in 'graphic', ok to remove it from 'items'
280  segList.erase( segList.begin() + xmini );
281 
282  // Set maximum proximity threshold for point to point nearness metric for
283  // board perimeter only, not interior keepouts yet.
284  prox = Millimeter2iu( 0.01 ); // should be enough to fix rounding issues
285  // is arc start and end point calculations
286 
287  // Output the Edge.Cuts perimeter as circle or polygon.
288  if( graphic->GetShape() == S_CIRCLE )
289  {
290  int steps = GetArcToSegmentCount( graphic->GetRadius(), ARC_LOW_DEF, 360.0 );
291  TransformCircleToPolygon( aPolygons, graphic->GetCenter(), graphic->GetRadius(), steps );
292  }
293  else
294  {
295  // Polygon start point. Arbitrarily chosen end of the
296  // segment and build the poly from here.
297 
298  wxPoint startPt = wxPoint( graphic->GetEnd() );
299  prevPt = graphic->GetEnd();
300  aPolygons.NewOutline();
301  aPolygons.Append( prevPt );
302 
303  // Do not append the other end point yet of this 'graphic', this first
304  // 'graphic' might be an arc.
305 
306  for(;;)
307  {
308  switch( graphic->GetShape() )
309  {
310  case S_SEGMENT:
311  {
312  wxPoint nextPt;
313 
314  // Use the line segment end point furthest away from
315  // prevPt as we assume the other end to be ON prevPt or
316  // very close to it.
317 
318  if( close_st( prevPt, graphic->GetStart(), graphic->GetEnd() ) )
319  nextPt = graphic->GetEnd();
320  else
321  nextPt = graphic->GetStart();
322 
323  aPolygons.Append( nextPt );
324  prevPt = nextPt;
325  }
326  break;
327 
328  case S_ARC:
329  // We do not support arcs in polygons, so approximate
330  // an arc with a series of short lines and put those
331  // line segments into the !same! PATH.
332  {
333  wxPoint pstart = graphic->GetArcStart();
334  wxPoint pend = graphic->GetArcEnd();
335  wxPoint pcenter = graphic->GetCenter();
336  double angle = -graphic->GetAngle();
337  double radius = graphic->GetRadius();
338  int steps = GetArcToSegmentCount( radius, ARC_LOW_DEF, angle / 10.0 );
339 
340  if( !close_enough( prevPt, pstart, prox ) )
341  {
342  wxASSERT( close_enough( prevPt, graphic->GetArcEnd(), prox ) );
343 
344  angle = -angle;
345  std::swap( pstart, pend );
346  }
347 
348  wxPoint nextPt;
349 
350  for( int step = 1; step<=steps; ++step )
351  {
352  double rotation = ( angle * step ) / steps;
353  nextPt = pstart;
354  RotatePoint( &nextPt, pcenter, rotation );
355 
356  aPolygons.Append( nextPt );
357  }
358 
359  prevPt = nextPt;
360  }
361  break;
362 
363  default:
364  if( aErrorText )
365  {
366  msg.Printf( _( "Unsupported DRAWSEGMENT type %s" ),
367  GetChars( BOARD_ITEM::ShowShape( graphic->GetShape() ) ) );
368 
369  *aErrorText << msg << "\n";
370  }
371 
372  return false;
373  }
374 
375  // Get next closest segment.
376 
377  graphic = findPoint( prevPt, segList, prox );
378 
379  // If there are no more close segments, check if the board
380  // outline polygon can be closed.
381 
382  if( !graphic )
383  {
384  if( close_enough( startPt, prevPt, prox ) )
385  {
386  // Close the polygon back to start point
387  // aPolygons.Append( startPt ); // not needed
388  }
389  else
390  {
391  if( aErrorText )
392  {
393  msg.Printf(
394  _( "Unable to find the next boundary segment with an endpoint of (%s mm, %s mm). "
395  "graphic outline must form a contiguous, closed polygon." ),
396  GetChars( FROM_UTF8( BOARD_ITEM::FormatInternalUnits( prevPt.x ).c_str() ) ),
397  GetChars( FROM_UTF8( BOARD_ITEM::FormatInternalUnits( prevPt.y ).c_str() ) )
398  );
399 
400  *aErrorText << msg << "\n";
401  }
402 
403  return false;
404  }
405  break;
406  }
407  }
408  }
409 
410  // Output the interior Edge.Cuts graphics as keepouts, using same nearness
411  // metric as the board edge as otherwise we have trouble completing complex
412  // polygons.
413  prox = Millimeter2iu( 0.05 );
414 
415  while( segList.size() )
416  {
417  // emit a signal layers keepout for every interior polygon left...
418  int hole = aPolygons.NewHole();
419 
420  graphic = (DRAWSEGMENT*) segList[0];
421  segList.erase( segList.begin() );
422 
423  if( graphic->GetShape() == S_CIRCLE )
424  {
425  // make a circle by segments;
426  wxPoint center = graphic->GetCenter();
427  double angle = 3600.0;
428  wxPoint start = center;
429  int radius = graphic->GetRadius();
430  int steps = GetArcToSegmentCount( radius, ARC_LOW_DEF, 360.0 );
431  wxPoint nextPt;
432 
433  start.x += radius;
434 
435  for( int step = 0; step < steps; ++step )
436  {
437  double rotation = ( angle * step ) / steps;
438  nextPt = start;
439  RotatePoint( &nextPt.x, &nextPt.y, center.x, center.y, rotation );
440  aPolygons.Append( nextPt, -1, hole );
441  }
442  }
443  else
444  {
445  // Polygon start point. Arbitrarily chosen end of the
446  // segment and build the poly from here.
447 
448  wxPoint startPt( graphic->GetEnd() );
449  prevPt = graphic->GetEnd();
450  aPolygons.Append( prevPt, -1, hole );
451 
452  // do not append the other end point yet, this first 'graphic' might be an arc
453  for(;;)
454  {
455  switch( graphic->GetShape() )
456  {
457  case S_SEGMENT:
458  {
459  wxPoint nextPt;
460 
461  // Use the line segment end point furthest away from
462  // prevPt as we assume the other end to be ON prevPt or
463  // very close to it.
464 
465  if( close_st( prevPt, graphic->GetStart(), graphic->GetEnd() ) )
466  {
467  nextPt = graphic->GetEnd();
468  }
469  else
470  {
471  nextPt = graphic->GetStart();
472  }
473 
474  prevPt = nextPt;
475  aPolygons.Append( prevPt, -1, hole );
476  }
477  break;
478 
479  case S_ARC:
480  // Freerouter does not yet understand arcs, so approximate
481  // an arc with a series of short lines and put those
482  // line segments into the !same! PATH.
483  {
484  wxPoint pstart = graphic->GetArcStart();
485  wxPoint pend = graphic->GetArcEnd();
486  wxPoint pcenter = graphic->GetCenter();
487  double angle = -graphic->GetAngle();
488  int radius = graphic->GetRadius();
489  int steps = GetArcToSegmentCount( radius, ARC_LOW_DEF, angle / 10.0 );
490 
491  if( !close_enough( prevPt, pstart, prox ) )
492  {
493  wxASSERT( close_enough( prevPt, graphic->GetArcEnd(), prox ) );
494 
495  angle = -angle;
496  std::swap( pstart, pend );
497  }
498 
499  wxPoint nextPt;
500 
501  for( int step = 1; step <= steps; ++step )
502  {
503  double rotation = ( angle * step ) / steps;
504 
505  nextPt = pstart;
506  RotatePoint( &nextPt, pcenter, rotation );
507 
508  aPolygons.Append( nextPt, -1, hole );
509  }
510 
511  prevPt = nextPt;
512  }
513  break;
514 
515  default:
516  if( aErrorText )
517  {
518  msg.Printf( _( "Unsupported DRAWSEGMENT type %s" ),
519  GetChars( BOARD_ITEM::ShowShape( graphic->GetShape() ) ) );
520 
521  *aErrorText << msg << "\n";
522  }
523 
524  return false;
525  }
526 
527  // Get next closest segment.
528 
529  graphic = findPoint( prevPt, segList, prox );
530 
531  // If there are no more close segments, check if polygon
532  // can be closed.
533 
534  if( !graphic )
535  {
536  if( close_enough( startPt, prevPt, prox ) )
537  {
538  // Close the polygon back to start point
539  // aPolygons.Append( startPt, -1, hole ); // not needed
540  }
541  else
542  {
543  if( aErrorText )
544  {
545  msg.Printf(
546  _( "Unable to find the next graphic segment with an endpoint of (%s mm, %s mm).\n"
547  "Edit graphics, making them contiguous polygons each." ),
548  GetChars( FROM_UTF8( BOARD_ITEM::FormatInternalUnits( prevPt.x ).c_str() ) ),
549  GetChars( FROM_UTF8( BOARD_ITEM::FormatInternalUnits( prevPt.y ).c_str() ) )
550  );
551 
552  *aErrorText << msg << "\n";
553  }
554 
555  return false;
556  }
557  break;
558  }
559  }
560  }
561  }
562 
563  return true;
564 }
565 
566 #include <class_board.h>
567 #include <collectors.h>
568 
569 /* This function is used to extract a board outlines (3D view, automatic zones build ...)
570  * Any closed outline inside the main outline is a hole
571  * All contours should be closed, i.e. valid closed polygon vertices
572  */
574  SHAPE_POLY_SET& aOutlines,
575  wxString* aErrorText )
576 {
577  PCB_TYPE_COLLECTOR items;
578 
579  // Get all the DRAWSEGMENTS and module graphics into 'items',
580  // then keep only those on layer == Edge_Cuts.
581  static const KICAD_T scan_graphics[] = { PCB_LINE_T, PCB_MODULE_EDGE_T, EOT };
582  items.Collect( aBoard, scan_graphics );
583 
584  // Make a working copy of aSegList, because the list is modified during calculations
585  std::vector< DRAWSEGMENT* > segList;
586 
587  for( int ii = 0; ii < items.GetCount(); ii++ )
588  {
589  if( items[ii]->GetLayer() == Edge_Cuts )
590  segList.push_back( static_cast< DRAWSEGMENT* >( items[ii] ) );
591  }
592 
593  bool success = ConvertOutlineToPolygon( segList, aOutlines, aErrorText );
594 
595  if( !success || !aOutlines.OutlineCount() )
596  {
597  // Creates a valid polygon outline is not possible.
598  // So uses the board edge cuts bounding box to create a
599  // rectangular outline
600  // When no edge cuts items, build a contour
601  // from global bounding box
602 
603  EDA_RECT bbbox = aBoard->GetBoardEdgesBoundingBox();
604 
605  // If null area, uses the global bounding box.
606  if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
607  bbbox = aBoard->ComputeBoundingBox();
608 
609  // Ensure non null area. If happen, gives a minimal size.
610  if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
611  bbbox.Inflate( Millimeter2iu( 1.0 ) );
612 
613  aOutlines.RemoveAllContours();
614  aOutlines.NewOutline();
615 
616  wxPoint corner;
617  aOutlines.Append( bbbox.GetOrigin() );
618 
619  corner.x = bbbox.GetOrigin().x;
620  corner.y = bbbox.GetEnd().y;
621  aOutlines.Append( corner );
622 
623  aOutlines.Append( bbbox.GetEnd() );
624 
625  corner.x = bbbox.GetEnd().x;
626  corner.y = bbbox.GetOrigin().y;
627  aOutlines.Append( corner );
628  }
629 
630  return success;
631 }
int GetCount() const
Function GetCount returns the number of objects in the list.
Definition: collector.h:106
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
Definition: eda_rect.h:112
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
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
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
Definition: eda_rect.h:118
bool ConvertOutlineToPolygon(std::vector< DRAWSEGMENT * > &aSegList, SHAPE_POLY_SET &aPolygons, 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.
usual segment : line with rounded ends
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:216
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 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:801
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)
a few functions useful in geometry calculations.
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&#39;s Inspector method, which does the collection.
Definition: collectors.cpp:498
const wxPoint GetEnd() const
Definition: eda_rect.h:114
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)
size_t i
Definition: json11.cpp:597
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.
Definition: eda_rect.h:44
int GetWidth() const
Definition: eda_rect.h:117
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:590
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) ...