KiCad PCB EDA Suite
polygon_2d.h File Reference
#include "object_2d.h"
#include "../accelerators/container_2d.h"
#include <geometry/shape_poly_set.h>
#include <vector>

Go to the source code of this file.

Classes

struct  POLYSEGMENT
 
struct  SEG_NORMALS
 
struct  SEGMENT_WITH_NORMALS
 
struct  OUTERS_AND_HOLES
 Handle a subset of a polygon. More...
 
class  POLYGON_2D
 Represent a sub polygon block. More...
 
class  DUMMY_BLOCK_2D
 A dummy block defined by a 2d box size. More...
 

Typedefs

typedef std::vector< POLYSEGMENTSEGMENTS
 
typedef std::vector< SEGMENT_WITH_NORMALSSEGMENTS_WIDTH_NORMALS
 List used to test ray2d intersections. More...
 

Functions

void ConvertPolygonToBlocks (const SHAPE_POLY_SET &aMainPath, CONTAINER_2D_BASE &aDstContainer, float aBiuTo3dUnitsScale, float aDivFactor, const BOARD_ITEM &aBoardItem, int aPolyIndex)
 Use a polygon in the format of the ClipperLib::Path and process it and create multiple 2d objects (POLYGON_2D and DUMMY_BLOCK_2D) that can be used to represent this polygon area. More...
 
void Polygon2d_TestModule ()
 

Typedef Documentation

◆ SEGMENTS

typedef std::vector< POLYSEGMENT > SEGMENTS

Definition at line 61 of file polygon_2d.h.

◆ SEGMENTS_WIDTH_NORMALS

List used to test ray2d intersections.

It will be a subset of an original polygon. The normals will be passed already interpolated.

Definition at line 69 of file polygon_2d.h.

Function Documentation

◆ ConvertPolygonToBlocks()

void ConvertPolygonToBlocks ( const SHAPE_POLY_SET aMainPath,
CONTAINER_2D_BASE aDstContainer,
float  aBiuTo3dUnitsScale,
float  aDivFactor,
const BOARD_ITEM aBoardItem,
int  aPolyIndex 
)

Use a polygon in the format of the ClipperLib::Path and process it and create multiple 2d objects (POLYGON_2D and DUMMY_BLOCK_2D) that can be used to represent this polygon area.

Parameters
aMainPaththe polygon are that was converted from the pcb board
aDstContainerthe destination container to put the created sub blocks
aBiuTo3dUnitsScalethe rendering target 3d scale
aDivFactora division factor (in 3Dunits) to divide the polygon plane, 0.0f will use the internal polygon segm statistics

Definition at line 378 of file polygon_2d.cpp.

381 {
382  // Get the path
383  wxASSERT( aPolyIndex < aMainPath.OutlineCount() );
384 
385  const SHAPE_LINE_CHAIN& path = aMainPath.COutline( aPolyIndex );
386 
387  BOX2I pathBounds = path.BBox();
388 
389  // Convert the points to segments class
390  BBOX_2D bbox;
391  bbox.Reset();
392 
393  // Contains the main list of segments and each segment normal interpolated
394  SEGMENTS_WIDTH_NORMALS segments_and_normals;
395 
396  // Contains a closed polygon used to calc if points are inside
397  SEGMENTS segments;
398 
399  segments_and_normals.reserve( path.PointCount() );
400  segments.reserve( path.PointCount() );
401 
402  SFVEC2F prevPoint;
403 
404  for( int i = 0; i < path.PointCount(); i++ )
405  {
406  const VECTOR2I& a = path.CPoint( i );
407 
408  const SFVEC2F point( (float) ( a.x ) * aBiuTo3dUnitsScale,
409  (float) ( -a.y ) * aBiuTo3dUnitsScale );
410 
411  // Only add points that are not coincident
412  if( ( i == 0 ) || ( fabs( prevPoint.x - point.x ) > FLT_EPSILON )
413  || ( fabs( prevPoint.y - point.y ) > FLT_EPSILON ) )
414  {
415  prevPoint = point;
416 
417  bbox.Union( point );
418 
420  sn.m_Start = point;
421  segments_and_normals.push_back( sn );
422 
423  POLYSEGMENT ps;
424  ps.m_Start = point;
425  segments.push_back( ps );
426  }
427  }
428 
429  bbox.ScaleNextUp();
430 
431  // Calc the slopes, normals and some statistics about this polygon
432  unsigned int i;
433  unsigned int j = segments_and_normals.size() - 1;
434 
435  // Temporary normal to the segment, it will later be used for interpolation
436  std::vector<SFVEC2F> tmpSegmentNormals;
437  tmpSegmentNormals.resize( segments_and_normals.size() );
438 
439  float medOfTheSquaresSegmentLength = 0.0f;
440 
441 #ifdef PRINT_STATISTICS_3D_VIEWER
442  float minLength = FLT_MAX;
443 #endif
444 
445  for( i = 0; i < segments_and_normals.size(); j = i++ )
446  {
447  const SFVEC2F slope = segments_and_normals[j].m_Start - segments_and_normals[i].m_Start;
448 
449  segments_and_normals[i].m_Precalc_slope = slope;
450 
451  // Calculate constants for each segment
452  segments[i].m_inv_JY_minus_IY =
453  1.0f / ( segments_and_normals[j].m_Start.y - segments_and_normals[i].m_Start.y );
454 
455  segments[i].m_JX_minus_IX =
456  ( segments_and_normals[j].m_Start.x - segments_and_normals[i].m_Start.x );
457 
458  // The normal orientation expect a fixed polygon orientation (!TODO: which one?)
459  //tmpSegmentNormals[i] = glm::normalize( SFVEC2F( -slope.y, +slope.x ) );
460  tmpSegmentNormals[i] = glm::normalize( SFVEC2F( slope.y, -slope.x ) );
461 
462  const float length = slope.x * slope.x + slope.y * slope.y;
463 
464 #ifdef PRINT_STATISTICS_3D_VIEWER
465  if( length < minLength )
466  minLength = length;
467 #endif
468 
469  medOfTheSquaresSegmentLength += length;
470  }
471 
472 #ifdef PRINT_STATISTICS_3D_VIEWER
473  float minSegmentLength = sqrt( minLength );
474 #endif
475 
476  // This calc an approximation of medium lengths, that will be used to calc
477  // the size of the division.
478  medOfTheSquaresSegmentLength /= segments_and_normals.size();
479  medOfTheSquaresSegmentLength = sqrt( medOfTheSquaresSegmentLength );
480 
481  // Compute the normal interpolation
482  // If calculate the dot between the segments, if they are above/below some
483  // threshold it will not interpolated it (ex: if you are in a edge corner
484  // or in a smooth transaction)
485  j = segments_and_normals.size() - 1;
486 
487  for( i = 0; i < segments_and_normals.size(); j = i++ )
488  {
489  const SFVEC2F normalBeforeSeg = tmpSegmentNormals[j];
490  const SFVEC2F normalSeg = tmpSegmentNormals[i];
491  const SFVEC2F normalAfterSeg = tmpSegmentNormals[( i + 1 ) % segments_and_normals.size()];
492 
493  const float dotBefore = glm::dot( normalBeforeSeg, normalSeg );
494  const float dotAfter = glm::dot( normalAfterSeg, normalSeg );
495 
496  if( dotBefore < 0.7f )
497  segments_and_normals[i].m_Normals.m_Start = normalSeg;
498  else
499  segments_and_normals[i].m_Normals.m_Start =
500  glm::normalize( ( normalBeforeSeg * dotBefore ) + normalSeg );
501 
502  if( dotAfter < 0.7f )
503  segments_and_normals[i].m_Normals.m_End = normalSeg;
504  else
505  segments_and_normals[i].m_Normals.m_End =
506  glm::normalize( ( normalAfterSeg * dotAfter ) + normalSeg );
507  }
508 
509  SFVEC2UI grid_divisions;
510 
511  if( aDivFactor < 0.0f )
512  {
513  grid_divisions = SFVEC2UI( 1 );
514  }
515  else
516  {
517  if( aDivFactor <= FLT_EPSILON )
518  aDivFactor = medOfTheSquaresSegmentLength;
519 
520  grid_divisions.x = (unsigned int) ( ( bbox.GetExtent().x / aDivFactor ) );
521  grid_divisions.y = (unsigned int) ( ( bbox.GetExtent().y / aDivFactor ) );
522 
523  grid_divisions = glm::clamp(
524  grid_divisions, SFVEC2UI( 1, 1 ), SFVEC2UI( MAX_NR_DIVISIONS, MAX_NR_DIVISIONS ) );
525  }
526 
527  // Calculate the steps advance of the grid
528  SFVEC2F blockAdvance;
529 
530  blockAdvance.x = bbox.GetExtent().x / (float) grid_divisions.x;
531  blockAdvance.y = bbox.GetExtent().y / (float) grid_divisions.y;
532 
533  wxASSERT( blockAdvance.x > 0.0f );
534  wxASSERT( blockAdvance.y > 0.0f );
535 
536  const int leftToRight_inc = ( pathBounds.GetRight() - pathBounds.GetLeft() ) / grid_divisions.x;
537 
538  const int topToBottom_inc = ( pathBounds.GetBottom() - pathBounds.GetTop() ) / grid_divisions.y;
539 
540  // Statistics
541  unsigned int stats_n_empty_blocks = 0;
542  unsigned int stats_n_dummy_blocks = 0;
543  unsigned int stats_n_poly_blocks = 0;
544  unsigned int stats_sum_size_of_polygons = 0;
545 
546  // Step by each block of a grid trying to extract segments and create polygon blocks
547  int topToBottom = pathBounds.GetTop();
548  float blockY = bbox.Max().y;
549 
550  for( unsigned int iy = 0; iy < grid_divisions.y; iy++ )
551  {
552  int leftToRight = pathBounds.GetLeft();
553  float blockX = bbox.Min().x;
554 
555  for( unsigned int ix = 0; ix < grid_divisions.x; ix++ )
556  {
557  BBOX_2D blockBox( SFVEC2F( blockX, blockY - blockAdvance.y ),
558  SFVEC2F( blockX + blockAdvance.x, blockY ) );
559 
560  // Make the box large to it will catch (intersect) the edges
561  blockBox.ScaleNextUp();
562  blockBox.ScaleNextUp();
563  blockBox.ScaleNextUp();
564 
565  SEGMENTS_WIDTH_NORMALS extractedSegments;
566 
567  extractPathsFrom( segments_and_normals, blockBox, extractedSegments );
568 
569  if( extractedSegments.empty() )
570  {
571 
572  SFVEC2F p1( blockBox.Min().x, blockBox.Min().y );
573  SFVEC2F p2( blockBox.Max().x, blockBox.Min().y );
574  SFVEC2F p3( blockBox.Max().x, blockBox.Max().y );
575  SFVEC2F p4( blockBox.Min().x, blockBox.Max().y );
576 
577  if( polygon_IsPointInside( segments, p1 ) || polygon_IsPointInside( segments, p2 )
578  || polygon_IsPointInside( segments, p3 )
579  || polygon_IsPointInside( segments, p4 ) )
580  {
581  // In this case, the segments are not intersecting the
582  // polygon, so it means that if any point is inside it,
583  // then all other are inside the polygon.
584  // This is a full bbox inside, so add a dummy box
585  aDstContainer.Add( new DUMMY_BLOCK_2D( blockBox, aBoardItem ) );
586  stats_n_dummy_blocks++;
587  }
588  else
589  {
590  // Points are outside, so this block completely missed the polygon
591  // In this case, no objects need to be added
592  stats_n_empty_blocks++;
593  }
594  }
595  else
596  {
597  // At this point, the borders of polygon were intersected by the
598  // bounding box, so we must calculate a new polygon that will
599  // close that small block.
600  // This block will be used to calculate if points are inside
601  // the (sub block) polygon.
602 
603  SHAPE_POLY_SET subBlockPoly;
604 
605  SHAPE_LINE_CHAIN sb = SHAPE_LINE_CHAIN( { VECTOR2I( leftToRight, topToBottom ),
606  VECTOR2I( leftToRight + leftToRight_inc, topToBottom ),
607  VECTOR2I( leftToRight + leftToRight_inc, topToBottom + topToBottom_inc ),
608  VECTOR2I( leftToRight, topToBottom + topToBottom_inc ) } );
609 
610  //sb.Append( leftToRight, topToBottom );
611  sb.SetClosed( true );
612 
613  subBlockPoly.AddOutline( sb );
614 
615  // We need here a strictly simple polygon with outlines and holes
616  SHAPE_POLY_SET solution;
617  solution.BooleanIntersection( aMainPath, subBlockPoly,
619 
620  OUTERS_AND_HOLES outersAndHoles;
621 
622  outersAndHoles.m_Holes.clear();
623  outersAndHoles.m_Outers.clear();
624 
625  for( int idx = 0; idx < solution.OutlineCount(); idx++ )
626  {
627  const SHAPE_LINE_CHAIN& outline = solution.Outline( idx );
628 
629  SEGMENTS solutionSegment;
630 
631  polygon_Convert( outline, solutionSegment, aBiuTo3dUnitsScale );
632  outersAndHoles.m_Outers.push_back( solutionSegment );
633 
634  stats_sum_size_of_polygons += solutionSegment.size();
635 
636  for( int holeIdx = 0; holeIdx < solution.HoleCount( idx ); holeIdx++ )
637  {
638  const SHAPE_LINE_CHAIN& hole = solution.Hole( idx, holeIdx );
639 
640  polygon_Convert( hole, solutionSegment, aBiuTo3dUnitsScale );
641  outersAndHoles.m_Holes.push_back( solutionSegment );
642  stats_sum_size_of_polygons += solutionSegment.size();
643  }
644  }
645 
646  if( !outersAndHoles.m_Outers.empty() )
647  {
648  aDstContainer.Add( new POLYGON_2D( extractedSegments, outersAndHoles,
649  aBoardItem ) );
650  stats_n_poly_blocks++;
651  }
652  }
653 
654  blockX += blockAdvance.x;
655  leftToRight += leftToRight_inc;
656  }
657 
658  blockY -= blockAdvance.y;
659  topToBottom += topToBottom_inc;
660  }
661 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
SFVEC2F GetExtent() const
Definition: bbox_2d.cpp:125
coord_type GetTop() const
Definition: box2.h:187
Define a general 2D-vector/point.
Definition: vector2d.h:61
std::vector< SEGMENT_WITH_NORMALS > SEGMENTS_WIDTH_NORMALS
List used to test ray2d intersections.
Definition: polygon_2d.h:69
coord_type GetRight() const
Definition: box2.h:182
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
SFVEC2F m_Start
Definition: polygon_2d.h:40
coord_type GetBottom() const
Definition: box2.h:183
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
A 2D bounding box built on top of an origin point and size vector.
Definition: box2.h:41
static void extractPathsFrom(const SEGMENTS_WIDTH_NORMALS &aSegList, const BBOX_2D &aBBox, SEGMENTS_WIDTH_NORMALS &aOutSegThatIntersect)
Definition: polygon_2d.cpp:305
void Add(OBJECT_2D *aObject)
Definition: container_2d.h:49
glm::uvec2 SFVEC2UI
Definition: xv3d_types.h:38
const SFVEC2F & Max() const
Definition: bbox_2d.h:172
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
glm::vec2 SFVEC2F
Definition: xv3d_types.h:42
void Reset()
Reset the bounding box to zero and uninitialize it.
Definition: bbox_2d.cpp:86
Represent a set of closed polygons.
SHAPE_LINE_CHAIN & Outline(int aIndex)
static bool polygon_IsPointInside(const SEGMENTS &aSegments, const SFVEC2F &aPoint)
Definition: polygon_2d.cpp:34
std::vector< SEGMENTS > m_Outers
Definition: polygon_2d.h:80
Handle a subset of a polygon.
Definition: polygon_2d.h:78
static void polygon_Convert(const SHAPE_LINE_CHAIN &aPath, SEGMENTS &aOutSegment, float aBiuTo3dUnitsScale)
Definition: polygon_2d.cpp:351
Manage a bounding box defined by two SFVEC2F min max points.
Definition: bbox_2d.h:41
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
std::vector< SEGMENTS > m_Holes
Definition: polygon_2d.h:81
void Union(const SFVEC2F &aPoint)
Recalculate the bounding box adding a point.
Definition: bbox_2d.cpp:93
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
std::vector< POLYSEGMENT > SEGMENTS
Definition: polygon_2d.h:61
const SFVEC2F & Min() const
Definition: bbox_2d.h:167
Represent a polyline (an zero-thickness chain of connected line segments).
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
void ScaleNextUp()
Scale a bounding box to the next float representation making it larger.
Definition: bbox_2d.cpp:162
coord_type GetLeft() const
Definition: box2.h:186
Represent a sub polygon block.
Definition: polygon_2d.h:93
A dummy block defined by a 2d box size.
Definition: polygon_2d.h:126
#define MAX_NR_DIVISIONS
Definition: polygon_2d.cpp:270

References CONTAINER_2D_BASE::Add(), SHAPE_POLY_SET::AddOutline(), SHAPE_POLY_SET::BooleanIntersection(), SHAPE_POLY_SET::COutline(), extractPathsFrom(), BOX2< Vec >::GetBottom(), BBOX_2D::GetExtent(), BOX2< Vec >::GetLeft(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetTop(), SHAPE_POLY_SET::Hole(), SHAPE_POLY_SET::HoleCount(), OUTERS_AND_HOLES::m_Holes, OUTERS_AND_HOLES::m_Outers, POLYSEGMENT::m_Start, SEGMENT_WITH_NORMALS::m_Start, BBOX_2D::Max(), MAX_NR_DIVISIONS, BBOX_2D::Min(), SHAPE_POLY_SET::Outline(), SHAPE_POLY_SET::OutlineCount(), path, SHAPE_POLY_SET::PM_STRICTLY_SIMPLE, polygon_Convert(), polygon_IsPointInside(), BBOX_2D::Reset(), BBOX_2D::ScaleNextUp(), SHAPE_LINE_CHAIN::SetClosed(), BBOX_2D::Union(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by RENDER_3D_RAYTRACE::Reload().

◆ Polygon2d_TestModule()

void Polygon2d_TestModule ( )