src/2geom/convex-cover.h

   1 #ifndef GEOM_CONVEX_COVER_H
   2 #define GEOM_CONVEX_COVER_H
   3
   4 /*
   5  * convex-cover.h
   6  *
   7  * Copyright 2006 Nathan Hurst <njh@mail.csse.monash.edu.au>
   8  * Copyright 2006 Michael G. Sloan <mgsloan@gmail.com>
   9  *
  10  * This library is free software; you can redistribute it and/or
  11  * modify it either under the terms of the GNU Lesser General Public
  12  * License version 2.1 as published by the Free Software Foundation
  13  * (the "LGPL") or, at your option, under the terms of the Mozilla
  14  * Public License Version 1.1 (the "MPL"). If you do not alter this
  15  * notice, a recipient may use your version of this file under either
  16  * the MPL or the LGPL.
  17  *
  18  * You should have received a copy of the LGPL along with this library
  19  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  21  * You should have received a copy of the MPL along with this library
  22  * in the file COPYING-MPL-1.1
  23  *
  24  * The contents of this file are subject to the Mozilla Public License
  25  * Version 1.1 (the "License"); you may not use this file except in
  26  * compliance with the License. You may obtain a copy of the License at
  27  * http://www.mozilla.org/MPL/
  28  *
  29  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  30  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  31  * the specific language governing rights and limitations.
  32  *
  33  */
  34
  35 /** A convex cover is a sequence of convex polygons that completely cover the path.  For now a
  36  * convex hull class is included here (the convex-hull header is wrong)
  37  */
  38
  39 #include <2geom/point.h>
  40 #include <vector>
  41
  42 namespace Geom{
  43
  44 /** ConvexHull
  45  * A convexhull is a convex region - every point between two points in the convex hull is also in
  46  * the convex hull.  It is defined by a set of points travelling in a clockwise direction.  We require the first point to be top most, and of the topmost, leftmost.
  47
  48  * An empty hull has no points, we allow a single point or two points degenerate cases.
  49
  50  * We could provide the centroid as a member for efficient direction determination.  We can update the
  51  * centroid with all operations with the same time complexity as the operation.
  52  */
  53
  54 class ConvexHull{
  55 public: // XXX: should be private :)
  56     // extracts the convex hull of boundary. internal use only
  57     void find_pivot();
  58     void angle_sort();
  59     void graham_scan();
  60     void graham();
  61 public:
  62     std::vector<Point> boundary;
  63     //Point centroid;
  64
  65     void merge(Point p);
  66     bool contains_point(Point p);
  67
  68     inline Point operator[](int i) const {
  69
  70         int l = boundary.size();
  71         if(l == 0) return Point();
  72         return boundary[i >= 0 ? i % l : (i % l) + l];
  73     }
  74
  75     /*inline Point &operator[](unsigned i) {
  76         int l = boundary.size();
  77         if(l == 0) return Point();
  78         return boundary[i >= 0 ? i % l : i % l + l];
  79     }*/
  80
  81 public:
  82     ConvexHull() {}
  83     ConvexHull(std::vector<Point> const & points) {
  84         boundary = points;
  85         graham();
  86     }
  87
  88     template <typename T>
  89     ConvexHull(T b, T e) :boundary(b,e) {}
  90
  91     ~ConvexHull()
  92     {
  93     }
  94
  95 public:
  96     /** Is the convex hull clockwise?  We use the definition of clockwise from point.h
  97     **/
  98     bool is_clockwise() const;
  99     bool no_colinear_points() const;
 100     bool top_point_first() const;
 101     bool meets_invariants() const;
 102
 103     // contains no points
 104     bool empty() const { return boundary.empty();}
 105
 106     // contains exactly one point
 107     bool singular() const { return boundary.size() == 1;}
 108
 109     //  all points are on a line
 110     bool linear() const { return boundary.size() == 2;}
 111     bool is_degenerate() const;
 112
 113     // area of the convex hull
 114     double centroid_and_area(Geom::Point& centroid) const;
 115     double area() const {
 116         Point tmp;
 117         return centroid_and_area(tmp);
 118     }
 119
 120     // furthest point in a direction (lg time)
 121     Point const * furthest(Point direction) const;
 122
 123     bool is_left(Point p, int n);
 124     int find_left(Point p);
 125     double narrowest_diameter(Point &a, Point &b, Point &c);
 126
 127 };
 128
 129 // do two convex hulls intersect?
 130 bool intersectp(ConvexHull a, ConvexHull b);
 131
 132 std::vector<Point> bridge_points(ConvexHull a, ConvexHull b);
 133
 134 // find the convex hull intersection
 135 ConvexHull intersection(ConvexHull a, ConvexHull b);
 136 ConvexHull sweepline_intersection(ConvexHull const &a, ConvexHull const &b);
 137
 138 // find the convex hull of a set of convex hulls
 139 ConvexHull merge(ConvexHull a, ConvexHull b);
 140
 141 // naive approach
 142 ConvexHull graham_merge(ConvexHull a, ConvexHull b);
 143
 144 unsigned find_bottom_right(ConvexHull const &a);
 145
 146 /*** Arbitrary transform operator.
 147  * Take a convex hull and apply an arbitrary convexity preserving transform.
 148  *  we should be concerned about singular tranforms here.
 149  */
 150 template <class T> ConvexHull operator*(ConvexHull const &p, T const &m) {
 151     ConvexHull pr;
 152
 153     pr.boundary.reserve(p.boundary.size());
 154
 155     for(unsigned i = 0; i < p.boundary.size(); i++) {
 156         pr.boundary.push_back(p.boundary[i]*m);
 157     }
 158     return pr;
 159 }
 160
 161 ConvexHull clip(ConvexHull const & ch, Point n, double d);
 162
 163 //TODO: reinstate
 164 /*class ConvexCover{
 165 public:
 166     Path const* path;
 167     std::vector<ConvexHull> cc;
 168
 169     ConvexCover(Path const &sp);
 170 };*/
 171
 172 };
 173
 174 #endif //2GEOM_CONVEX_COVER_H
 175
 176 /*
 177   Local Variables:
 178   mode:c++
 179   c-file-style:"stroustrup"
 180   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 181   indent-tabs-mode:nil
 182   fill-column:99
 183   End:
 184 */
 185 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :