diff options
Diffstat (limited to 'Polygon.cpp')
| -rw-r--r-- | Polygon.cpp | 205 |
1 files changed, 201 insertions, 4 deletions
diff --git a/Polygon.cpp b/Polygon.cpp index 9340135..3425727 100644 --- a/Polygon.cpp +++ b/Polygon.cpp @@ -1,8 +1,9 @@ #include "Polygon.h" +#include <list> #include <math.h> -double Polygon::area() const { +double Polygon::signedArea() const { double d = 0.0; for(const_iterator it = begin(); it != end(); it++) { @@ -12,7 +13,17 @@ double Polygon::area() const { d += (it2->getX()+it->getX())*(it2->getY()-it->getY()); } - return fabs(d/2); + return d/2; +} + +Polygon::Direction Polygon::getDirection() const { + double area = signedArea(); + + return (area > 0) ? Triangle::CW : (area < 0) ? Triangle::CCW : Triangle::Unknown; +} + +double Polygon::area() const { + return fabs(signedArea()); } double Polygon::perimeter() const { @@ -103,8 +114,8 @@ bool Polygon::contains(const Vertex &v) const { bool Polygon::intersects(const Line &l) const { Line line; - for(Polygon::const_iterator it = begin(); it != end(); it++) { - Polygon::const_iterator it2 = it+1; + for(const_iterator it = begin(); it != end(); it++) { + const_iterator it2 = it+1; if(it2 == end()) it2 = begin(); line.setVertex1(*it); @@ -116,3 +127,189 @@ bool Polygon::intersects(const Line &l) const { return false; } + +bool Polygon::isConcave(const Direction &dir, const Vertex &v1, const Vertex &v2, const Vertex &v3) const { + switch(dir) { + case Triangle::CW: + return (v1.getX()-v2.getX())*(v3.getY()-v2.getY()) > (v3.getX()-v2.getX())*(v1.getY()-v2.getY()); + case Triangle::CCW: + return (v1.getX()-v2.getX())*(v3.getY()-v2.getY()) < (v3.getX()-v2.getX())*(v1.getY()-v2.getY()); + } + + return false; +} + +bool Polygon::intersections(std::vector<Intersection> *intersections) const { + bool ret = false; + size_t s = size(); + + for(size_t i = 0; i+2 < s; i++) { + Line l(at(i), at(i+1)); + + for(size_t j = i+2; j < s; j++) { + if(i == (j+1)%s) continue; + + Line l2(at(j), at((j+1)%s)); + + Vertex v; + if(l.intersects(l2, &v) == INTERSECTION_SEGMENT_SEGMENT) { + if(intersections) { + Intersection in = {i, i+1, j, ((j+1)%s), v}; + + intersections->push_back(in); + ret = true; + } + else { + return true; + } + } + } + } + + return ret; +} + +bool Polygon::isSimple() const { + return !intersections(); +} + +bool Polygon::simplify(Polygon &polygon) const { + std::vector<Intersection> ins; + + if(!intersections(&ins)) return false; + + int s = size(); + int start = 0; + + for(int i = 1; i < s; i++) { + if(at(i).getX() < at(start).getX()) + start = i; + else if(at(i).getX() == at(start).getX() && at(i).getY() < at(start).getY()) + start = i; + } + + int dir = Triangle(at((s+start-1)%s), at(start), at((start+1)%s)).getDirection(); + + int i2 = start; + const Vertex *v2 = &at(i2); + bool intersected; + + do { + intersected = false; + + int i = i2; + + if(dir == Triangle::CW) + i2 = (i2+1)%s; + else + i2 = (s+i2-1)%s; + + const Vertex *v1 = v2; + v2 = &at(i2); + + Vertex *v = NULL; + int v3, v4; + + for(std::vector<Intersection>::iterator in = ins.begin(); in != ins.end(); ++in) { + if(v2->distanceSq(in->v) >= v2->distanceSq(*v1) || v1 == &in->v) + continue; + + if(v) { + if(v1->distanceSq(in->v) >= v1->distanceSq(*v)) + continue; + } + + if((i == in->va1 && i2 == in->va2) || (i == in->va2 && i2 == in->va1)) { + v = &in->v; + v3 = in->vb1; + v4 = in->vb2; + } + else if((i == in->vb1 && i2 == in->vb2) || (i == in->vb2 && i2 == in->vb1)) { + v = &in->v; + v3 = in->va1; + v4 = in->va2; + } + } + + if(v) { + v2 = v; + intersected = true; + + if(isConcave(Triangle::CW, *v1, *v2, at(v4))) { + i2 = v3; + dir = Triangle::CW; + } + else { + i2 = v4; + dir = Triangle::CCW; + } + } + + polygon.push_back(*v2); + } while(i2 != start || intersected); + + return true; +} + +// FIXME: has still some problems... +void Polygon::doTriangulate(std::vector<Triangle> &triangles) const { + size_t s = size(); + + if(s < 3) return; + + std::vector<size_t> p; + std::list<size_t> concave; + Direction dir = getDirection(); + + for(size_t i = 0; i < s; i++) { + p.push_back((i+1)%s); + + if(isConcave(dir, at(i), at((i+1)%s), at((i+2)%s))) + concave.push_back((i+1)%s); + } + + for(size_t i = 0; i < p.size() && p.size() > 3; i++) { + size_t s2 = p.size(); + + const Vertex *v0 = &at(p[i]); + const Vertex *v1 = &at(p[(i+1)%s2]); + const Vertex *v2 = &at(p[(i+2)%s2]); + const Vertex *v3 = &at(p[(i+3)%s2]); + const Vertex *v4 = &at(p[(i+4)%s2]); + + if(isConcave(dir, *v1, *v2, *v3)) + continue; + + Triangle t(*v1, *v2, *v3); + + std::list<size_t>::iterator it = concave.begin(); + for(; it != concave.end(); it++) { + if(*it != p[(i+1)%s2] && *it != p[(i+3)%s2] && t.contains(at(*it))) + break; + } + + if(it != concave.end()) + continue; + + triangles.push_back(t); + + if(isConcave(dir, *v2, *v3, *v4) && !isConcave(dir, *v1, *v3, *v4)) + concave.remove(p[(i+3)%s2]); + + if(isConcave(dir, *v0, *v1, *v2) && !isConcave(dir, *v0, *v1, *v3)) { + concave.remove(p[(i+1)%s2]); + } + + p.erase(p.begin()+(i+2)%s2); + i = 0; + } + + triangles.push_back(Triangle(at(p[0]), at(p[1]), at(p[2]))); +} + +void Polygon::triangulate(std::vector<Triangle> &triangles) const { + Polygon p; + + if(simplify(p)) p.doTriangulate(triangles); + else doTriangulate(triangles); +} |