KiCad PCB EDA Suite
convex_hull.cpp File Reference
#include <geometry/convex_hull.h>
#include <geometry/shape_line_chain.h>
#include <geometry/shape_poly_set.h>
#include <math/vector2d.h>
#include <trigo.h>
#include <algorithm>
#include <wx/wx.h>

Go to the source code of this file.

Typedefs

typedef long long coord2_t
 

Functions

static bool compare_point (const wxPoint &ref, const wxPoint &p)
 
static coord2_t cross_product (const wxPoint &O, const wxPoint &A, const wxPoint &B)
 
void BuildConvexHull (std::vector< wxPoint > &aResult, const std::vector< wxPoint > &aPoly)
 Calculate the convex hull of a list of points in counter-clockwise order. More...
 
void BuildConvexHull (std::vector< wxPoint > &aResult, const SHAPE_POLY_SET &aPolygons)
 Calculate the convex hull of a SHAPE_POLY_SET. More...
 
void BuildConvexHull (std::vector< wxPoint > &aResult, const SHAPE_POLY_SET &aPolygons, wxPoint aPosition, double aRotation)
 Calculate the convex hull (rotated and moved) of a SHAPE_POLY_SET. More...
 

Typedef Documentation

◆ coord2_t

typedef long long coord2_t

Definition at line 68 of file convex_hull.cpp.

Function Documentation

◆ BuildConvexHull() [1/3]

void BuildConvexHull ( std::vector< wxPoint > &  aResult,
const std::vector< wxPoint > &  aPoly 
)

Calculate the convex hull of a list of points in counter-clockwise order.

Parameters
aResult= a vector to store the convex polygon.
aPolyis the list of points.

Definition at line 89 of file convex_hull.cpp.

90 {
91  std::vector<wxPoint> poly = aPoly;
92  int point_count = poly.size();
93 
94  if( point_count < 2 ) // Should not happen, but who know
95  return;
96 
97  // Sort points lexicographically
98  // Andrew's monotone chain 2D convex hull algorithm needs that
99  std::sort( poly.begin(), poly.end(), compare_point );
100 
101  int k = 0;
102 
103  // Store room (2 * n points) for result:
104  // The actual convex hull use less points. the room will be adjusted later
105  aResult.resize( 2 * point_count );
106 
107  // Build lower hull
108  for( int ii = 0; ii < point_count; ++ii )
109  {
110  while( k >= 2 && cross_product( aResult[k - 2], aResult[k - 1], poly[ii] ) <= 0 )
111  k--;
112 
113  aResult[k++] = poly[ii];
114  }
115 
116  // Build upper hull
117  for( int ii = point_count - 2, t = k + 1; ii >= 0; ii-- )
118  {
119  while( k >= t && cross_product( aResult[k - 2], aResult[k - 1], poly[ii] ) <= 0 )
120  k--;
121 
122  aResult[k++] = poly[ii];
123  }
124 
125  // The last point in the list is the same as the first one.
126  // This is not needed, and sometimes create issues ( 0 length polygon segment:
127  // remove it:
128 
129  if( k > 1 && aResult[0] == aResult[k - 1] )
130  k -= 1;
131 
132  aResult.resize( k );
133 }
static coord2_t cross_product(const wxPoint &O, const wxPoint &A, const wxPoint &B)
Definition: convex_hull.cpp:81
static bool compare_point(const wxPoint &ref, const wxPoint &p)
Definition: convex_hull.cpp:72

References compare_point(), and cross_product().

Referenced by ZONE_FILLER::addKnockout(), BuildConvexHull(), and DSN::SPECCTRA_DB::makePADSTACK().

◆ BuildConvexHull() [2/3]

void BuildConvexHull ( std::vector< wxPoint > &  aResult,
const SHAPE_POLY_SET aPolygons 
)

Calculate the convex hull of a SHAPE_POLY_SET.

Parameters
aResult= a vector to store the convex polygon.
aPolygons= the SHAPE_POLY_SET

Definition at line 136 of file convex_hull.cpp.

138 {
139  BuildConvexHull( aResult, aPolygons, wxPoint( 0, 0 ), 0.0 );
140 }
void BuildConvexHull(std::vector< wxPoint > &aResult, const std::vector< wxPoint > &aPoly)
Calculate the convex hull of a list of points in counter-clockwise order.
Definition: convex_hull.cpp:89

References BuildConvexHull().

◆ BuildConvexHull() [3/3]

void BuildConvexHull ( std::vector< wxPoint > &  aResult,
const SHAPE_POLY_SET aPolygons,
wxPoint  aPosition,
double  aRotation 
)

Calculate the convex hull (rotated and moved) of a SHAPE_POLY_SET.

Parameters
aResult= a vector to store the convex polygon.
aPolygonsis the set of polygons
aPosition= the final position of the convex hull
aRotation= the rotation of the convex hull

Definition at line 143 of file convex_hull.cpp.

146 {
147  // Build the convex hull of the SHAPE_POLY_SET
148  std::vector<wxPoint> buf;
149 
150  for( int cnt = 0; cnt < aPolygons.OutlineCount(); cnt++ )
151  {
152  const SHAPE_LINE_CHAIN& poly = aPolygons.COutline( cnt );
153 
154  for( int ii = 0; ii < poly.PointCount(); ++ii )
155  {
156  buf.emplace_back( poly.CPoint( ii ).x, poly.CPoint( ii ).y );
157  }
158  }
159 
160  BuildConvexHull(aResult, buf );
161 
162  // Move and rotate the points according to aPosition and aRotation
163 
164  for( unsigned ii = 0; ii < aResult.size(); ii++ )
165  {
166  RotatePoint( &aResult[ii], aRotation );
167  aResult[ii] += aPosition;
168  }
169 }
int OutlineCount() const
Returns the number of outlines in the set
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:208
void BuildConvexHull(std::vector< wxPoint > &aResult, const std::vector< wxPoint > &aPoly)
Calculate the convex hull of a list of points in counter-clockwise order.
Definition: convex_hull.cpp:89
int PointCount() const
Function PointCount()
const VECTOR2I & CPoint(int aIndex) const
Function Point()
SHAPE_LINE_CHAIN.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const

References BuildConvexHull(), SHAPE_POLY_SET::COutline(), SHAPE_LINE_CHAIN::CPoint(), SHAPE_POLY_SET::OutlineCount(), SHAPE_LINE_CHAIN::PointCount(), RotatePoint(), VECTOR2< T >::x, and VECTOR2< T >::y.

◆ compare_point()

static bool compare_point ( const wxPoint ref,
const wxPoint p 
)
static

Definition at line 72 of file convex_hull.cpp.

73 {
74  return ref.x < p.x || (ref.x == p.x && ref.y < p.y);
75 }

References wxPoint::x, and wxPoint::y.

Referenced by BuildConvexHull().

◆ cross_product()

static coord2_t cross_product ( const wxPoint O,
const wxPoint A,
const wxPoint B 
)
static

Definition at line 81 of file convex_hull.cpp.

82 {
83  return (coord2_t) (A.x - O.x) * (coord2_t) (B.y - O.y)
84  - (coord2_t) (A.y - O.y) * (coord2_t) (B.x - O.x);
85 }
long long coord2_t
Definition: convex_hull.cpp:68

References wxPoint::x, and wxPoint::y.

Referenced by BuildConvexHull().