KiCad PCB EDA Suite
shape_poly_set.cpp File Reference
#include <algorithm>
#include <assert.h>
#include <cmath>
#include <cstdio>
#include <istream>
#include <limits>
#include <map>
#include <memory>
#include <set>
#include <string>
#include <type_traits>
#include <unordered_set>
#include <vector>
#include <clipper.hpp>
#include <geometry/geometry_utils.h>
#include <geometry/polygon_triangulation.h>
#include <geometry/seg.h>
#include <geometry/shape.h>
#include <geometry/shape_line_chain.h>
#include <geometry/shape_poly_set.h>
#include <math/box2.h>
#include <math/util.h>
#include <math/vector2d.h>
#include <md5_hash.h>
#include <geometry/shape_segment.h>
#include <geometry/shape_circle.h>
#include <wx/log.h>

Go to the source code of this file.

Classes

struct  FractureEdge
 

Macros

#define SEG_CNT_MAX   64
 

Typedefs

typedef std::vector< FractureEdge * > FractureEdgeSet
 

Functions

static int processEdge (FractureEdgeSet &edges, FractureEdge *edge)
 
static void partitionPolyIntoRegularCellGrid (const SHAPE_POLY_SET &aPoly, int aSize, SHAPE_POLY_SET &aOut)
 

Macro Definition Documentation

◆ SEG_CNT_MAX

#define SEG_CNT_MAX   64

Typedef Documentation

◆ FractureEdgeSet

typedef std::vector<FractureEdge*> FractureEdgeSet

Definition at line 869 of file shape_poly_set.cpp.

Function Documentation

◆ partitionPolyIntoRegularCellGrid()

static void partitionPolyIntoRegularCellGrid ( const SHAPE_POLY_SET aPoly,
int  aSize,
SHAPE_POLY_SET aOut 
)
static

Definition at line 2248 of file shape_poly_set.cpp.

2250 {
2251  BOX2I bb = aPoly.BBox();
2252 
2253  double w = bb.GetWidth();
2254  double h = bb.GetHeight();
2255 
2256  if( w == 0.0 || h == 0.0 )
2257  return;
2258 
2259  int n_cells_x, n_cells_y;
2260 
2261  if( w > h )
2262  {
2263  n_cells_x = w / aSize;
2264  n_cells_y = floor( h / w * n_cells_x ) + 1;
2265  }
2266  else
2267  {
2268  n_cells_y = h / aSize;
2269  n_cells_x = floor( w / h * n_cells_y ) + 1;
2270  }
2271 
2272  SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
2273 
2274  for( int yy = 0; yy < n_cells_y; yy++ )
2275  {
2276  for( int xx = 0; xx < n_cells_x; xx++ )
2277  {
2278  VECTOR2I p;
2279 
2280  p.x = bb.GetX() + w * xx / n_cells_x;
2281  p.y = bb.GetY() + h * yy / n_cells_y;
2282 
2283  VECTOR2I p2;
2284 
2285  p2.x = bb.GetX() + w * ( xx + 1 ) / n_cells_x;
2286  p2.y = bb.GetY() + h * ( yy + 1 ) / n_cells_y;
2287 
2288 
2289  SHAPE_LINE_CHAIN mask;
2290  mask.Append( VECTOR2I( p.x, p.y ) );
2291  mask.Append( VECTOR2I( p2.x, p.y ) );
2292  mask.Append( VECTOR2I( p2.x, p2.y ) );
2293  mask.Append( VECTOR2I( p.x, p2.y ) );
2294  mask.SetClosed( true );
2295 
2296  if( ( xx ^ yy ) & 1 )
2297  maskSetOdd.AddOutline( mask );
2298  else
2299  maskSetEven.AddOutline( mask );
2300  }
2301  }
2302 
2303  ps1.BooleanIntersection( maskSetOdd, SHAPE_POLY_SET::PM_FAST );
2304  ps2.BooleanIntersection( maskSetEven, SHAPE_POLY_SET::PM_FAST );
2305  ps1.Fracture( SHAPE_POLY_SET::PM_FAST );
2306  ps2.Fracture( SHAPE_POLY_SET::PM_FAST );
2307 
2308  aOut = ps1;
2309 
2310  for( int i = 0; i < ps2.OutlineCount(); i++ )
2311  aOut.AddOutline( ps2.COutline( i ) );
2312 
2313  if( !aOut.OutlineCount() )
2314  aOut = aPoly;
2315 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
coord_type GetX() const
Definition: box2.h:173
Define a general 2D-vector/point.
Definition: vector2d.h:61
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
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
Represent a set of closed polygons.
coord_type GetWidth() const
Definition: box2.h:180
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
coord_type GetY() const
Definition: box2.h:174
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
coord_type GetHeight() const
Definition: box2.h:181
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.

References SHAPE_POLY_SET::AddOutline(), SHAPE_LINE_CHAIN::Append(), SHAPE_POLY_SET::BBox(), BOX2< Vec >::GetHeight(), BOX2< Vec >::GetWidth(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), SHAPE_POLY_SET::OutlineCount(), SHAPE_POLY_SET::PM_FAST, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by SHAPE_POLY_SET::CacheTriangulation().

◆ processEdge()

static int processEdge ( FractureEdgeSet edges,
FractureEdge edge 
)
static

Definition at line 872 of file shape_poly_set.cpp.

873 {
874  int x = edge->m_p1.x;
875  int y = edge->m_p1.y;
876  int min_dist = std::numeric_limits<int>::max();
877  int x_nearest = 0;
878 
879  FractureEdge* e_nearest = nullptr;
880 
881  for( FractureEdge* e : edges )
882  {
883  if( !e->matches( y ) )
884  continue;
885 
886  int x_intersect;
887 
888  if( e->m_p1.y == e->m_p2.y ) // horizontal edge
889  {
890  x_intersect = std::max( e->m_p1.x, e->m_p2.x );
891  }
892  else
893  {
894  x_intersect = e->m_p1.x + rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y,
895  e->m_p2.y - e->m_p1.y );
896  }
897 
898  int dist = ( x - x_intersect );
899 
900  if( dist >= 0 && dist < min_dist && e->m_connected )
901  {
902  min_dist = dist;
903  x_nearest = x_intersect;
904  e_nearest = e;
905  }
906  }
907 
908  if( e_nearest && e_nearest->m_connected )
909  {
910  int count = 0;
911 
912  FractureEdge* lead1 = new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
913  FractureEdge* lead2 = new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
914  FractureEdge* split_2 = new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
915 
916  edges.push_back( split_2 );
917  edges.push_back( lead1 );
918  edges.push_back( lead2 );
919 
920  FractureEdge* link = e_nearest->m_next;
921 
922  e_nearest->m_p2 = VECTOR2I( x_nearest, y );
923  e_nearest->m_next = lead1;
924  lead1->m_next = edge;
925 
926  FractureEdge* last;
927 
928  for( last = edge; last->m_next != edge; last = last->m_next )
929  {
930  last->m_connected = true;
931  count++;
932  }
933 
934  last->m_connected = true;
935  last->m_next = lead2;
936  lead2->m_next = split_2;
937  split_2->m_next = link;
938 
939  return count + 1;
940  }
941 
942  return 0;
943 }
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
FractureEdge * m_next
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:98

References FractureEdge::m_connected, FractureEdge::m_next, FractureEdge::m_p1, FractureEdge::m_p2, rescale(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by SHAPE_POLY_SET::fractureSingle().