convex_hull.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24
25
26 /*
27  * Implementation of Andrew's monotone chain 2D convex hull algorithm.
28  * Asymptotic complexity: O(n log n).
29  * See http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull
30  * (Licence GNU Free Documentation License 1.2)
31  *
32  * Pseudo-code:
33  *
34  * Input: a list P of points in the plane.
35  *
36  * Sort the points of P by x-coordinate (in case of a tie, sort by y-coordinate).
37  *
38  * Initialize U and L as empty lists.
39  * The lists will hold the vertices of upper and lower hulls respectively.
40  *
41  * for i = 1, 2, ..., n:
42  * while L contains at least two points and the sequence of last two points
43  * of L and the point P[i] does not make a counter-clockwise turn:
44  * remove the last point from L
45  * append P[i] to L
46  *
47  * for i = n, n-1, ..., 1:
48  * while U contains at least two points and the sequence of last two points
49  * of U and the point P[i] does not make a counter-clockwise turn:
50  * remove the last point from U
51  * append P[i] to U
52  *
53  * Remove the last point of each list (it's the same as the first point of the other list).
54  * Concatenate L and U to obtain the convex hull of P.
55  * Points in the result will be listed in counter-clockwise order.
56  */
57
58 #include <geometry/convex_hull.h>
59 #include <geometry/shape_line_chain.h> // for SHAPE_LINE_CHAIN
61 #include <math/vector2d.h> // for VECTOR2I
62 #include <trigo.h>
63
64 #include <algorithm>
65 #include <wx/wx.h>
66
67
68 typedef long long coord2_t; // must be big enough to hold 2*max(|coordinate|)^2
69
70 // this function is used to sort points.
71 // Andrew's monotone chain 2D convex hull algorithm needs a sorted set of points
72 static bool compare_point( const wxPoint& ref, const wxPoint& p )
73 {
74  return ref.x < p.x || (ref.x == p.x && ref.y < p.y);
75 }
76
77
78 // 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
79 // Returns a positive value, if OAB makes a counter-clockwise turn,
80 // negative for clockwise turn, and zero if the points are collinear.
81 static coord2_t cross_product( const wxPoint& O, const wxPoint& A, const wxPoint& B )
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 }
86
87
88 // Fills aResult with a list of points on the convex hull in counter-clockwise order.
89 void BuildConvexHull( std::vector<wxPoint>& aResult, const std::vector<wxPoint>& aPoly )
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 }
134
135
136 void BuildConvexHull( std::vector<wxPoint>& aResult,
137  const SHAPE_POLY_SET& aPolygons )
138 {
139  BuildConvexHull( aResult, aPolygons, wxPoint( 0, 0 ), 0.0 );
140 }
141
142
143 void BuildConvexHull( std::vector<wxPoint>& aResult,
144  const SHAPE_POLY_SET& aPolygons,
145  wxPoint aPosition, double aRotation )
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
static coord2_t cross_product(const wxPoint &O, const wxPoint &A, const wxPoint &B)
Definition: convex_hull.cpp:81
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:208
static bool compare_point(const wxPoint &ref, const wxPoint &p)
Definition: convex_hull.cpp:72
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_POLY_SET.
SHAPE_LINE_CHAIN.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
long long coord2_t
Definition: convex_hull.cpp:68