diff options
Diffstat (limited to 'include/2geom/convex-hull.h')
| -rw-r--r-- | include/2geom/convex-hull.h | 346 |
1 files changed, 346 insertions, 0 deletions
diff --git a/include/2geom/convex-hull.h b/include/2geom/convex-hull.h new file mode 100644 index 0000000..4dff9c2 --- /dev/null +++ b/include/2geom/convex-hull.h @@ -0,0 +1,346 @@ +/** @file + * @brief Convex hull data structures + *//* + * Copyright 2006 Nathan Hurst <njh@mail.csse.monash.edu.au> + * Copyright 2006 Michael G. Sloan <mgsloan@gmail.com> + * + * This library is free software; you can redistribute it and/or + * modify it either under the terms of the GNU Lesser General Public + * License version 2.1 as published by the Free Software Foundation + * (the "LGPL") or, at your option, under the terms of the Mozilla + * Public License Version 1.1 (the "MPL"). If you do not alter this + * notice, a recipient may use your version of this file under either + * the MPL or the LGPL. + * + * You should have received a copy of the LGPL along with this library + * in the file COPYING-LGPL-2.1; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * You should have received a copy of the MPL along with this library + * in the file COPYING-MPL-1.1 + * + * The contents of this file are subject to the Mozilla Public License + * Version 1.1 (the "License"); you may not use this file except in + * compliance with the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY + * OF ANY KIND, either express or implied. See the LGPL or the MPL for + * the specific language governing rights and limitations. + * + */ + +#ifndef LIB2GEOM_SEEN_CONVEX_HULL_H +#define LIB2GEOM_SEEN_CONVEX_HULL_H + +#include <2geom/point.h> +#include <2geom/rect.h> +#include <vector> +#include <algorithm> +#include <boost/operators.hpp> +#include <optional> +#include <boost/range/iterator_range.hpp> + +namespace Geom { + +namespace { + +/** @brief Iterator for the lower convex hull. + * This iterator allows us to avoid duplicating any points in the hull + * boundary and still express most algorithms in a concise way. */ +class ConvexHullLowerIterator + : public boost::random_access_iterator_helper + < ConvexHullLowerIterator + , Point + , std::ptrdiff_t + , Point const * + , Point const & + > +{ +public: + typedef ConvexHullLowerIterator Self; + ConvexHullLowerIterator() + : _data(NULL) + , _size(0) + , _x(0) + {} + ConvexHullLowerIterator(std::vector<Point> const &pts, std::size_t x) + : _data(&pts[0]) + , _size(pts.size()) + , _x(x) + {} + + Self &operator++() { + *this += 1; + return *this; + } + Self &operator--() { + *this -= 1; + return *this; + } + Self &operator+=(std::ptrdiff_t d) { + _x += d; + return *this; + } + Self &operator-=(std::ptrdiff_t d) { + _x -= d; + return *this; + } + std::ptrdiff_t operator-(Self const &other) const { + return _x - other._x; + } + Point const &operator*() const { + if (_x < _size) { + return _data[_x]; + } else { + return *_data; + } + } + bool operator==(Self const &other) const { + return _data == other._data && _x == other._x; + } + bool operator<(Self const &other) const { + return _data == other._data && _x < other._x; + } + +private: + Point const *_data; + std::size_t _size; + std::size_t _x; +}; + +} // end anonymous namespace + +/** + * @brief Convex hull based on the Andrew's monotone chain algorithm. + * @ingroup Shapes + */ +class ConvexHull { +public: + typedef std::vector<Point>::const_iterator iterator; + typedef std::vector<Point>::const_iterator const_iterator; + typedef std::vector<Point>::const_iterator UpperIterator; + typedef ConvexHullLowerIterator LowerIterator; + + /// @name Construct a convex hull. + /// @{ + + /// Create an empty convex hull. + ConvexHull() {} + /// Construct a singular convex hull. + explicit ConvexHull(Point const &a) + : _boundary(1, a) + , _lower(1) + {} + /// Construct a convex hull of two points. + ConvexHull(Point const &a, Point const &b); + /// Construct a convex hull of three points. + ConvexHull(Point const &a, Point const &b, Point const &c); + /// Construct a convex hull of four points. + ConvexHull(Point const &a, Point const &b, Point const &c, Point const &d); + /// Create a convex hull of a vector of points. + ConvexHull(std::vector<Point> const &pts); + + /// Create a convex hull of a range of points. + template <typename Iter> + ConvexHull(Iter first, Iter last) + : _lower(0) + { + _prune(first, last, _boundary); + _construct(); + } + /// @} + + /// @name Inspect basic properties. + /// @{ + + /// Check for emptiness. + bool empty() const { return _boundary.empty(); } + /// Get the number of points in the hull. + size_t size() const { return _boundary.size(); } + /// Check whether the hull contains only one point. + bool isSingular() const { return _boundary.size() == 1; } + /// Check whether the hull is a line. + bool isLinear() const { return _boundary.size() == 2; } + /// Check whether the hull has zero area. + bool isDegenerate() const { return _boundary.size() < 3; } + /// Calculate the area of the convex hull. + double area() const; + //Point centroid() const; + //double areaAndCentroid(Point &c); + //FatLine maxDiameter() const; + //FatLine minDiameter() const; + /// @} + + /// @name Inspect bounds and extreme points. + /// @{ + + /// Compute the bounding rectangle of the convex hull. + OptRect bounds() const; + + /// Get the leftmost (minimum X) coordinate of the hull. + Coord left() const { return _boundary[0][X]; } + /// Get the rightmost (maximum X) coordinate of the hull. + Coord right() const { return _boundary[_lower-1][X]; } + /// Get the topmost (minimum Y) coordinate of the hull. + Coord top() const { return topPoint()[Y]; } + /// Get the bottommost (maximum Y) coordinate of the hull. + Coord bottom() const { return bottomPoint()[Y]; } + + /// Get the leftmost (minimum X) point of the hull. + /// If the leftmost edge is vertical, the top point of the edge is returned. + Point leftPoint() const { return _boundary[0]; } + /// Get the rightmost (maximum X) point of the hull. + /// If the rightmost edge is vertical, the bottom point edge is returned. + Point rightPoint() const { return _boundary[_lower-1]; } + /// Get the topmost (minimum Y) point of the hull. + /// If the topmost edge is horizontal, the right point of the edge is returned. + Point topPoint() const; + /// Get the bottommost (maximum Y) point of the hull. + /// If the bottommost edge is horizontal, the left point of the edge is returned. + Point bottomPoint() const; + ///@} + + /// @name Iterate over points. + /// @{ + /** @brief Get the begin iterator to the points that form the hull. + * Points are returned beginning with the leftmost one, going along + * the upper (minimum Y) side, and then along the bottom. + * Thus the points are always ordered clockwise. No point is + * repeated. */ + iterator begin() const { return _boundary.begin(); } + /// Get the end iterator to the points that form the hull. + iterator end() const { return _boundary.end(); } + /// Get the first, leftmost point in the hull. + Point const &front() const { return _boundary.front(); } + /// Get the penultimate point of the lower hull. + Point const &back() const { return _boundary.back(); } + Point const &operator[](std::size_t i) const { + return _boundary[i]; + } + + /** @brief Get an iterator range to the upper part of the hull. + * This returns a range that includes the leftmost point, + * all points of the upper hull, and the rightmost point. */ + boost::iterator_range<UpperIterator> upperHull() const { + boost::iterator_range<UpperIterator> r(_boundary.begin(), _boundary.begin() + _lower); + return r; + } + + /** @brief Get an iterator range to the lower part of the hull. + * This returns a range that includes the leftmost point, + * all points of the lower hull, and the rightmost point. */ + boost::iterator_range<LowerIterator> lowerHull() const { + if (_boundary.empty()) { + boost::iterator_range<LowerIterator> r(LowerIterator(_boundary, 0), + LowerIterator(_boundary, 0)); + return r; + } + if (_boundary.size() == 1) { + boost::iterator_range<LowerIterator> r(LowerIterator(_boundary, 0), + LowerIterator(_boundary, 1)); + return r; + } + boost::iterator_range<LowerIterator> r(LowerIterator(_boundary, _lower - 1), + LowerIterator(_boundary, _boundary.size() + 1)); + return r; + } + /// @} + + /// @name Check for containment and intersection. + /// @{ + /** @brief Check whether the given point is inside the hull. + * This takes logarithmic time. */ + bool contains(Point const &p) const; + /** @brief Check whether the given axis-aligned rectangle is inside the hull. + * A rectangle is inside the hull if all of its corners are inside. */ + bool contains(Rect const &r) const; + /// Check whether the given convex hull is completely contained in this one. + bool contains(ConvexHull const &other) const; + //bool interiorContains(Point const &p) const; + //bool interiorContains(Rect const &r) const; + //bool interiorContains(ConvexHull const &other) const; + //bool intersects(Rect const &r) const; + //bool intersects(ConvexHull const &other) const; + + //ConvexHull &operator|=(ConvexHull const &other); + //ConvexHull &operator&=(ConvexHull const &other); + //ConvexHull &operator*=(Affine const &m); + + //ConvexHull &expand(Point const &p); + //void unifyWith(ConvexHull const &other); + //void intersectWith(ConvexHull const &other); + /// @} + + void swap(ConvexHull &other); + void swap(std::vector<Point> &pts); + +private: + void _construct(); + static bool _is_clockwise_turn(Point const &a, Point const &b, Point const &c); + + /// Take a vector of points and produce a pruned sorted vector. + template <typename Iter> + static void _prune(Iter first, Iter last, std::vector<Point> &out) { + std::optional<Point> ymin, ymax, xmin, xmax; + for (Iter i = first; i != last; ++i) { + Point p = *i; + if (!ymin || Point::LexLess<Y>()(p, *ymin)) { + ymin = p; + } + if (!xmin || Point::LexLess<X>()(p, *xmin)) { + xmin = p; + } + if (!ymax || Point::LexGreater<Y>()(p, *ymax)) { + ymax = p; + } + if (!xmax || Point::LexGreater<X>()(p, *xmax)) { + xmax = p; + } + } + if (!ymin) return; + + ConvexHull qhull(*xmin, *xmax, *ymin, *ymax); + for (Iter i = first; i != last; ++i) { + if (qhull.contains(*i)) continue; + out.push_back(*i); + } + + out.push_back(*xmin); + out.push_back(*xmax); + out.push_back(*ymin); + out.push_back(*ymax); + std::sort(out.begin(), out.end(), Point::LexLess<X>()); + out.erase(std::unique(out.begin(), out.end()), out.end()); + } + + /// Sequence of points forming the convex hull polygon. + std::vector<Point> _boundary; + /// Index one past the rightmost point, where the lower part of the boundary starts. + std::size_t _lower; +}; + +/** @brief Output operator for convex hulls. + * Prints out all the coordinates. */ +inline std::ostream &operator<< (std::ostream &out_file, const Geom::ConvexHull &in_cvx) { + out_file << "ConvexHull("; + for(auto i : in_cvx) { + out_file << i << ", "; + } + out_file << ")"; + return out_file; +} + +} // end namespace Geom + +#endif // LIB2GEOM_SEEN_CONVEX_HULL_H + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : |