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

Function Documentation

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 87 of file convex_hull.cpp.

References compare_point(), and cross_product().

Referenced by BuildConvexHull(), and ZONE_FILLER::buildZoneFeatureHoleList().

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
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 134 of file convex_hull.cpp.

References BuildConvexHull().

136 {
137  BuildConvexHull( aResult, aPolygons, wxPoint( 0, 0 ), 0.0 );
138 }
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
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 141 of file convex_hull.cpp.

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.

144 {
145  // Build the convex hull of the SHAPE_POLY_SET
146  std::vector<wxPoint> buf;
147 
148  for( int cnt = 0; cnt < aPolygons.OutlineCount(); cnt++ )
149  {
150  const SHAPE_LINE_CHAIN& poly = aPolygons.COutline( cnt );
151 
152  for( int ii = 0; ii < poly.PointCount(); ++ii )
153  {
154  buf.push_back( wxPoint( poly.CPoint( ii ).x, poly.CPoint( ii ).y ) );
155  }
156  }
157 
158  BuildConvexHull(aResult, buf );
159 
160  // Move and rotate the points according to aPosition and aRotation
161 
162  for( unsigned ii = 0; ii < aResult.size(); ii++ )
163  {
164  RotatePoint( &aResult[ii], aRotation );
165  aResult[ii] += aPosition;
166  }
167 }
int PointCount() const
Function PointCount()
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:317
int OutlineCount() const
Returns the number of outlines in the set
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
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
Class SHAPE_LINE_CHAIN.
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()