KiCad PCB EDA Suite
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 *
4 * Copyright (C) 2016 Jean-Pierre Charras, jp.charras at wanadoo.fr
5 * Copyright (C) 1992-2021 KiCad Developers, see AUTHORS.txt for contributors.
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:
19 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
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
59#include <geometry/shape_line_chain.h> // for SHAPE_LINE_CHAIN
61#include <math/vector2d.h> // for VECTOR2I
62#include <trigo.h>
63#include <algorithm>
64
65
66typedef long long coord2_t; // must be big enough to hold 2*max(|coordinate|)^2
67
68// this function is used to sort points.
69// Andrew's monotone chain 2D convex hull algorithm needs a sorted set of points
70static bool compare_point( const VECTOR2I& ref, const VECTOR2I& p )
71{
72 return ref.x < p.x || (ref.x == p.x && ref.y < p.y);
73}
74
75
76// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
77// Returns a positive value, if OAB makes a counter-clockwise turn,
78// negative for clockwise turn, and zero if the points are collinear.
79static coord2_t cross_product( const VECTOR2I& O, const VECTOR2I& A, const VECTOR2I& B )
80{
81 return (coord2_t) (A.x - O.x) * (coord2_t) (B.y - O.y)
82 - (coord2_t) (A.y - O.y) * (coord2_t) (B.x - O.x);
83}
84
85
86// Fills aResult with a list of points on the convex hull in counter-clockwise order.
87void BuildConvexHull( std::vector<VECTOR2I>& aResult, const std::vector<VECTOR2I>& aPoly )
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}
132
133
134void BuildConvexHull( std::vector<VECTOR2I>& aResult, const SHAPE_POLY_SET& aPolygons )
135{
136 BuildConvexHull( aResult, aPolygons, VECTOR2I( 0, 0 ), ANGLE_0 );
137}
138
139
140void BuildConvexHull( std::vector<VECTOR2I>& aResult, const SHAPE_POLY_SET& aPolygons,
141 const VECTOR2I& aPosition, const EDA_ANGLE& aRotation )
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.
Represent a set of closed polygons.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
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
long long coord2_t
Definition: convex_hull.cpp:66
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
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Definition: trigo.cpp:183
VECTOR2< int > VECTOR2I
Definition: vector2d.h:618