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 area() const;
 110
 111     // furthest point in a direction (lg time)
 112     Point const * furthest(Point direction) const;
 113
 114     bool is_left(Point p, int n);
 115     int find_left(Point p);
 116 };
 117
 118 // do two convex hulls intersect?
 119 bool intersectp(ConvexHull a, ConvexHull b);
 120
 121 std::vector<Point> bridge_points(ConvexHull a, ConvexHull b);
 122
 123 // find the convex hull intersection
 124 ConvexHull intersection(ConvexHull a, ConvexHull b);
 125 ConvexHull sweepline_intersection(ConvexHull const &a, ConvexHull const &b);
 126
 127 // find the convex hull of a set of convex hulls
 128 ConvexHull merge(ConvexHull a, ConvexHull b);
 129
 130 // naive approach
 131 ConvexHull graham_merge(ConvexHull a, ConvexHull b);
 132
 133 unsigned find_bottom_right(ConvexHull const &a);
 134
 135 /*** Arbitrary transform operator.
 136  * Take a convex hull and apply an arbitrary convexity preserving transform.
 137  *  we should be concerned about singular tranforms here.
 138  */
 139 template <class T> ConvexHull operator*(ConvexHull const &p, T const &m) {
 140     ConvexHull pr;
 141
 142     pr.boundary.reserve(p.boundary.size());
 143
 144     for(unsigned i = 0; i < p.boundary.size(); i++) {
 145         pr.boundary.push_back(p.boundary[i]*m);
 146     }
 147     return pr;
 148 }
 149
 150 //TODO: reinstate
 151 /*class ConvexCover{
 152 public:
 153     Path const* path;
 154     std::vector<ConvexHull> cc;
 155
 156     ConvexCover(Path const &sp);
 157 };*/
 158
 159 };
 160
 161 #endif //2GEOM_CONVEX_COVER_H
 162
 163 /*
 164   Local Variables:
 165   mode:c++
 166   c-file-style:"stroustrup"
 167   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 168   indent-tabs-mode:nil
 169   fill-column:99
 170   End:
 171 */
 172 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :