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...

## ◆ coord2_t

 typedef long long coord2_t

Definition at line 68 of file convex_hull.cpp.

## ◆ 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. aPoly is 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().

## ◆ 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. aPolygons is 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

## ◆ 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().