convex-cover.cpp revision c3a8ad9235ff81909bd472707550aef5b91daf7b
/*
*
* Copyright 2006 Nathan Hurst <njh@mail.csse.monash.edu.au>
* Copyright 2006 Michael G. Sloan <mgsloan@gmail.com>
*
* 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
*
* 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.
*
*/
#include <algorithm>
#include <map>
/** Todo:
+ modify graham scan to work top to bottom, rather than around angles
+ intersection
+ minimum distance between convex hulls
+ maximum distance between convex hulls
+ hausdorf metric?
+ check all degenerate cases carefully
+ check all algorithms meet all invariants
+ generalise rotating caliper algorithm (iterator/circulator?)
*/
namespace Geom{
/*** SignedTriangleArea
* returns the area of the triangle defined by p0, p1, p2. A clockwise triangle has positive area.
*/
double
}
class angle_cmp{
public:
Point o;
#if 0
bool
// not remove this check or std::sort could crash
if (a == b) return false;
#if 1
if(da[1] == 0)
return true; // infinite tangent
if(db[1] == 0)
return false; // infinite tangent
return true;
#else
//assert((ata > atb) == (aa < ab));
return true;
#endif
return false;
}
#else
{
// not remove this check or std::sort could generate
// a segmentation fault because it needs a strict '<'
// but due to round errors a == b doesn't mean dxy == dyx
if (a == b) return false;
}
#endif
};
void
ConvexHull::find_pivot() {
// Find pivot P;
unsigned pivot = 0;
pivot = i;
}
void
ConvexHull::angle_sort() {
// sort points by angle (resolve ties in favor of point farther from P);
// we leave the first one in place as our pivot
}
void
ConvexHull::graham_scan() {
unsigned stac = 2;
boundary[i]);
if(o == 0) { // colinear - dangerous...
stac--;
} else if(o < 0) { // anticlockwise
} else { // remove concavity
while(o >= 0 && stac > 2) {
stac--;
boundary[i]);
}
}
}
}
void
ConvexHull::graham() {
if(is_degenerate()) // nothing to do
return;
find_pivot();
angle_sort();
graham_scan();
}
//Mathematically incorrect mod, but more useful.
int mod(int i, int l) {
return i >= 0 ?
i % l : (i % l) + l;
}
//OPT: usages can often be replaced by conditions
/*** ConvexHull::left
* Tests if a point is left (outside) of a particular segment, n. */
bool
return SignedTriangleArea((*this)[n], (*this)[n+1], p) >= 0;
}
/*** ConvexHull::strict_left
* Tests if a point is left (outside) of a particular segment, n. */
bool
return SignedTriangleArea((*this)[n], (*this)[n+1], p) > 0;
}
/*** ConvexHull::find_positive
* May return any number n where the segment n -> n + 1 (possibly looped around) in the hull such
* that the point is on the wrong side to be within the hull. Returns -1 if it is within the hull.*/
int
for(int i = 0; i < l; i++) {
if(is_left(p, i)) return i;
}
return -1;
}
/*** ConvexHull::find_positive
* May return any number n where the segment n -> n + 1 (possibly looped around) in the hull such
* that the point is on the wrong side to be within the hull. Returns -1 if it is within the hull.*/
int
for(int i = 0; i < l; i++) {
if(is_strict_left(p, i)) return i;
}
return -1;
}
//OPT: do a spread iteration - quasi-random with no repeats and full coverage.
/*** ConvexHull::contains_point
* In order to test whether a point is inside a convex hull we can travel once around the outside making
* sure that each triangle made from an edge and the point has positive area. */
bool
return find_left(p) == -1;
}
/*** ConvexHull::strict_contains_point
* In order to test whether a point is strictly inside (not on the boundary) a convex hull we can travel once around the outside making
* sure that each triangle made from an edge and the point has positive area. */
bool
return find_strict_left(p) == -1;
}
/*** ConvexHull::add_point
* to add a point we need to find whether the new point extends the boundary, and if so, what it
* obscures. Tarjan? Jarvis?*/
void
if(l < 2) {
return;
}
bool pushed = false;
for(int i = 0; i < l; i++) {
bool cur = is_strict_left(p, i);
if(pre) {
if(cur) {
if(!pushed) {
pushed = true;
}
continue;
}
else if(!pushed) {
pushed = true;
}
}
}
}
//OPT: quickly find an obscured point and find the bounds by extending from there. then push all points not within the bounds in order.
//OPT: use binary searches to find the actual starts/ends, use known rights as boundaries. may require cooperation of find_left algo.
/*** ConvexHull::is_clockwise
* We require that successive pairs of edges always turn right.
* proposed algorithm: walk successive edges and require triangle area is positive.
*/
bool
ConvexHull::is_clockwise() const {
if(is_degenerate())
return true;
it != e;) {
return false;
++it;
}
return true;
}
/*** ConvexHull::top_point_first
* We require that the first point in the convex hull has the least y coord, and that off all such points on the hull, it has the least x coord.
* proposed algorithm: track lexicographic minimum while walking the list.
*/
bool
ConvexHull::top_point_first() const {
}
}
//OPT: since the Y values are orderly there should be something like a binary search to do this.
/*** ConvexHull::no_colinear_points
* We require that no three vertices are colinear.
proposed algorithm: We must be very careful about rounding here.
*/
bool
ConvexHull::no_colinear_points() const {
// XXX: implement me!
}
bool
ConvexHull::meets_invariants() const {
}
/*** ConvexHull::is_degenerate
* We allow three degenerate cases: empty, 1 point and 2 points. In many cases these should be handled explicitly.
*/
bool
ConvexHull::is_degenerate() const {
}
/* Here we really need a rotating calipers implementation. This implementation is slow and incorrect.
This incorrectness is a problem because it throws off the algorithms. Perhaps I will come up with
something better tomorrow. The incorrectness is in the order of the bridges - they must be in the
order of traversal around. Since the a->b and b->a bridges are seperated, they don't need to be merge
order, just the order of the traversal of the host hull. Currently some situations make a n->0 bridge
first.*/
}
}
}
}
}
return ret;
}
unsigned find_bottom_right(ConvexHull const &a) {
unsigned it = 1;
it++;
return it-1;
}
/*** ConvexHull sweepline_intersection(ConvexHull a, ConvexHull b);
* find the intersection between two convex hulls. The intersection is also a convex hull.
* (Proof: take any two points both in a and in b. Any point between them is in a by convexity,
* and in b by convexity, thus in both. Need to prove still finite bounds.)
* This algorithm works by sweeping a line down both convex hulls in parallel, working out the left and right edges of the new hull.
*/
unsigned al = 0;
unsigned bl = 0;
al++;
}
bl++;
}
// al and bl now point to the top of the first pair of edges that overlap in y value
//double sweep_y = std::min(a.boundary[al][Y],
// b.boundary[bl][Y]);
return ret;
}
/*** ConvexHull intersection(ConvexHull a, ConvexHull b);
* find the intersection between two convex hulls. The intersection is also a convex hull.
* (Proof: take any two points both in a and in b. Any point between them is in a by convexity,
* and in b by convexity, thus in both. Need to prove still finite bounds.)
*/
/*
int ai = 0, bi = 0;
int aj = a.boundary.size() - 1;
int bj = b.boundary.size() - 1;
*/
/*while (true) {
if(a[ai]
}*/
return ret;
}
/*** ConvexHull merge(ConvexHull a, ConvexHull b);
* find the smallest convex hull that surrounds a and b.
*/
ab[-1] = 0;
bb[-1] = 0;
int i = -1; // XXX: i is int but refers to vector indices
while(true) {
}
if(ab[i] == 0 && i != -1) break;
i = ab[i];
}
if(bb[i] == 0 && i != -1) break;
i = bb[i];
}
return ret;
}
// we can avoid the find pivot step because of top_point_first
/** if we modified graham scan to work top to bottom as proposed in lect754.pdf we could replace the
angle sort with a simple merge sort type algorithm. furthermore, we could do the graham scan
online, avoiding a bunch of memory copies. That would probably be linear. -- njh*/
result.angle_sort();
return result;
}
//TODO: reinstate
/*ConvexCover::ConvexCover(Path const &sp) : path(&sp) {
cc.reserve(sp.size());
for(Geom::Path::const_iterator it(sp.begin()), end(sp.end()); it != end; ++it) {
cc.push_back(ConvexHull((*it).begin(), (*it).end()));
}
}*/
if (n < 2)
return 0;
if(n < 3) {
return 0;
}
double atmp = 0;
for (unsigned i = n-1, j = 0; j < n; i = j, j++) {
}
if (atmp != 0) {
}
return atmp / 2;
}
// n/2, n-1 construct a new point, say (n/2 + n)/2 throw away the furthest boundary point iterate
// until interval is a single value
if(d < dd) {
p = &boundary[i];
d = dd;
}
}
return p;
}
// returns (a, (b,c)), three points which define the narrowest diameter of the hull as the pair of
// lines going through b,c, and through a, parallel to b,c TODO: This can be made linear time by
// moving point tc incrementally from the previous value (it can only move in one direction). It
// is currently n*O(furthest)
double d = INFINITY;
if(td < d) {
a = ta;
b = tb;
c = tc;
d = td;
}
}
return d;
}
};
/*
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:encoding=utf-8:textwidth=99 :