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         int l = boundary.size();
  70         if(l == 0) return Point();
  71         return boundary[i >= 0 ? i % l : (i % l) + l];
  72     }
  73
  74     /*inline Point &operator[](unsigned i) {
  75         int l = boundary.size();
  76         if(l == 0) return Point();
  77         return boundary[i >= 0 ? i % l : i % l + l];
  78     }*/
  79
  80 public:
  81     ConvexHull() {}
  82     ConvexHull(std::vector<Point> const & points) {
  83         boundary = points;
  84         graham();
  85     }
  86
  87     template <typename T>
  88     ConvexHull(T b, T e) :boundary(b,e) {}
  89
  90 public:
  91     /** Is the convex hull clockwise?  We use the definition of clockwise from point.h
  92     **/
  93     bool is_clockwise() const;
  94     bool no_colinear_points() const;
  95     bool top_point_first() const;
  96     bool meets_invariants() const;
  97
  98     // contains no points
  99     bool empty() const { return boundary.empty();}
 100
 101     // contains exactly one point
 102     bool singular() const { return boundary.size() == 1;}
 103
 104     //  all points are on a line
 105     bool linear() const { return boundary.size() == 2;}
 106     bool is_degenerate() const;
 107
 108     // area of the convex hull
 109     double centroid_and_area(Geom::Point& centroid) const;
 110     double area() const {
 111         Point tmp;
 112         return centroid_and_area(tmp);
 113     }
 114
 115     // furthest point in a direction (lg time)
 116     Point const * furthest(Point direction) const;
 117
 118     bool is_left(Point p, int n);
 119     int find_left(Point p);
 120     double narrowest_diameter(Point &a, Point &b, Point &c);
 121 };
 122
 123 // do two convex hulls intersect?
 124 bool intersectp(ConvexHull a, ConvexHull b);
 125
 126 std::vector<Point> bridge_points(ConvexHull a, ConvexHull b);
 127
 128 // find the convex hull intersection
 129 ConvexHull intersection(ConvexHull a, ConvexHull b);
 130 ConvexHull sweepline_intersection(ConvexHull const &a, ConvexHull const &b);
 131
 132 // find the convex hull of a set of convex hulls
 133 ConvexHull merge(ConvexHull a, ConvexHull b);
 134
 135 // naive approach
 136 ConvexHull graham_merge(ConvexHull a, ConvexHull b);
 137
 138 unsigned find_bottom_right(ConvexHull const &a);
 139
 140 /*** Arbitrary transform operator.
 141  * Take a convex hull and apply an arbitrary convexity preserving transform.
 142  *  we should be concerned about singular tranforms here.
 143  */
 144 template <class T> ConvexHull operator*(ConvexHull const &p, T const &m) {
 145     ConvexHull pr;
 146
 147     pr.boundary.reserve(p.boundary.size());
 148
 149     for(unsigned i = 0; i < p.boundary.size(); i++) {
 150         pr.boundary.push_back(p.boundary[i]*m);
 151     }
 152     return pr;
 153 }
 154
 155 ConvexHull clip(ConvexHull const & ch, Point n, double d);
 156
 157 //TODO: reinstate
 158 /*class ConvexCover{
 159 public:
 160     Path const* path;
 161     std::vector<ConvexHull> cc;
 162
 163     ConvexCover(Path const &sp);
 164 };*/
 165
 166 };
 167
 168 #endif //2GEOM_CONVEX_COVER_H
 169
 170 /*
 171   Local Variables:
 172   mode:c++
 173   c-file-style:"stroustrup"
 174   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 175   indent-tabs-mode:nil
 176   fill-column:99
 177   End:
 178 */
 179 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :