KiCad PCB EDA Suite
convex_hull.h File Reference
#include <vector>
#include <math/vector2d.h>
#include <geometry/eda_angle.h>

Go to the source code of this file.

Functions

void BuildConvexHull (std::vector< VECTOR2I > &aResult, const std::vector< VECTOR2I > &aPoly)
 Calculate the convex hull of a list of points in counter-clockwise order. More...
 
void BuildConvexHull (std::vector< VECTOR2I > &aResult, const SHAPE_POLY_SET &aPolygons)
 Calculate the convex hull of a SHAPE_POLY_SET. More...
 
void BuildConvexHull (std::vector< VECTOR2I > &aResult, const SHAPE_POLY_SET &aPolygons, const VECTOR2I &aPosition, const EDA_ANGLE &aRotation)
 Calculate the convex hull (rotated and moved) of a SHAPE_POLY_SET. More...
 

Function Documentation

◆ BuildConvexHull() [1/3]

void BuildConvexHull ( std::vector< VECTOR2I > &  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, VECTOR2I( 0, 0 ), ANGLE_0 );
137}
void BuildConvexHull(std::vector< VECTOR2I > &aResult, const std::vector< VECTOR2I > &aPoly)
Calculate the convex hull of a list of points in counter-clockwise order.
Definition: convex_hull.cpp:87
static constexpr EDA_ANGLE & ANGLE_0
Definition: eda_angle.h:412
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618

References ANGLE_0, and BuildConvexHull().

◆ BuildConvexHull() [2/3]

void BuildConvexHull ( std::vector< VECTOR2I > &  aResult,
const SHAPE_POLY_SET aPolygons,
const VECTOR2I aPosition,
const EDA_ANGLE 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<VECTOR2I> 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}
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
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.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Definition: trigo.cpp:183

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.

◆ BuildConvexHull() [3/3]

void BuildConvexHull ( std::vector< VECTOR2I > &  aResult,
const std::vector< VECTOR2I > &  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<VECTOR2I> 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 VECTOR2I &O, const VECTOR2I &A, const VECTOR2I &B)
Definition: convex_hull.cpp:79
static bool compare_point(const VECTOR2I &ref, const VECTOR2I &p)
Definition: convex_hull.cpp:70

References compare_point(), and cross_product().

Referenced by ZONE_FILLER::addKnockout(), BuildConvexHull(), TEARDROP_MANAGER::ComputePointsOnPadVia(), FOOTPRINT::GetBoundingHull(), and DSN::SPECCTRA_DB::makePADSTACK().