| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /** @file | ||
| 2 | * @brief Convex hull data structures | ||
| 3 | *//* | ||
| 4 | * Copyright 2006 Nathan Hurst <njh@mail.csse.monash.edu.au> | ||
| 5 | * Copyright 2006 Michael G. Sloan <mgsloan@gmail.com> | ||
| 6 | * | ||
| 7 | * This library is free software; you can redistribute it and/or | ||
| 8 | * modify it either under the terms of the GNU Lesser General Public | ||
| 9 | * License version 2.1 as published by the Free Software Foundation | ||
| 10 | * (the "LGPL") or, at your option, under the terms of the Mozilla | ||
| 11 | * Public License Version 1.1 (the "MPL"). If you do not alter this | ||
| 12 | * notice, a recipient may use your version of this file under either | ||
| 13 | * the MPL or the LGPL. | ||
| 14 | * | ||
| 15 | * You should have received a copy of the LGPL along with this library | ||
| 16 | * in the file COPYING-LGPL-2.1; if not, write to the Free Software | ||
| 17 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | ||
| 18 | * You should have received a copy of the MPL along with this library | ||
| 19 | * in the file COPYING-MPL-1.1 | ||
| 20 | * | ||
| 21 | * The contents of this file are subject to the Mozilla Public License | ||
| 22 | * Version 1.1 (the "License"); you may not use this file except in | ||
| 23 | * compliance with the License. You may obtain a copy of the License at | ||
| 24 | * http://www.mozilla.org/MPL/ | ||
| 25 | * | ||
| 26 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY | ||
| 27 | * OF ANY KIND, either express or implied. See the LGPL or the MPL for | ||
| 28 | * the specific language governing rights and limitations. | ||
| 29 | * | ||
| 30 | */ | ||
| 31 | |||
| 32 | #ifndef LIB2GEOM_SEEN_CONVEX_HULL_H | ||
| 33 | #define LIB2GEOM_SEEN_CONVEX_HULL_H | ||
| 34 | |||
| 35 | #include <algorithm> | ||
| 36 | #include <optional> | ||
| 37 | #include <vector> | ||
| 38 | #include <boost/operators.hpp> | ||
| 39 | #include <boost/range/iterator_range.hpp> | ||
| 40 | #include <2geom/point.h> | ||
| 41 | #include <2geom/rect.h> | ||
| 42 | #include <2geom/transforms.h> | ||
| 43 | |||
| 44 | namespace Geom { | ||
| 45 | |||
| 46 | namespace { | ||
| 47 | |||
| 48 | /** @brief Iterator for the lower convex hull. | ||
| 49 | * This iterator allows us to avoid duplicating any points in the hull | ||
| 50 | * boundary and still express most algorithms in a concise way. */ | ||
| 51 | class ConvexHullLowerIterator | ||
| 52 | : public boost::random_access_iterator_helper | ||
| 53 | < ConvexHullLowerIterator | ||
| 54 | , Point | ||
| 55 | , std::ptrdiff_t | ||
| 56 | , Point const * | ||
| 57 | , Point const & | ||
| 58 | > | ||
| 59 | { | ||
| 60 | public: | ||
| 61 | using Self = ConvexHullLowerIterator; | ||
| 62 | ConvexHullLowerIterator() = default; | ||
| 63 | 292 | ConvexHullLowerIterator(std::vector<Point> const &pts, std::size_t x) | |
| 64 | 292 | : _data(&pts[0]) | |
| 65 | 292 | , _size(pts.size()) | |
| 66 | 292 | , _x(x) | |
| 67 | 292 | {} | |
| 68 | |||
| 69 | 108 | Self &operator++() { | |
| 70 | 108 | *this += 1; | |
| 71 | 108 | return *this; | |
| 72 | } | ||
| 73 | Self &operator--() { | ||
| 74 | *this -= 1; | ||
| 75 | return *this; | ||
| 76 | } | ||
| 77 | 266 | Self &operator+=(std::ptrdiff_t d) { | |
| 78 | 266 | _x += d; | |
| 79 | 266 | return *this; | |
| 80 | } | ||
| 81 | 62 | Self &operator-=(std::ptrdiff_t d) { | |
| 82 | 62 | _x -= d; | |
| 83 | 62 | return *this; | |
| 84 | } | ||
| 85 | 64 | std::ptrdiff_t operator-(Self const &other) const { | |
| 86 | 64 | return _x - other._x; | |
| 87 | } | ||
| 88 | 335 | Point const &operator*() const { | |
| 89 |
2/2✓ Branch 0 taken 287 times.
✓ Branch 1 taken 48 times.
|
335 | if (_x < _size) { |
| 90 | 287 | return _data[_x]; | |
| 91 | } else { | ||
| 92 | 48 | return *_data; | |
| 93 | } | ||
| 94 | } | ||
| 95 | 185 | bool operator==(Self const &other) const { | |
| 96 |
3/4✓ Branch 0 taken 185 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 177 times.
|
185 | return _data == other._data && _x == other._x; |
| 97 | } | ||
| 98 | bool operator<(Self const &other) const { | ||
| 99 | return _data == other._data && _x < other._x; | ||
| 100 | } | ||
| 101 | |||
| 102 | private: | ||
| 103 | Point const *_data = nullptr; | ||
| 104 | std::size_t _size = 0; | ||
| 105 | std::size_t _x = 0; | ||
| 106 | }; | ||
| 107 | |||
| 108 | } // namespace | ||
| 109 | |||
| 110 | /** | ||
| 111 | * @brief Convex hull based on the Andrew's monotone chain algorithm. | ||
| 112 | * @ingroup Shapes | ||
| 113 | */ | ||
| 114 | class ConvexHull | ||
| 115 | { | ||
| 116 | public: | ||
| 117 | using iterator = std::vector<Point>::const_iterator; | ||
| 118 | using const_iterator = std::vector<Point>::const_iterator; | ||
| 119 | using UpperIterator = std::vector<Point>::const_iterator; | ||
| 120 | using LowerIterator = ConvexHullLowerIterator; | ||
| 121 | |||
| 122 | /// @name Construct a convex hull. | ||
| 123 | /// @{ | ||
| 124 | |||
| 125 | /// Create an empty convex hull. | ||
| 126 | 773 | ConvexHull() = default; | |
| 127 | /// Construct a singular convex hull. | ||
| 128 | explicit ConvexHull(Point const &a) | ||
| 129 | : _boundary(1, a) | ||
| 130 | , _lower(1) | ||
| 131 | {} | ||
| 132 | /// Construct a convex hull of two points. | ||
| 133 | ConvexHull(Point const &a, Point const &b); | ||
| 134 | /// Construct a convex hull of three points. | ||
| 135 | ConvexHull(Point const &a, Point const &b, Point const &c); | ||
| 136 | /// Construct a convex hull of four points. | ||
| 137 | ConvexHull(Point const &a, Point const &b, Point const &c, Point const &d); | ||
| 138 | /// Create a convex hull of a vector of points. | ||
| 139 | ConvexHull(std::vector<Point> const &pts); | ||
| 140 | |||
| 141 | /// Create a convex hull of a range of points. | ||
| 142 | template <typename Iter> | ||
| 143 | ConvexHull(Iter first, Iter last) | ||
| 144 | : _lower(0) | ||
| 145 | { | ||
| 146 | _prune(first, last, _boundary); | ||
| 147 | _construct(); | ||
| 148 | } | ||
| 149 | /// @} | ||
| 150 | |||
| 151 | /// @name Inspect basic properties. | ||
| 152 | /// @{ | ||
| 153 | |||
| 154 | /// Check for emptiness. | ||
| 155 | 102 | bool empty() const { return _boundary.empty(); } | |
| 156 | /// Get the number of points in the hull. | ||
| 157 | 8153 | size_t size() const { return _boundary.size(); } | |
| 158 | /// Check whether the hull contains only one point. | ||
| 159 | bool isSingular() const { return _boundary.size() == 1; } | ||
| 160 | /// Check whether the hull is a line. | ||
| 161 | bool isLinear() const { return _boundary.size() == 2; } | ||
| 162 | /// Check whether the hull has zero area. | ||
| 163 | bool isDegenerate() const { return _boundary.size() < 3; } | ||
| 164 | /// Calculate the area of the convex hull. | ||
| 165 | double area() const; | ||
| 166 | //Point centroid() const; | ||
| 167 | //double areaAndCentroid(Point &c); | ||
| 168 | /// @} | ||
| 169 | |||
| 170 | /// @name Inspect bounds and extreme points. | ||
| 171 | /// @{ | ||
| 172 | |||
| 173 | /// Compute the bounding rectangle of the convex hull. | ||
| 174 | OptRect bounds() const; | ||
| 175 | /// Return a rotation that puts the convex hull into a position | ||
| 176 | /// such that bounds() has minimal area, and return those bounds. | ||
| 177 | std::pair<Rotate, OptRect> minAreaRotation() const; | ||
| 178 | |||
| 179 | /// Get the leftmost (minimum X) coordinate of the hull. | ||
| 180 | ✗ | Coord left() const { return _boundary[0][X]; } | |
| 181 | /// Get the rightmost (maximum X) coordinate of the hull. | ||
| 182 | ✗ | Coord right() const { return _boundary[_lower-1][X]; } | |
| 183 | /// Get the topmost (minimum Y) coordinate of the hull. | ||
| 184 | ✗ | Coord top() const { return topPoint()[Y]; } | |
| 185 | /// Get the bottommost (maximum Y) coordinate of the hull. | ||
| 186 | ✗ | Coord bottom() const { return bottomPoint()[Y]; } | |
| 187 | |||
| 188 | /// Get the leftmost (minimum X) point of the hull. | ||
| 189 | /// If the leftmost edge is vertical, the top point of the edge is returned. | ||
| 190 | Point leftPoint() const { return _boundary[0]; } | ||
| 191 | /// Get the rightmost (maximum X) point of the hull. | ||
| 192 | /// If the rightmost edge is vertical, the bottom point edge is returned. | ||
| 193 | Point rightPoint() const { return _boundary[_lower-1]; } | ||
| 194 | /// Get the topmost (minimum Y) point of the hull. | ||
| 195 | /// If the topmost edge is horizontal, the right point of the edge is returned. | ||
| 196 | Point topPoint() const; | ||
| 197 | /// Get the bottommost (maximum Y) point of the hull. | ||
| 198 | /// If the bottommost edge is horizontal, the left point of the edge is returned. | ||
| 199 | Point bottomPoint() const; | ||
| 200 | ///@} | ||
| 201 | |||
| 202 | /// @name Iterate over points. | ||
| 203 | /// @{ | ||
| 204 | /** @brief Get the begin iterator to the points that form the hull. | ||
| 205 | * Points are returned beginning with the leftmost one, going along | ||
| 206 | * the upper (minimum Y) side, and then along the bottom. | ||
| 207 | * Thus the points are always ordered clockwise. No point is | ||
| 208 | * repeated. */ | ||
| 209 | ✗ | iterator begin() const { return _boundary.begin(); } | |
| 210 | /// Get the end iterator to the points that form the hull. | ||
| 211 | ✗ | iterator end() const { return _boundary.end(); } | |
| 212 | /// Get the first, leftmost point in the hull. | ||
| 213 | 2 | Point const &front() const { return _boundary.front(); } | |
| 214 | /// Get the penultimate point of the lower hull. | ||
| 215 | ✗ | Point const &back() const { return _boundary.back(); } | |
| 216 | 12524 | Point const &operator[](std::size_t i) const { return _boundary[i]; } | |
| 217 | |||
| 218 | /** @brief Get an iterator range to the upper part of the hull. | ||
| 219 | * This returns a range that includes the leftmost point, | ||
| 220 | * all points of the upper hull, and the rightmost point. */ | ||
| 221 | 146 | boost::iterator_range<UpperIterator> upperHull() const { | |
| 222 |
1/2✓ Branch 6 taken 146 times.
✗ Branch 7 not taken.
|
146 | return boost::iterator_range<UpperIterator>(_boundary.begin(), _boundary.begin() + _lower); |
| 223 | } | ||
| 224 | |||
| 225 | /** @brief Get an iterator range to the lower part of the hull. | ||
| 226 | * This returns a range that includes the leftmost point, | ||
| 227 | * all points of the lower hull, and the rightmost point. */ | ||
| 228 | 146 | boost::iterator_range<LowerIterator> lowerHull() const { | |
| 229 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 146 times.
|
146 | if (_boundary.empty()) { |
| 230 | ✗ | boost::iterator_range<LowerIterator> r(LowerIterator(_boundary, 0), | |
| 231 | ✗ | LowerIterator(_boundary, 0)); | |
| 232 | ✗ | return r; | |
| 233 | } | ||
| 234 |
2/2✓ Branch 1 taken 3 times.
✓ Branch 2 taken 143 times.
|
146 | if (_boundary.size() == 1) { |
| 235 | 3 | boost::iterator_range<LowerIterator> r(LowerIterator(_boundary, 0), | |
| 236 |
1/2✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
|
3 | LowerIterator(_boundary, 1)); |
| 237 | 3 | return r; | |
| 238 | } | ||
| 239 | 143 | boost::iterator_range<LowerIterator> r(LowerIterator(_boundary, _lower - 1), | |
| 240 |
1/2✓ Branch 6 taken 143 times.
✗ Branch 7 not taken.
|
143 | LowerIterator(_boundary, _boundary.size() + 1)); |
| 241 | 143 | return r; | |
| 242 | } | ||
| 243 | /// @} | ||
| 244 | |||
| 245 | /// @name Check for containment and intersection. | ||
| 246 | /// @{ | ||
| 247 | /** @brief Check whether the given point is inside the hull. | ||
| 248 | * This takes logarithmic time. */ | ||
| 249 | bool contains(Point const &p) const; | ||
| 250 | /** @brief Check whether the given axis-aligned rectangle is inside the hull. | ||
| 251 | * A rectangle is inside the hull if all of its corners are inside. */ | ||
| 252 | bool contains(Rect const &r) const; | ||
| 253 | /// Check whether the given convex hull is completely contained in this one. | ||
| 254 | bool contains(ConvexHull const &other) const; | ||
| 255 | //bool interiorContains(Point const &p) const; | ||
| 256 | //bool interiorContains(Rect const &r) const; | ||
| 257 | //bool interiorContains(ConvexHull const &other) const; | ||
| 258 | //bool intersects(Rect const &r) const; | ||
| 259 | //bool intersects(ConvexHull const &other) const; | ||
| 260 | |||
| 261 | //ConvexHull &operator|=(ConvexHull const &other); | ||
| 262 | //ConvexHull &operator&=(ConvexHull const &other); | ||
| 263 | //ConvexHull &operator*=(Affine const &m); | ||
| 264 | |||
| 265 | //ConvexHull &expand(Point const &p); | ||
| 266 | //void unifyWith(ConvexHull const &other); | ||
| 267 | //void intersectWith(ConvexHull const &other); | ||
| 268 | /// @} | ||
| 269 | |||
| 270 | void swap(ConvexHull &other); | ||
| 271 | void swap(std::vector<Point> &pts); | ||
| 272 | |||
| 273 | private: | ||
| 274 | void _construct(); | ||
| 275 | |||
| 276 | /// Take a vector of points and produce a pruned sorted vector. | ||
| 277 | template <typename Iter> | ||
| 278 | static void _prune(Iter first, Iter last, std::vector<Point> &out) { | ||
| 279 | std::optional<Point> ymin, ymax, xmin, xmax; | ||
| 280 | for (Iter i = first; i != last; ++i) { | ||
| 281 | Point p = *i; | ||
| 282 | if (!ymin || Point::LexLess<Y>()(p, *ymin)) { | ||
| 283 | ymin = p; | ||
| 284 | } | ||
| 285 | if (!xmin || Point::LexLess<X>()(p, *xmin)) { | ||
| 286 | xmin = p; | ||
| 287 | } | ||
| 288 | if (!ymax || Point::LexGreater<Y>()(p, *ymax)) { | ||
| 289 | ymax = p; | ||
| 290 | } | ||
| 291 | if (!xmax || Point::LexGreater<X>()(p, *xmax)) { | ||
| 292 | xmax = p; | ||
| 293 | } | ||
| 294 | } | ||
| 295 | if (!ymin) return; | ||
| 296 | |||
| 297 | ConvexHull qhull(*xmin, *xmax, *ymin, *ymax); | ||
| 298 | for (Iter i = first; i != last; ++i) { | ||
| 299 | if (qhull.contains(*i)) continue; | ||
| 300 | out.push_back(*i); | ||
| 301 | } | ||
| 302 | |||
| 303 | out.push_back(*xmin); | ||
| 304 | out.push_back(*xmax); | ||
| 305 | out.push_back(*ymin); | ||
| 306 | out.push_back(*ymax); | ||
| 307 | std::sort(out.begin(), out.end(), Point::LexLess<X>()); | ||
| 308 | out.erase(std::unique(out.begin(), out.end()), out.end()); | ||
| 309 | } | ||
| 310 | |||
| 311 | /// Sequence of points forming the convex hull polygon. | ||
| 312 | std::vector<Point> _boundary; | ||
| 313 | /// Index one past the rightmost point, where the lower part of the boundary starts. | ||
| 314 | std::size_t _lower; | ||
| 315 | }; | ||
| 316 | |||
| 317 | /** @brief Output operator for convex hulls. | ||
| 318 | * Prints out all the coordinates. */ | ||
| 319 | inline std::ostream &operator<<(std::ostream &out, Geom::ConvexHull const &hull) { | ||
| 320 | out << "ConvexHull("; | ||
| 321 | for (auto i : hull) { | ||
| 322 | out << i << ", "; | ||
| 323 | } | ||
| 324 | return out << ")"; | ||
| 325 | } | ||
| 326 | |||
| 327 | } // namespace Geom | ||
| 328 | |||
| 329 | #endif // LIB2GEOM_SEEN_CONVEX_HULL_H | ||
| 330 | |||
| 331 | /* | ||
| 332 | Local Variables: | ||
| 333 | mode:c++ | ||
| 334 | c-file-style:"stroustrup" | ||
| 335 | c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) | ||
| 336 | indent-tabs-mode:nil | ||
| 337 | fill-column:99 | ||
| 338 | End: | ||
| 339 | */ | ||
| 340 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : | ||
| 341 |