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 
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 
181 bool ConvertOutlineToPolygon( std::vector< DRAWSEGMENT* >& aSegList,
182  SHAPE_POLY_SET& aPolygons, int aSegmentsByCircle,
183  wxString* aErrorText )
184 {
185 
186  if( aSegList.size() == 0 )
187  return true;
188 
189  wxString msg;
190 
191  // Make a working copy of aSegList, because the list is modified during calculations
192  std::vector< DRAWSEGMENT* > segList = aSegList;
193 
194  unsigned prox; // a proximity BIU metric, not an accurate distance
195  DRAWSEGMENT* graphic;
196  wxPoint prevPt;
197 
198  // Find edge point with minimum x, this should be in the outer polygon
199  // which will define the perimeter Edge.Cuts polygon.
200  wxPoint xmin = wxPoint( INT_MAX, 0 );
201  int xmini = 0;
202 
203  for( size_t i = 0; i < segList.size(); i++ )
204  {
205  graphic = (DRAWSEGMENT*) segList[i];
206 
207  switch( graphic->GetShape() )
208  {
209  case S_SEGMENT:
210  {
211  if( graphic->GetStart().x < xmin.x )
212  {
213  xmin = graphic->GetStart();
214  xmini = i;
215  }
216 
217  if( graphic->GetEnd().x < xmin.x )
218  {
219  xmin = graphic->GetEnd();
220  xmini = i;
221  }
222  }
223  break;
224 
225  case S_ARC:
226  // Freerouter does not yet understand arcs, so approximate
227  // an arc with a series of short lines and put those
228  // line segments into the !same! PATH.
229  {
230  wxPoint pstart = graphic->GetArcStart();
231  wxPoint center = graphic->GetCenter();
232  double angle = -graphic->GetAngle();
233  int steps = aSegmentsByCircle * fabs(angle) /3600.0;
234 
235  if( steps == 0 )
236  steps = 1;
237 
238  wxPoint pt;
239 
240  for( int step = 1; step<=steps; ++step )
241  {
242  double rotation = ( angle * step ) / steps;
243 
244  pt = pstart;
245 
246  RotatePoint( &pt, center, rotation );
247 
248  if( pt.x < xmin.x )
249  {
250  xmin = pt;
251  xmini = i;
252  }
253  }
254  }
255  break;
256 
257  case S_CIRCLE:
258  {
259  wxPoint pt = graphic->GetCenter();
260 
261  // pt has minimum x point
262  pt.x -= graphic->GetRadius();
263 
264  // when the radius <= 0, this is a mal-formed circle. Skip it
265  if( graphic->GetRadius() > 0 && pt.x < xmin.x )
266  {
267  xmin = pt;
268  xmini = i;
269  }
270  }
271  break;
272 
273  default:
274  break;
275  }
276  }
277 
278  // Grab the left most point, assume its on the board's perimeter, and see if we
279  // can put enough graphics together by matching endpoints to formulate a cohesive
280  // polygon.
281 
282  graphic = (DRAWSEGMENT*) segList[xmini];
283 
284  // The first DRAWSEGMENT is in 'graphic', ok to remove it from 'items'
285  segList.erase( segList.begin() + xmini );
286 
287  // Set maximum proximity threshold for point to point nearness metric for
288  // board perimeter only, not interior keepouts yet.
289  prox = Millimeter2iu( 0.01 ); // should be enough to fix rounding issues
290  // is arc start and end point calculations
291 
292  // Output the Edge.Cuts perimeter as circle or polygon.
293  if( graphic->GetShape() == S_CIRCLE )
294  {
295  TransformCircleToPolygon( aPolygons, graphic->GetCenter(),
296  graphic->GetRadius(), aSegmentsByCircle );
297  }
298  else
299  {
300  // Polygon start point. Arbitrarily chosen end of the
301  // segment and build the poly from here.
302 
303  wxPoint startPt = wxPoint( graphic->GetEnd() );
304  prevPt = graphic->GetEnd();
305  aPolygons.NewOutline();
306  aPolygons.Append( prevPt );
307 
308  // Do not append the other end point yet of this 'graphic', this first
309  // 'graphic' might be an arc.
310 
311  for(;;)
312  {
313  switch( graphic->GetShape() )
314  {
315  case S_SEGMENT:
316  {
317  wxPoint nextPt;
318 
319  // Use the line segment end point furthest away from
320  // prevPt as we assume the other end to be ON prevPt or
321  // very close to it.
322 
323  if( close_st( prevPt, graphic->GetStart(), graphic->GetEnd() ) )
324  {
325  nextPt = graphic->GetEnd();
326  }
327  else
328  {
329  nextPt = graphic->GetStart();
330  }
331 
332  aPolygons.Append( nextPt );
333  prevPt = nextPt;
334  }
335  break;
336 
337  case S_ARC:
338  // We do not support arcs in polygons, so approximate
339  // an arc with a series of short lines and put those
340  // line segments into the !same! PATH.
341  {
342  wxPoint pstart = graphic->GetArcStart();
343  wxPoint pend = graphic->GetArcEnd();
344  wxPoint pcenter = graphic->GetCenter();
345  double angle = -graphic->GetAngle();
346  int steps = aSegmentsByCircle * fabs(angle) /3600.0;
347 
348  if( steps == 0 )
349  steps = 1;
350 
351  if( !close_enough( prevPt, pstart, prox ) )
352  {
353  wxASSERT( close_enough( prevPt, graphic->GetArcEnd(), prox ) );
354 
355  angle = -angle;
356  std::swap( pstart, pend );
357  }
358 
359  wxPoint nextPt;
360 
361  for( int step = 1; step<=steps; ++step )
362  {
363  double rotation = ( angle * step ) / steps;
364  nextPt = pstart;
365  RotatePoint( &nextPt, pcenter, rotation );
366 
367  aPolygons.Append( nextPt );
368  }
369 
370  prevPt = nextPt;
371  }
372  break;
373 
374  default:
375  if( aErrorText )
376  {
377  msg.Printf( _( "Unsupported DRAWSEGMENT type %s" ),
378  GetChars( BOARD_ITEM::ShowShape( graphic->GetShape() ) ) );
379 
380  *aErrorText << msg << "\n";
381  }
382 
383  return false;
384  }
385 
386  // Get next closest segment.
387 
388  graphic = findPoint( prevPt, segList, prox );
389 
390  // If there are no more close segments, check if the board
391  // outline polygon can be closed.
392 
393  if( !graphic )
394  {
395  if( close_enough( startPt, prevPt, prox ) )
396  {
397  // Close the polygon back to start point
398  // aPolygons.Append( startPt ); // not needed
399  }
400  else
401  {
402  if( aErrorText )
403  {
404  msg.Printf(
405  _( "Unable to find the next boundary segment with an endpoint of (%s mm, %s mm). "
406  "graphic outline must form a contiguous, closed polygon." ),
407  GetChars( FROM_UTF8( BOARD_ITEM::FormatInternalUnits( prevPt.x ).c_str() ) ),
408  GetChars( FROM_UTF8( BOARD_ITEM::FormatInternalUnits( prevPt.y ).c_str() ) )
409  );
410 
411  *aErrorText << msg << "\n";
412  }
413 
414  return false;
415  }
416  break;
417  }
418  }
419  }
420 
421  // Output the interior Edge.Cuts graphics as keepouts, using same nearness
422  // metric as the board edge as otherwise we have trouble completing complex
423  // polygons.
424  prox = Millimeter2iu( 0.05 );
425 
426  while( segList.size() )
427  {
428  // emit a signal layers keepout for every interior polygon left...
429  int hole = aPolygons.NewHole();
430 
431  graphic = (DRAWSEGMENT*) segList[0];
432  segList.erase( segList.begin() );
433 
434  if( graphic->GetShape() == S_CIRCLE )
435  {
436  // make a circle by segments;
437  wxPoint center = graphic->GetCenter();
438  double angle = 3600.0;
439  wxPoint start = center;
440  int radius = graphic->GetRadius();
441  start.x += radius;
442 
443  wxPoint nextPt;
444 
445  for( int step = 0; step<aSegmentsByCircle; ++step )
446  {
447  double rotation = ( angle * step ) / aSegmentsByCircle;
448  nextPt = start;
449  RotatePoint( &nextPt.x, &nextPt.y, center.x, center.y, rotation );
450  aPolygons.Append( nextPt, -1, hole );
451  }
452  }
453  else
454  {
455  // Polygon start point. Arbitrarily chosen end of the
456  // segment and build the poly from here.
457 
458  wxPoint startPt( graphic->GetEnd() );
459  prevPt = graphic->GetEnd();
460  aPolygons.Append( prevPt, -1, hole );
461 
462  // do not append the other end point yet, this first 'graphic' might be an arc
463  for(;;)
464  {
465  switch( graphic->GetShape() )
466  {
467  case S_SEGMENT:
468  {
469  wxPoint nextPt;
470 
471  // Use the line segment end point furthest away from
472  // prevPt as we assume the other end to be ON prevPt or
473  // very close to it.
474 
475  if( close_st( prevPt, graphic->GetStart(), graphic->GetEnd() ) )
476  {
477  nextPt = graphic->GetEnd();
478  }
479  else
480  {
481  nextPt = graphic->GetStart();
482  }
483 
484  prevPt = nextPt;
485  aPolygons.Append( prevPt, -1, hole );
486  }
487  break;
488 
489  case S_ARC:
490  // Freerouter does not yet understand arcs, so approximate
491  // an arc with a series of short lines and put those
492  // line segments into the !same! PATH.
493  {
494  wxPoint pstart = graphic->GetArcStart();
495  wxPoint pend = graphic->GetArcEnd();
496  wxPoint pcenter = graphic->GetCenter();
497  double angle = -graphic->GetAngle();
498  int steps = aSegmentsByCircle * fabs(angle) /3600.0;
499 
500  if( steps == 0 )
501  steps = 1;
502 
503  if( !close_enough( prevPt, pstart, prox ) )
504  {
505  wxASSERT( close_enough( prevPt, graphic->GetArcEnd(), prox ) );
506 
507  angle = -angle;
508  std::swap( pstart, pend );
509  }
510 
511  wxPoint nextPt;
512 
513  for( int step = 1; step <= steps; ++step )
514  {
515  double rotation = ( angle * step ) / steps;
516 
517  nextPt = pstart;
518  RotatePoint( &nextPt, pcenter, rotation );
519 
520  aPolygons.Append( nextPt, -1, hole );
521  }
522 
523  prevPt = nextPt;
524  }
525  break;
526 
527  default:
528  if( aErrorText )
529  {
530  msg.Printf(
531  _( "Unsupported DRAWSEGMENT type %s" ),
532  GetChars( BOARD_ITEM::ShowShape( graphic->GetShape() ) ) );
533 
534  *aErrorText << msg << "\n";
535  }
536 
537  return false;
538  }
539 
540  // Get next closest segment.
541 
542  graphic = findPoint( prevPt, segList, prox );
543 
544  // If there are no more close segments, check if polygon
545  // can be closed.
546 
547  if( !graphic )
548  {
549  if( close_enough( startPt, prevPt, prox ) )
550  {
551  // Close the polygon back to start point
552  // aPolygons.Append( startPt, -1, hole ); // not needed
553  }
554  else
555  {
556  if( aErrorText )
557  {
558  msg.Printf(
559  _( "Unable to find the next graphic segment with an endpoint of (%s mm, %s mm).\n"
560  "Edit graphics, making them contiguous polygons each." ),
561  GetChars( FROM_UTF8( BOARD_ITEM::FormatInternalUnits( prevPt.x ).c_str() ) ),
562  GetChars( FROM_UTF8( BOARD_ITEM::FormatInternalUnits( prevPt.y ).c_str() ) )
563  );
564 
565  *aErrorText << msg << "\n";
566  }
567 
568  return false;
569  }
570  break;
571  }
572  }
573  }
574  }
575 
576  return true;
577 }
578 
579 #include <class_board.h>
580 #include <collectors.h>
581 
582 /* This function is used to extract a board outlines (3D view, automatic zones build ...)
583  * Any closed outline inside the main outline is a hole
584  * All contours should be closed, i.e. valid closed polygon vertices
585  */
587  SHAPE_POLY_SET& aOutlines,
588  wxString* aErrorText )
589 {
590  PCB_TYPE_COLLECTOR items;
591 
592  // Get all the DRAWSEGMENTS and module graphics into 'items',
593  // then keep only those on layer == Edge_Cuts.
594  static const KICAD_T scan_graphics[] = { PCB_LINE_T, PCB_MODULE_EDGE_T, EOT };
595  items.Collect( aBoard, scan_graphics );
596 
597  // Make a working copy of aSegList, because the list is modified during calculations
598  std::vector< DRAWSEGMENT* > segList;
599 
600  for( int ii = 0; ii < items.GetCount(); ii++ )
601  {
602  if( items[ii]->GetLayer() == Edge_Cuts )
603  segList.push_back( static_cast< DRAWSEGMENT* >( items[ii] ) );
604  }
605 
606  const int STEPS = 36; // for a segmentation of an arc of 360 degrees
607  bool success = ConvertOutlineToPolygon( segList, aOutlines, STEPS, aErrorText );
608 
609  if( !success || !aOutlines.OutlineCount() )
610  {
611  // Creates a valid polygon outline is not possible.
612  // So uses the board edge cuts bounding box to create a
613  // rectangular outline
614  // When no edge cuts items, build a contour
615  // from global bounding box
616 
617  EDA_RECT bbbox = aBoard->GetBoardEdgesBoundingBox();
618 
619  // If null area, uses the global bounding box.
620  if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
621  bbbox = aBoard->ComputeBoundingBox();
622 
623  // Ensure non null area. If happen, gives a minimal size.
624  if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
625  bbbox.Inflate( Millimeter2iu( 1.0 ) );
626 
627  aOutlines.RemoveAllContours();
628  aOutlines.NewOutline();
629 
630  wxPoint corner;
631  aOutlines.Append( bbbox.GetOrigin() );
632 
633  corner.x = bbbox.GetOrigin().x;
634  corner.y = bbbox.GetEnd().y;
635  aOutlines.Append( corner );
636 
637  aOutlines.Append( bbbox.GetEnd() );
638 
639  corner.x = bbbox.GetEnd().x;
640  corner.y = bbbox.GetOrigin().y;
641  aOutlines.Append( corner );
642  }
643 
644  return success;
645 }
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.
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:106
search types array terminator (End Of Types)
Definition: typeinfo.h:94
KICAD_T
Enum KICAD_T is the set of class identification values, stored in EDA_ITEM::m_StructType.
Definition: typeinfo.h:90
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:839
const wxPoint & GetOrigin() const
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[])
Function Collect scans a BOARD_ITEM using this class's Inspector method, which does the collection...
Definition: collectors.cpp:488
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:166
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)
Function findPoint searches for a DRAWSEGMENT with an end point or start point of aPoint...
Class EDA_RECT handles the component boundary box.
int GetWidth() const
static bool GetLayer(MODEL_VRML &aModel, LAYER_NUM layer, VRML_LAYER **vlayer)
Class PCB_TYPE_COLLECTOR merely gathers up all BOARD_ITEMs of a given set of KICAD_T type(s)...
Definition: collectors.h:593
class DRAWSEGMENT, a segment not on copper layers
Definition: typeinfo.h:103
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) ...