summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/2geom/include/2geom/convex-hull.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/2geom/include/2geom/convex-hull.h')
-rw-r--r--src/3rdparty/2geom/include/2geom/convex-hull.h346
1 files changed, 346 insertions, 0 deletions
diff --git a/src/3rdparty/2geom/include/2geom/convex-hull.h b/src/3rdparty/2geom/include/2geom/convex-hull.h
new file mode 100644
index 0000000..4dff9c2
--- /dev/null
+++ b/src/3rdparty/2geom/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 :
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-03 17:06:14 +0000