KiCad PCB EDA Suite
cpolygon2d.h File Reference
#include "cobject2d.h"
#include "../accelerators/ccontainer2d.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
 This structured will be used to handle a sub set of a polygon. More...
 
class  CPOLYGONBLOCK2D
 This class represents a sub polygon block. More...
 
class  CDUMMYBLOCK2D
 This dummy block will be defined by a 2d box size. More...
 

Typedefs

typedef std::vector< POLYSEGMENTSEGMENTS
 
typedef std::vector< SEGMENT_WITH_NORMALSSEGMENTS_WIDTH_NORMALS
 This list will be used to test ray2d intersections. More...
 

Functions

void Convert_path_polygon_to_polygon_blocks_and_dummy_blocks (const SHAPE_POLY_SET &aMainPath, CGENERICCONTAINER2D &aDstContainer, float aBiuTo3DunitsScale, float aDivFactor, const BOARD_ITEM &aBoardItem, int aPolyIndex)
 Convert_path_polygon_to_polygon_blocks_and_dummy_blocks This function will use a polygon in the format of the ClipperLib::Path will process it and will create multiple 2d objects (CPOLYGONBLOCK2D and CDUMMYBLOCK2D) that can be used to represent this polygon area. More...
 
void Polygon2d_TestModule ()
 

Typedef Documentation

◆ SEGMENTS

typedef std::vector< POLYSEGMENT > SEGMENTS

Definition at line 62 of file cpolygon2d.h.

◆ SEGMENTS_WIDTH_NORMALS

This list will be used to test ray2d intersections.

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

Definition at line 67 of file cpolygon2d.h.

Function Documentation

◆ Convert_path_polygon_to_polygon_blocks_and_dummy_blocks()

void Convert_path_polygon_to_polygon_blocks_and_dummy_blocks ( const SHAPE_POLY_SET aMainPath,
CGENERICCONTAINER2D aDstContainer,
float  aBiuTo3DunitsScale,
float  aDivFactor,
const BOARD_ITEM aBoardItem,
int  aPolyIndex 
)

Convert_path_polygon_to_polygon_blocks_and_dummy_blocks This function will use a polygon in the format of the ClipperLib::Path will process it and will create multiple 2d objects (CPOLYGONBLOCK2D and CDUMMYBLOCK2D) that can be used to represent this polygon area.

Parameters
aMainPath- the polygon are that was converted from the pcb board
aDstContainer- the destination container to put the created sub blocks
aBiuTo3DunitsScale- the rendering target 3d scale
aDivFactor- a division factor (in 3Dunits) to divide the polygon plane, 0.0f will use the internal polygon segm statistics

Definition at line 403 of file cpolygon2d.cpp.

410 {
411  // Get the path
412 
413  wxASSERT( aPolyIndex < aMainPath.OutlineCount() );
414 
415  const SHAPE_LINE_CHAIN& path = aMainPath.COutline( aPolyIndex );
416 
417  BOX2I pathBounds = path.BBox();
418 
419  // Convert the points to segments class
420  CBBOX2D bbox;
421  bbox.Reset();
422 
423  // Contains the main list of segments and each segment normal interpolated
424  SEGMENTS_WIDTH_NORMALS segments_and_normals;
425 
426  // Contains a closed polygon used to calc if points are inside
427  SEGMENTS segments;
428 
429  segments_and_normals.reserve( path.PointCount() );
430  segments.reserve( path.PointCount() );
431 
432  SFVEC2F prevPoint;
433 
434  for( int i = 0; i < path.PointCount(); i++ )
435  {
436  const VECTOR2I& a = path.CPoint( i );
437 
438  const SFVEC2F point ( (float)( a.x) * aBiuTo3DunitsScale,
439  (float)(-a.y) * aBiuTo3DunitsScale );
440 
441  // Only add points that are not coincident
442  if( (i == 0) ||
443  (fabs(prevPoint.x - point.x) > FLT_EPSILON) ||
444  (fabs(prevPoint.y - point.y) > FLT_EPSILON) )
445  {
446  prevPoint = point;
447 
448  bbox.Union( point );
449 
451  sn.m_Start = point;
452  segments_and_normals.push_back( sn );
453 
454  POLYSEGMENT ps;
455  ps.m_Start = point;
456  segments.push_back( ps );
457  }
458  }
459 
460  bbox.ScaleNextUp();
461 
462 
463  // Calc the slopes, normals and some statistics about this polygon
464  unsigned int i;
465  unsigned int j = segments_and_normals.size() - 1;
466 
467  // Temporary normal to the segment, it will later be used for interpolation
468  std::vector< SFVEC2F > tmpSegmentNormals;
469  tmpSegmentNormals.resize( segments_and_normals.size() );
470 
471  float medOfTheSquaresSegmentLength = 0.0f;
472 #ifdef PRINT_STATISTICS_3D_VIEWER
473  float minLength = FLT_MAX;
474 #endif
475 
476  for( i = 0; i < segments_and_normals.size(); j = i++ )
477  {
478  const SFVEC2F slope = segments_and_normals[j].m_Start -
479  segments_and_normals[i].m_Start;
480 
481  segments_and_normals[i].m_Precalc_slope = slope;
482 
483  // Calculate constants for each segment
484  segments[i].m_inv_JY_minus_IY = 1.0f / ( segments_and_normals[j].m_Start.y -
485  segments_and_normals[i].m_Start.y );
486 
487  segments[i].m_JX_minus_IX = ( segments_and_normals[j].m_Start.x -
488  segments_and_normals[i].m_Start.x );
489 
490  // The normal orientation expect a fixed polygon orientation (!TODO: which one?)
491  //tmpSegmentNormals[i] = glm::normalize( SFVEC2F( -slope.y, +slope.x ) );
492  tmpSegmentNormals[i] = glm::normalize( SFVEC2F( slope.y, -slope.x ) );
493 
494  const float length = slope.x * slope.x + slope.y * slope.y;
495 
496 #ifdef PRINT_STATISTICS_3D_VIEWER
497  if( length < minLength )
498  minLength = length;
499 #endif
500 
501  medOfTheSquaresSegmentLength += length;
502  }
503 
504 #ifdef PRINT_STATISTICS_3D_VIEWER
505  float minSegmentLength = sqrt( minLength );
506 #endif
507 
508  // This calc an approximation of medium lengths, that will be used to calc
509  // the size of the division.
510  medOfTheSquaresSegmentLength /= segments_and_normals.size();
511  medOfTheSquaresSegmentLength = sqrt( medOfTheSquaresSegmentLength );
512 
513 
514  // Compute the normal interpolation
515  // If calculate the dot between the segments, if they are above/below some
516  // threshould it will not interpolated it (ex: if you are in a edge corner
517  // or in a smooth transaction)
518  j = segments_and_normals.size() - 1;
519  for( i = 0; i < segments_and_normals.size(); j = i++ )
520  {
521  const SFVEC2F normalBeforeSeg = tmpSegmentNormals[j];
522  const SFVEC2F normalSeg = tmpSegmentNormals[i];
523  const SFVEC2F normalAfterSeg = tmpSegmentNormals[ (i + 1) %
524  segments_and_normals.size() ];
525 
526  const float dotBefore = glm::dot( normalBeforeSeg, normalSeg );
527  const float dotAfter = glm::dot( normalAfterSeg, normalSeg );
528 
529  if( dotBefore < 0.7f )
530  segments_and_normals[i].m_Normals.m_Start = normalSeg;
531  else
532  segments_and_normals[i].m_Normals.m_Start =
533  glm::normalize( (normalBeforeSeg * dotBefore ) + normalSeg );
534 
535  if( dotAfter < 0.7f )
536  segments_and_normals[i].m_Normals.m_End = normalSeg;
537  else
538  segments_and_normals[i].m_Normals.m_End =
539  glm::normalize( (normalAfterSeg * dotAfter ) + normalSeg );
540  }
541 
542  if( aDivFactor == 0.0f )
543  aDivFactor = medOfTheSquaresSegmentLength;
544 
545  SFVEC2UI grid_divisions;
546  grid_divisions.x = (unsigned int)( (bbox.GetExtent().x / aDivFactor) );
547  grid_divisions.y = (unsigned int)( (bbox.GetExtent().y / aDivFactor) );
548 
549  grid_divisions = glm::clamp( grid_divisions ,
550  SFVEC2UI( 1, 1 ),
552 
553  // Calculate the steps advance of the grid
554  SFVEC2F blockAdvance;
555 
556  blockAdvance.x = bbox.GetExtent().x / (float)grid_divisions.x;
557  blockAdvance.y = bbox.GetExtent().y / (float)grid_divisions.y;
558 
559  wxASSERT( blockAdvance.x > 0.0f );
560  wxASSERT( blockAdvance.y > 0.0f );
561 
562  const int leftToRight_inc = (pathBounds.GetRight() - pathBounds.GetLeft()) /
563  grid_divisions.x;
564 
565  const int topToBottom_inc = (pathBounds.GetBottom() - pathBounds.GetTop()) /
566  grid_divisions.y;
567 
568  // Statistics
569  unsigned int stats_n_empty_blocks = 0;
570  unsigned int stats_n_dummy_blocks = 0;
571  unsigned int stats_n_poly_blocks = 0;
572  unsigned int stats_sum_size_of_polygons = 0;
573 
574 
575  // Step by each block of a grid trying to extract segments and create
576  // polygon blocks
577 
578  int topToBottom = pathBounds.GetTop();
579  float blockY = bbox.Max().y;
580 
581  for( unsigned int iy = 0; iy < grid_divisions.y; iy++ )
582  {
583 
584  int leftToRight = pathBounds.GetLeft();
585  float blockX = bbox.Min().x;
586 
587  for( unsigned int ix = 0; ix < grid_divisions.x; ix++ )
588  {
589  CBBOX2D blockBox( SFVEC2F( blockX,
590  blockY - blockAdvance.y ),
591  SFVEC2F( blockX + blockAdvance.x,
592  blockY ) );
593 
594  // Make the box large to it will catch (intersect) the edges
595  blockBox.ScaleNextUp();
596  blockBox.ScaleNextUp();
597  blockBox.ScaleNextUp();
598 
599  SEGMENTS_WIDTH_NORMALS extractedSegments;
600 
601  extractPathsFrom( segments_and_normals, blockBox, extractedSegments );
602 
603 
604  if( extractedSegments.empty() )
605  {
606 
607  SFVEC2F p1( blockBox.Min().x, blockBox.Min().y );
608  SFVEC2F p2( blockBox.Max().x, blockBox.Min().y );
609  SFVEC2F p3( blockBox.Max().x, blockBox.Max().y );
610  SFVEC2F p4( blockBox.Min().x, blockBox.Max().y );
611 
612  if( polygon_IsPointInside( segments, p1 ) ||
613  polygon_IsPointInside( segments, p2 ) ||
614  polygon_IsPointInside( segments, p3 ) ||
615  polygon_IsPointInside( segments, p4 ) )
616  {
617  // In this case, the segments are not intersecting the
618  // polygon, so it means that if any point is inside it,
619  // then all other are inside the polygon.
620  // This is a full bbox inside, so add a dummy box
621 
622  aDstContainer.Add( new CDUMMYBLOCK2D( blockBox, aBoardItem ) );
623  stats_n_dummy_blocks++;
624  }
625  else
626  {
627  // Points are outside, so this block complety missed the polygon
628  // In this case, no objects need to be added
629  stats_n_empty_blocks++;
630  }
631  }
632  else
633  {
634  // At this point, the borders of polygon were intersected by the
635  // bounding box, so we must calculate a new polygon that will
636  // close that small block.
637  // This block will be used to calculate if points are inside
638  // the (sub block) polygon.
639 
640  SHAPE_POLY_SET subBlockPoly;
641 
642  SHAPE_LINE_CHAIN sb = SHAPE_LINE_CHAIN( { VECTOR2I( leftToRight, topToBottom ),
643  VECTOR2I( leftToRight + leftToRight_inc, topToBottom ),
644  VECTOR2I( leftToRight + leftToRight_inc, topToBottom + topToBottom_inc ),
645  VECTOR2I( leftToRight, topToBottom + topToBottom_inc ) } );
646 
647  //sb.Append( leftToRight, topToBottom );
648  sb.SetClosed( true );
649 
650  subBlockPoly.AddOutline( sb );
651 
652  // We need here a strictly simple polygon with outlines and holes
653  SHAPE_POLY_SET solution;
654  solution.BooleanIntersection( aMainPath,
655  subBlockPoly,
657 
658  OUTERS_AND_HOLES outersAndHoles;
659 
660  outersAndHoles.m_Holes.clear();
661  outersAndHoles.m_Outers.clear();
662 
663  for( int idx = 0; idx < solution.OutlineCount(); idx++ )
664  {
665  const SHAPE_LINE_CHAIN & outline = solution.Outline( idx );
666 
667  SEGMENTS solutionSegment;
668 
669  polygon_Convert( outline, solutionSegment, aBiuTo3DunitsScale );
670  outersAndHoles.m_Outers.push_back( solutionSegment );
671 
672  stats_sum_size_of_polygons += solutionSegment.size();
673 
674  for( int holeIdx = 0;
675  holeIdx < solution.HoleCount( idx );
676  holeIdx++ )
677  {
678  const SHAPE_LINE_CHAIN & hole = solution.Hole( idx, holeIdx );
679 
680  polygon_Convert( hole, solutionSegment, aBiuTo3DunitsScale );
681  outersAndHoles.m_Holes.push_back( solutionSegment );
682  stats_sum_size_of_polygons += solutionSegment.size();
683  }
684 
685  }
686 
687  if( !outersAndHoles.m_Outers.empty() )
688  {
689  aDstContainer.Add( new CPOLYGONBLOCK2D( extractedSegments,
690  outersAndHoles,
691  aBoardItem ) );
692  stats_n_poly_blocks++;
693  }
694  }
695 
696  blockX += blockAdvance.x;
697  leftToRight += leftToRight_inc;
698  }
699 
700  blockY -= blockAdvance.y;
701  topToBottom += topToBottom_inc;
702  }
703 }
void Union(const SFVEC2F &aPoint)
Function Union recalculate the bounding box adding a point.
Definition: cbbox2d.cpp:94
int OutlineCount() const
Returns the number of outlines in the set
coord_type GetTop() const
Definition: box2.h:204
const SFVEC2F & Min() const
Function Min return the minimun vertex pointer.
Definition: cbbox2d.h:176
CBBOX manages a bounding box defined by two SFVEC2F min max points.
Definition: cbbox2d.h:40
coord_type GetRight() const
Definition: box2.h:199
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Returns the reference to aHole-th hole in the aIndex-th outline
SFVEC2F m_Start
Definition: cpolygon2d.h:41
coord_type GetBottom() const
Definition: box2.h:200
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
std::vector< POLYSEGMENT > SEGMENTS
Definition: cpolygon2d.h:62
void Reset()
Function Reset reset the bounding box to zero and de-initialized it.
Definition: cbbox2d.cpp:87
glm::uvec2 SFVEC2UI
Definition: xv3d_types.h:41
static void extractPathsFrom(const SEGMENTS_WIDTH_NORMALS &aSegList, const CBBOX2D &aBBox, SEGMENTS_WIDTH_NORMALS &aOutSegThatIntersect)
Definition: cpolygon2d.cpp:323
void SetClosed(bool aClosed)
Function SetClosed()
glm::vec2 SFVEC2F
Definition: xv3d_types.h:45
SHAPE_POLY_SET.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
std::vector< SEGMENTS > m_Outers
Definition: cpolygon2d.h:76
This structured will be used to handle a sub set of a polygon.
Definition: cpolygon2d.h:74
const SFVEC2F & Max() const
Function Max return the maximum vertex pointer.
Definition: cbbox2d.h:183
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset intersection For aFastMode meaning, see function booleanOp
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
#define MAX_NR_DIVISIONS
Definition: cpolygon2d.cpp:287
static void polygon_Convert(const SHAPE_LINE_CHAIN &aPath, SEGMENTS &aOutSegment, float aBiuTo3DunitsScale)
Definition: cpolygon2d.cpp:374
std::vector< SEGMENTS > m_Holes
Definition: cpolygon2d.h:77
void ScaleNextUp()
Function ScaleNextUp scales a bounding box to the next float representation making it larger.
Definition: cbbox2d.cpp:163
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
void Add(COBJECT2D *aObject)
Definition: ccontainer2d.h:52
SFVEC2F GetExtent() const
Function GetExtent.
Definition: cbbox2d.cpp:126
static bool polygon_IsPointInside(const SEGMENTS &aSegments, const SFVEC2F &aPoint)
Definition: cpolygon2d.cpp:40
SHAPE_LINE_CHAIN.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
coord_type GetLeft() const
Definition: box2.h:203
This dummy block will be defined by a 2d box size.
Definition: cpolygon2d.h:117
std::vector< SEGMENT_WITH_NORMALS > SEGMENTS_WIDTH_NORMALS
This list will be used to test ray2d intersections.
Definition: cpolygon2d.h:67
This class represents a sub polygon block.
Definition: cpolygon2d.h:86

References CGENERICCONTAINER2D::Add(), SHAPE_POLY_SET::AddOutline(), SHAPE_POLY_SET::BooleanIntersection(), SHAPE_POLY_SET::COutline(), extractPathsFrom(), BOX2< Vec >::GetBottom(), CBBOX2D::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, CBBOX2D::Max(), MAX_NR_DIVISIONS, CBBOX2D::Min(), SHAPE_POLY_SET::Outline(), SHAPE_POLY_SET::OutlineCount(), SHAPE_POLY_SET::PM_STRICTLY_SIMPLE, polygon_Convert(), polygon_IsPointInside(), CBBOX2D::Reset(), CBBOX2D::ScaleNextUp(), SHAPE_LINE_CHAIN::SetClosed(), CBBOX2D::Union(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by C3D_RENDER_RAYTRACING::Reload().

◆ Polygon2d_TestModule()

void Polygon2d_TestModule ( )