1
#ifndef GEOM_CONVEX_COVER_H
2
#define GEOM_CONVEX_COVER_H
7
* Copyright 2006 Nathan Hurst <njh@mail.csse.monash.edu.au>
8
* Copyright 2006 Michael G. Sloan <mgsloan@gmail.com>
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.
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
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/
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.
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)
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.
48
* An empty hull has no points, we allow a single point or two points degenerate cases.
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.
55
public: // XXX: should be private :)
56
// extracts the convex hull of boundary. internal use only
62
std::vector<Point> boundary;
66
bool contains_point(Point p);
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];
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];
82
ConvexHull(std::vector<Point> const & points) {
88
ConvexHull(T b, T e) :boundary(b,e) {}
91
/** Is the convex hull clockwise? We use the definition of clockwise from point.h
93
bool is_clockwise() const;
94
bool no_colinear_points() const;
95
bool top_point_first() const;
96
bool meets_invariants() const;
99
bool empty() const { return boundary.empty();}
101
// contains exactly one point
102
bool singular() const { return boundary.size() == 1;}
104
// all points are on a line
105
bool linear() const { return boundary.size() == 2;}
106
bool is_degenerate() const;
108
// area of the convex hull
111
// furthest point in a direction (lg time)
112
Point const * furthest(Point direction) const;
114
bool is_left(Point p, int n);
115
int find_left(Point p);
118
// do two convex hulls intersect?
119
bool intersectp(ConvexHull a, ConvexHull b);
121
std::vector<Point> bridge_points(ConvexHull a, ConvexHull b);
123
// find the convex hull intersection
124
ConvexHull intersection(ConvexHull a, ConvexHull b);
125
ConvexHull sweepline_intersection(ConvexHull const &a, ConvexHull const &b);
127
// find the convex hull of a set of convex hulls
128
ConvexHull merge(ConvexHull a, ConvexHull b);
131
ConvexHull graham_merge(ConvexHull a, ConvexHull b);
133
unsigned find_bottom_right(ConvexHull const &a);
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.
139
template <class T> ConvexHull operator*(ConvexHull const &p, T const &m) {
142
pr.boundary.reserve(p.boundary.size());
144
for(unsigned i = 0; i < p.boundary.size(); i++) {
145
pr.boundary.push_back(p.boundary[i]*m);
154
std::vector<ConvexHull> cc;
156
ConvexCover(Path const &sp);
161
#endif //2GEOM_CONVEX_COVER_H
166
c-file-style:"stroustrup"
167
c-file-offsets:((innamespace . 0)(substatement-open . 0))
172
vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :