KiCad PCB EDA Suite
convex_hull.h File Reference
#include <vector>

Go to the source code of this file.

Functions

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, const wxPoint &aPosition, double aRotation)
 Calculate the convex hull (rotated and moved) of a SHAPE_POLY_SET. More...
 

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
aResultis a vector to store the convex polygon.
aPolyis the list of points.

Definition at line 87 of file convex_hull.cpp.

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

References compare_point(), and cross_product().

Referenced by ZONE_FILLER::addKnockout(), BuildConvexHull(), FOOTPRINT::GetBoundingHull(), 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
aResultis a vector to store the convex polygon.
aPolygonsis the SHAPE_POLY_SET.

Definition at line 134 of file convex_hull.cpp.

135 {
136  BuildConvexHull( aResult, aPolygons, wxPoint( 0, 0 ), 0.0 );
137 }
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:87

References BuildConvexHull().

◆ BuildConvexHull() [3/3]

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

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

Parameters
aResultis a vector to store the convex polygon.
aPolygonsis the set of polygons.
aPositionis the final position of the convex hull.
aRotationis the rotation of the convex hull.

Definition at line 140 of file convex_hull.cpp.

142 {
143  // Build the convex hull of the SHAPE_POLY_SET
144  std::vector<wxPoint> buf;
145 
146  for( int cnt = 0; cnt < aPolygons.OutlineCount(); cnt++ )
147  {
148  const SHAPE_LINE_CHAIN& poly = aPolygons.COutline( cnt );
149 
150  for( int ii = 0; ii < poly.PointCount(); ++ii )
151  buf.emplace_back( poly.CPoint( ii ).x, poly.CPoint( ii ).y );
152  }
153 
154  BuildConvexHull( aResult, buf );
155 
156  // Move and rotate the points according to aPosition and aRotation
157 
158  for( unsigned ii = 0; ii < aResult.size(); ii++ )
159  {
160  RotatePoint( &aResult[ii], aRotation );
161  aResult[ii] += aPosition;
162  }
163 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:229
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:87
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
Represent a polyline (an zero-thickness chain of connected line segments).
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.