KiCad PCB EDA Suite
cpolygon2d.h File Reference
#include "cobject2d.h"
#include "../accelerators/ccontainer2d.h"
#include <geometry/shape_poly_set.h>
#include <polygons_defs.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)
 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 Polygon_Calc_BBox_3DU (const SHAPE_POLY_SET &aPolysList, CBBOX2D &aOutBBox, float aBiuTo3DunitsScale)
 
void Polygon_Convert (const KI_POLYGON &aPolygon, ClipperLib::Path &aOutPath, CBBOX2D &aOutBBox, float aBiuTo3DunitsScale)
 
void Polygon2d_TestModule ()
 

Typedef Documentation

typedef std::vector< POLYSEGMENT > SEGMENTS

Definition at line 63 of file cpolygon2d.h.

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 68 of file cpolygon2d.h.

Function Documentation

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 
)

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 406 of file cpolygon2d.cpp.

References CGENERICCONTAINER2D::Add(), SHAPE_POLY_SET::AddOutline(), SHAPE_POLY_SET::BBox(), SHAPE_POLY_SET::BooleanIntersection(), SHAPE_POLY_SET::CPolygon(), 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, 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().

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

Definition at line 714 of file cpolygon2d.cpp.

References SHAPE_LINE_CHAIN::CPoint(), SHAPE_POLY_SET::CPolygon(), SHAPE_POLY_SET::OutlineCount(), SHAPE_LINE_CHAIN::PointCount(), CBBOX2D::Reset(), CBBOX2D::ScaleNextUp(), CBBOX2D::Union(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by CINFO3D_VISU::createBoardPolygon().

717 {
718  aOutBBox.Reset();
719 
720  for( int idx = 0; idx < aPolysList.OutlineCount(); ++idx )
721  {
722  // Each polygon in aPolysList is a polygon with holes
723  const SHAPE_POLY_SET::POLYGON& curr_polywithholes = aPolysList.CPolygon( idx );
724 
725  for( unsigned ipoly = 0; ipoly < curr_polywithholes.size(); ++ipoly )
726  {
727  const SHAPE_LINE_CHAIN& path = curr_polywithholes[ipoly]; // a simple polygon
728 
729  for( int jj = 0; jj < path.PointCount(); jj++ )
730  {
731  const VECTOR2I& a = path.CPoint( jj );
732 
733  aOutBBox.Union( SFVEC2F( (float) a.x * aBiuTo3DunitsScale,
734  (float)-a.y * aBiuTo3DunitsScale ) );
735  }
736  }
737  }
738 
739  aOutBBox.ScaleNextUp();
740 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void Union(const SFVEC2F &aPoint)
Function Union recalculate the bounding box adding a point.
Definition: cbbox2d.cpp:95
int PointCount() const
Function PointCount()
int OutlineCount() const
Returns the number of outlines in the set
void Reset()
Function Reset reset the bounding box to zero and de-initialized it.
Definition: cbbox2d.cpp:88
glm::vec2 SFVEC2F
Definition: xv3d_types.h:45
void ScaleNextUp()
Function ScaleNextUp scales a bounding box to the next float representation making it larger...
Definition: cbbox2d.cpp:164
Class SHAPE_LINE_CHAIN.
const POLYGON & CPolygon(int aIndex) const
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
void Polygon_Convert ( const KI_POLYGON aPolygon,
ClipperLib::Path &  aOutPath,
CBBOX2D aOutBBox,
float  aBiuTo3DunitsScale 
)

Definition at line 743 of file cpolygon2d.cpp.

References CBBOX2D::Reset(), CBBOX2D::ScaleNextUp(), and CBBOX2D::Union().

747 {
748  aOutPath.resize( aPolygon.size() );
749  aOutBBox.Reset();
750 
751  for( unsigned i = 0; i < aPolygon.size(); i++ )
752  {
753  const KI_POLY_POINT point = *(aPolygon.begin() + i);
754 
755  aOutPath[i] = ClipperLib::IntPoint( (ClipperLib::cInt)point.x(),
756  (ClipperLib::cInt)point.y() );
757 
758  aOutBBox.Union( SFVEC2F( (float) point.x() * aBiuTo3DunitsScale,
759  (float)-point.y() * aBiuTo3DunitsScale ) );
760  }
761 
762  aOutBBox.ScaleNextUp();
763 
764  ClipperLib::CleanPolygon( aOutPath );
765 }
void Union(const SFVEC2F &aPoint)
Function Union recalculate the bounding box adding a point.
Definition: cbbox2d.cpp:95
void Reset()
Function Reset reset the bounding box to zero and de-initialized it.
Definition: cbbox2d.cpp:88
glm::vec2 SFVEC2F
Definition: xv3d_types.h:45
void ScaleNextUp()
Function ScaleNextUp scales a bounding box to the next float representation making it larger...
Definition: cbbox2d.cpp:164
bpl::point_data< int > KI_POLY_POINT
KI_POLY_POINT defines a point for boost::polygon.
Definition: polygons_defs.h:66