From 86549ae5135f2efa9ceb0689b88004ede5269668 Mon Sep 17 00:00:00 2001 From: Alex Wilson Date: Thu, 10 May 2012 19:52:26 +1000 Subject: New triangulator for map polygons Replacing the qTriangulate call with poly2tri. This is a BSD-licensed triangulation library that gives better performance for most of our shapes. See http://pastie.org/3893553 for a timing comparison on linux-x86 (timing is given for the whole screen transformation step) The BSD-licensed code is isolated into its own dir (in src/3rdparty) and compiled as a separate static library to be linked in. The files have been renamed (.cc => .cpp) and doubles changed to floats, but are otherwise identical to those found at http://code.google.com/p/poly2tri/ Change-Id: Ib07aadafdc5d4b8ac1024e1eecd70ab39f673197 Reviewed-by: Aaron McCarthy --- doc/config/qtlocation-dita.qdocconf | 3 +- doc/config/qtlocation.qdocconf | 3 +- src/3rdparty/3rdparty.pro | 2 + src/3rdparty/poly2tri/AUTHORS | 8 + src/3rdparty/poly2tri/LICENSE | 27 + src/3rdparty/poly2tri/common/shapes.cpp | 367 ++++++++++ src/3rdparty/poly2tri/common/shapes.h | 325 ++++++++ src/3rdparty/poly2tri/common/utils.h | 123 ++++ src/3rdparty/poly2tri/poly2tri.h | 39 + src/3rdparty/poly2tri/poly2tri.pro | 20 + src/3rdparty/poly2tri/sweep/advancing_front.cpp | 109 +++ src/3rdparty/poly2tri/sweep/advancing_front.h | 118 +++ src/3rdparty/poly2tri/sweep/cdt.cpp | 72 ++ src/3rdparty/poly2tri/sweep/cdt.h | 105 +++ src/3rdparty/poly2tri/sweep/sweep.cpp | 813 +++++++++++++++++++++ src/3rdparty/poly2tri/sweep/sweep.h | 285 ++++++++ src/3rdparty/poly2tri/sweep/sweep_context.cpp | 202 +++++ src/3rdparty/poly2tri/sweep/sweep_context.h | 186 +++++ src/3rdparty/poly2tri_legal.qdoc | 37 + src/imports/location/location.pro | 4 + src/imports/location/qdeclarativecirclemapitem.cpp | 4 + .../location/qdeclarativepolygonmapitem.cpp | 73 +- .../location/qdeclarativepolygonmapitem_p.h | 3 + src/src.pro | 4 +- 24 files changed, 2911 insertions(+), 21 deletions(-) create mode 100644 src/3rdparty/3rdparty.pro create mode 100644 src/3rdparty/poly2tri/AUTHORS create mode 100644 src/3rdparty/poly2tri/LICENSE create mode 100644 src/3rdparty/poly2tri/common/shapes.cpp create mode 100644 src/3rdparty/poly2tri/common/shapes.h create mode 100644 src/3rdparty/poly2tri/common/utils.h create mode 100644 src/3rdparty/poly2tri/poly2tri.h create mode 100644 src/3rdparty/poly2tri/poly2tri.pro create mode 100644 src/3rdparty/poly2tri/sweep/advancing_front.cpp create mode 100644 src/3rdparty/poly2tri/sweep/advancing_front.h create mode 100644 src/3rdparty/poly2tri/sweep/cdt.cpp create mode 100644 src/3rdparty/poly2tri/sweep/cdt.h create mode 100644 src/3rdparty/poly2tri/sweep/sweep.cpp create mode 100644 src/3rdparty/poly2tri/sweep/sweep.h create mode 100644 src/3rdparty/poly2tri/sweep/sweep_context.cpp create mode 100644 src/3rdparty/poly2tri/sweep/sweep_context.h create mode 100644 src/3rdparty/poly2tri_legal.qdoc diff --git a/doc/config/qtlocation-dita.qdocconf b/doc/config/qtlocation-dita.qdocconf index d0a39920..6bb4dd4d 100644 --- a/doc/config/qtlocation-dita.qdocconf +++ b/doc/config/qtlocation-dita.qdocconf @@ -10,7 +10,8 @@ project = Qt Location exampledirs += ../src/examples \ ../.. \ ../../examples \ - ../src + ../src \ + ../../src/3rdparty headerdirs += ../src \ ../../src diff --git a/doc/config/qtlocation.qdocconf b/doc/config/qtlocation.qdocconf index ef7d1557..90ded2a7 100644 --- a/doc/config/qtlocation.qdocconf +++ b/doc/config/qtlocation.qdocconf @@ -18,7 +18,8 @@ exampledirs += ../src/examples \ ../.. \ ../../examples \ ../../examples/declarative \ - ../src + ../src \ + ../../src/3rdparty headerdirs += ../src \ ../../src \ diff --git a/src/3rdparty/3rdparty.pro b/src/3rdparty/3rdparty.pro new file mode 100644 index 00000000..e59086eb --- /dev/null +++ b/src/3rdparty/3rdparty.pro @@ -0,0 +1,2 @@ +TEMPLATE = subdirs +SUBDIRS += poly2tri diff --git a/src/3rdparty/poly2tri/AUTHORS b/src/3rdparty/poly2tri/AUTHORS new file mode 100644 index 00000000..421601ad --- /dev/null +++ b/src/3rdparty/poly2tri/AUTHORS @@ -0,0 +1,8 @@ +Primary Contributors: + + Mason Green (C++, Python) + Thomas Åhlén (Java) + +Other Contributors: + + diff --git a/src/3rdparty/poly2tri/LICENSE b/src/3rdparty/poly2tri/LICENSE new file mode 100644 index 00000000..9417c083 --- /dev/null +++ b/src/3rdparty/poly2tri/LICENSE @@ -0,0 +1,27 @@ +Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors +http://code.google.com/p/poly2tri/ + +All rights reserved. +Redistribution and use in source and binary forms, with or without modification, +are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. +* Neither the name of Poly2Tri nor the names of its contributors may be + used to endorse or promote products derived from this software without specific + prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR +CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/src/3rdparty/poly2tri/common/shapes.cpp b/src/3rdparty/poly2tri/common/shapes.cpp new file mode 100644 index 00000000..b8bcf702 --- /dev/null +++ b/src/3rdparty/poly2tri/common/shapes.cpp @@ -0,0 +1,367 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "shapes.h" +#include + +namespace p2t { + +Triangle::Triangle(Point& a, Point& b, Point& c) +{ + points_[0] = &a; points_[1] = &b; points_[2] = &c; + neighbors_[0] = NULL; neighbors_[1] = NULL; neighbors_[2] = NULL; + constrained_edge[0] = constrained_edge[1] = constrained_edge[2] = false; + delaunay_edge[0] = delaunay_edge[1] = delaunay_edge[2] = false; + interior_ = false; +} + +// Update neighbor pointers +void Triangle::MarkNeighbor(Point* p1, Point* p2, Triangle* t) +{ + if ((p1 == points_[2] && p2 == points_[1]) || (p1 == points_[1] && p2 == points_[2])) + neighbors_[0] = t; + else if ((p1 == points_[0] && p2 == points_[2]) || (p1 == points_[2] && p2 == points_[0])) + neighbors_[1] = t; + else if ((p1 == points_[0] && p2 == points_[1]) || (p1 == points_[1] && p2 == points_[0])) + neighbors_[2] = t; + else + assert(0); +} + +// Exhaustive search to update neighbor pointers +void Triangle::MarkNeighbor(Triangle& t) +{ + if (t.Contains(points_[1], points_[2])) { + neighbors_[0] = &t; + t.MarkNeighbor(points_[1], points_[2], this); + } else if (t.Contains(points_[0], points_[2])) { + neighbors_[1] = &t; + t.MarkNeighbor(points_[0], points_[2], this); + } else if (t.Contains(points_[0], points_[1])) { + neighbors_[2] = &t; + t.MarkNeighbor(points_[0], points_[1], this); + } +} + +/** + * Clears all references to all other triangles and points + */ +void Triangle::Clear() +{ + Triangle *t; + for (int i=0; i<3; i++) + { + t = neighbors_[i]; + if (t != NULL) + { + t->ClearNeighbor( this ); + } + } + ClearNeighbors(); + points_[0]=points_[1]=points_[2] = NULL; +} + +void Triangle::ClearNeighbor(Triangle *triangle ) +{ + if (neighbors_[0] == triangle) + { + neighbors_[0] = NULL; + } + else if (neighbors_[1] == triangle) + { + neighbors_[1] = NULL; + } + else + { + neighbors_[2] = NULL; + } +} + +void Triangle::ClearNeighbors() +{ + neighbors_[0] = NULL; + neighbors_[1] = NULL; + neighbors_[2] = NULL; +} + +void Triangle::ClearDelunayEdges() +{ + delaunay_edge[0] = delaunay_edge[1] = delaunay_edge[2] = false; +} + +Point* Triangle::OppositePoint(Triangle& t, Point& p) +{ + Point *cw = t.PointCW(p); + float x = cw->x; + float y = cw->y; + x = p.x; + y = p.y; + return PointCW(*cw); +} + +// Legalized triangle by rotating clockwise around point(0) +void Triangle::Legalize(Point& point) +{ + points_[1] = points_[0]; + points_[0] = points_[2]; + points_[2] = &point; +} + +// Legalize triagnle by rotating clockwise around oPoint +void Triangle::Legalize(Point& opoint, Point& npoint) +{ + if (&opoint == points_[0]) { + points_[1] = points_[0]; + points_[0] = points_[2]; + points_[2] = &npoint; + } else if (&opoint == points_[1]) { + points_[2] = points_[1]; + points_[1] = points_[0]; + points_[0] = &npoint; + } else if (&opoint == points_[2]) { + points_[0] = points_[2]; + points_[2] = points_[1]; + points_[1] = &npoint; + } else { + assert(0); + } +} + +int Triangle::Index(const Point* p) +{ + if (p == points_[0]) { + return 0; + } else if (p == points_[1]) { + return 1; + } else if (p == points_[2]) { + return 2; + } + assert(0); +} + +int Triangle::EdgeIndex(const Point* p1, const Point* p2) +{ + if (points_[0] == p1) { + if (points_[1] == p2) { + return 2; + } else if (points_[2] == p2) { + return 1; + } + } else if (points_[1] == p1) { + if (points_[2] == p2) { + return 0; + } else if (points_[0] == p2) { + return 2; + } + } else if (points_[2] == p1) { + if (points_[0] == p2) { + return 1; + } else if (points_[1] == p2) { + return 0; + } + } + return -1; +} + +void Triangle::MarkConstrainedEdge(const int index) +{ + constrained_edge[index] = true; +} + +void Triangle::MarkConstrainedEdge(Edge& edge) +{ + MarkConstrainedEdge(edge.p, edge.q); +} + +// Mark edge as constrained +void Triangle::MarkConstrainedEdge(Point* p, Point* q) +{ + if ((q == points_[0] && p == points_[1]) || (q == points_[1] && p == points_[0])) { + constrained_edge[2] = true; + } else if ((q == points_[0] && p == points_[2]) || (q == points_[2] && p == points_[0])) { + constrained_edge[1] = true; + } else if ((q == points_[1] && p == points_[2]) || (q == points_[2] && p == points_[1])) { + constrained_edge[0] = true; + } +} + +// The point counter-clockwise to given point +Point* Triangle::PointCW(Point& point) +{ + if (&point == points_[0]) { + return points_[2]; + } else if (&point == points_[1]) { + return points_[0]; + } else if (&point == points_[2]) { + return points_[1]; + } + assert(0); +} + +// The point counter-clockwise to given point +Point* Triangle::PointCCW(Point& point) +{ + if (&point == points_[0]) { + return points_[1]; + } else if (&point == points_[1]) { + return points_[2]; + } else if (&point == points_[2]) { + return points_[0]; + } + assert(0); +} + +// The neighbor clockwise to given point +Triangle* Triangle::NeighborCW(Point& point) +{ + if (&point == points_[0]) { + return neighbors_[1]; + } else if (&point == points_[1]) { + return neighbors_[2]; + } + return neighbors_[0]; +} + +// The neighbor counter-clockwise to given point +Triangle* Triangle::NeighborCCW(Point& point) +{ + if (&point == points_[0]) { + return neighbors_[2]; + } else if (&point == points_[1]) { + return neighbors_[0]; + } + return neighbors_[1]; +} + +bool Triangle::GetConstrainedEdgeCCW(Point& p) +{ + if (&p == points_[0]) { + return constrained_edge[2]; + } else if (&p == points_[1]) { + return constrained_edge[0]; + } + return constrained_edge[1]; +} + +bool Triangle::GetConstrainedEdgeCW(Point& p) +{ + if (&p == points_[0]) { + return constrained_edge[1]; + } else if (&p == points_[1]) { + return constrained_edge[2]; + } + return constrained_edge[0]; +} + +void Triangle::SetConstrainedEdgeCCW(Point& p, bool ce) +{ + if (&p == points_[0]) { + constrained_edge[2] = ce; + } else if (&p == points_[1]) { + constrained_edge[0] = ce; + } else { + constrained_edge[1] = ce; + } +} + +void Triangle::SetConstrainedEdgeCW(Point& p, bool ce) +{ + if (&p == points_[0]) { + constrained_edge[1] = ce; + } else if (&p == points_[1]) { + constrained_edge[2] = ce; + } else { + constrained_edge[0] = ce; + } +} + +bool Triangle::GetDelunayEdgeCCW(Point& p) +{ + if (&p == points_[0]) { + return delaunay_edge[2]; + } else if (&p == points_[1]) { + return delaunay_edge[0]; + } + return delaunay_edge[1]; +} + +bool Triangle::GetDelunayEdgeCW(Point& p) +{ + if (&p == points_[0]) { + return delaunay_edge[1]; + } else if (&p == points_[1]) { + return delaunay_edge[2]; + } + return delaunay_edge[0]; +} + +void Triangle::SetDelunayEdgeCCW(Point& p, bool e) +{ + if (&p == points_[0]) { + delaunay_edge[2] = e; + } else if (&p == points_[1]) { + delaunay_edge[0] = e; + } else { + delaunay_edge[1] = e; + } +} + +void Triangle::SetDelunayEdgeCW(Point& p, bool e) +{ + if (&p == points_[0]) { + delaunay_edge[1] = e; + } else if (&p == points_[1]) { + delaunay_edge[2] = e; + } else { + delaunay_edge[0] = e; + } +} + +// The neighbor across to given point +Triangle& Triangle::NeighborAcross(Point& opoint) +{ + if (&opoint == points_[0]) { + return *neighbors_[0]; + } else if (&opoint == points_[1]) { + return *neighbors_[1]; + } + return *neighbors_[2]; +} + +void Triangle::DebugPrint() +{ + using namespace std; + cout << points_[0]->x << "," << points_[0]->y << " "; + cout << points_[1]->x << "," << points_[1]->y << " "; + cout << points_[2]->x << "," << points_[2]->y << endl; +} + +} + diff --git a/src/3rdparty/poly2tri/common/shapes.h b/src/3rdparty/poly2tri/common/shapes.h new file mode 100644 index 00000000..6d3f48cd --- /dev/null +++ b/src/3rdparty/poly2tri/common/shapes.h @@ -0,0 +1,325 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +// Include guard +#ifndef SHAPES_H +#define SHAPES_H + +#include +#include +#include +#include + +namespace p2t { + +struct Edge; + +struct Point { + + float x, y; + + /// Default constructor does nothing (for performance). + Point() + { + x = 0.0; + y = 0.0; + } + + /// The edges this point constitutes an upper ending point + std::vector edge_list; + + /// Construct using coordinates. + Point(float x, float y) : x(x), y(y) {} + + /// Set this point to all zeros. + void set_zero() + { + x = 0.0; + y = 0.0; + } + + /// Set this point to some specified coordinates. + void set(float x_, float y_) + { + x = x_; + y = y_; + } + + /// Negate this point. + Point operator -() const + { + Point v; + v.set(-x, -y); + return v; + } + + /// Add a point to this point. + void operator +=(const Point& v) + { + x += v.x; + y += v.y; + } + + /// Subtract a point from this point. + void operator -=(const Point& v) + { + x -= v.x; + y -= v.y; + } + + /// Multiply this point by a scalar. + void operator *=(float a) + { + x *= a; + y *= a; + } + + /// Get the length of this point (the norm). + float Length() const + { + return sqrt(x * x + y * y); + } + + /// Convert this point into a unit point. Returns the Length. + float Normalize() + { + float len = Length(); + x /= len; + y /= len; + return len; + } + +}; + +// Represents a simple polygon's edge +struct Edge { + + Point* p, *q; + + /// Constructor + Edge(Point& p1, Point& p2) : p(&p1), q(&p2) + { + if (p1.y > p2.y) { + q = &p1; + p = &p2; + } else if (p1.y == p2.y) { + if (p1.x > p2.x) { + q = &p1; + p = &p2; + } else if (p1.x == p2.x) { + // Repeat points + assert(false); + } + } + + q->edge_list.push_back(this); + } +}; + +// Triangle-based data structures are know to have better performance than quad-edge structures +// See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator" +// "Triangulations in CGAL" +class Triangle { +public: + +/// Constructor +Triangle(Point& a, Point& b, Point& c); + +/// Flags to determine if an edge is a Constrained edge +bool constrained_edge[3]; +/// Flags to determine if an edge is a Delauney edge +bool delaunay_edge[3]; + +Point* GetPoint(const int& index); +Point* PointCW(Point& point); +Point* PointCCW(Point& point); +Point* OppositePoint(Triangle& t, Point& p); + +Triangle* GetNeighbor(const int& index); +void MarkNeighbor(Point* p1, Point* p2, Triangle* t); +void MarkNeighbor(Triangle& t); + +void MarkConstrainedEdge(const int index); +void MarkConstrainedEdge(Edge& edge); +void MarkConstrainedEdge(Point* p, Point* q); + +int Index(const Point* p); +int EdgeIndex(const Point* p1, const Point* p2); + +Triangle* NeighborCW(Point& point); +Triangle* NeighborCCW(Point& point); +bool GetConstrainedEdgeCCW(Point& p); +bool GetConstrainedEdgeCW(Point& p); +void SetConstrainedEdgeCCW(Point& p, bool ce); +void SetConstrainedEdgeCW(Point& p, bool ce); +bool GetDelunayEdgeCCW(Point& p); +bool GetDelunayEdgeCW(Point& p); +void SetDelunayEdgeCCW(Point& p, bool e); +void SetDelunayEdgeCW(Point& p, bool e); + +bool Contains(Point* p); +bool Contains(const Edge& e); +bool Contains(Point* p, Point* q); +void Legalize(Point& point); +void Legalize(Point& opoint, Point& npoint); +/** + * Clears all references to all other triangles and points + */ +void Clear(); +void ClearNeighbor(Triangle *triangle ); +void ClearNeighbors(); +void ClearDelunayEdges(); + +inline bool IsInterior(); +inline void IsInterior(bool b); + +Triangle& NeighborAcross(Point& opoint); + +void DebugPrint(); + +private: + +/// Triangle points +Point* points_[3]; +/// Neighbor list +Triangle* neighbors_[3]; + +/// Has this triangle been marked as an interior triangle? +bool interior_; +}; + +inline bool cmp(const Point* a, const Point* b) +{ + if (a->y < b->y) { + return true; + } else if (a->y == b->y) { + // Make sure q is point with greater x value + if (a->x < b->x) { + return true; + } + } + return false; +} + +/// Add two points_ component-wise. +inline Point operator +(const Point& a, const Point& b) +{ + return Point(a.x + b.x, a.y + b.y); +} + +/// Subtract two points_ component-wise. +inline Point operator -(const Point& a, const Point& b) +{ + return Point(a.x - b.x, a.y - b.y); +} + +/// Multiply point by scalar +inline Point operator *(float s, const Point& a) +{ + return Point(s * a.x, s * a.y); +} + +inline bool operator ==(const Point& a, const Point& b) +{ + return a.x == b.x && a.y == b.y; +} + +inline bool operator !=(const Point& a, const Point& b) +{ + return a.x != b.x && a.y != b.y; +} + +/// Peform the dot product on two vectors. +inline float Dot(const Point& a, const Point& b) +{ + return a.x * b.x + a.y * b.y; +} + +/// Perform the cross product on two vectors. In 2D this produces a scalar. +inline float Cross(const Point& a, const Point& b) +{ + return a.x * b.y - a.y * b.x; +} + +/// Perform the cross product on a point and a scalar. In 2D this produces +/// a point. +inline Point Cross(const Point& a, float s) +{ + return Point(s * a.y, -s * a.x); +} + +/// Perform the cross product on a scalar and a point. In 2D this produces +/// a point. +inline Point Cross(const float s, const Point& a) +{ + return Point(-s * a.y, s * a.x); +} + +inline Point* Triangle::GetPoint(const int& index) +{ + return points_[index]; +} + +inline Triangle* Triangle::GetNeighbor(const int& index) +{ + return neighbors_[index]; +} + +inline bool Triangle::Contains(Point* p) +{ + return p == points_[0] || p == points_[1] || p == points_[2]; +} + +inline bool Triangle::Contains(const Edge& e) +{ + return Contains(e.p) && Contains(e.q); +} + +inline bool Triangle::Contains(Point* p, Point* q) +{ + return Contains(p) && Contains(q); +} + +inline bool Triangle::IsInterior() +{ + return interior_; +} + +inline void Triangle::IsInterior(bool b) +{ + interior_ = b; +} + +} + +#endif + + diff --git a/src/3rdparty/poly2tri/common/utils.h b/src/3rdparty/poly2tri/common/utils.h new file mode 100644 index 00000000..9f50cc5d --- /dev/null +++ b/src/3rdparty/poly2tri/common/utils.h @@ -0,0 +1,123 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef UTILS_H +#define UTILS_H + +// Otherwise #defines like M_PI are undeclared under Visual Studio +#define _USE_MATH_DEFINES + +#include +#include + +namespace p2t { + +const float PI_3div4 = 3 * M_PI / 4; +const float PI_div2 = 1.57079632679489661923; +const float EPSILON = 1e-12; + +enum Orientation { CW, CCW, COLLINEAR }; + +/** + * Forumla to calculate signed area
+ * Positive if CCW
+ * Negative if CW
+ * 0 if collinear
+ * 
+ * A[P1,P2,P3]  =  (x1*y2 - y1*x2) + (x2*y3 - y2*x3) + (x3*y1 - y3*x1)
+ *              =  (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
+ *
+ */ +Orientation Orient2d(Point& pa, Point& pb, Point& pc) +{ + float detleft = (pa.x - pc.x) * (pb.y - pc.y); + float detright = (pa.y - pc.y) * (pb.x - pc.x); + float val = detleft - detright; + if (val > -EPSILON && val < EPSILON) { + return COLLINEAR; + } else if (val > 0) { + return CCW; + } + return CW; +} + +/* +bool InScanArea(Point& pa, Point& pb, Point& pc, Point& pd) +{ + float pdx = pd.x; + float pdy = pd.y; + float adx = pa.x - pdx; + float ady = pa.y - pdy; + float bdx = pb.x - pdx; + float bdy = pb.y - pdy; + + float adxbdy = adx * bdy; + float bdxady = bdx * ady; + float oabd = adxbdy - bdxady; + + if (oabd <= EPSILON) { + return false; + } + + float cdx = pc.x - pdx; + float cdy = pc.y - pdy; + + float cdxady = cdx * ady; + float adxcdy = adx * cdy; + float ocad = cdxady - adxcdy; + + if (ocad <= EPSILON) { + return false; + } + + return true; +} + +*/ + +bool InScanArea(Point& pa, Point& pb, Point& pc, Point& pd) +{ + float oadb = (pa.x - pb.x)*(pd.y - pb.y) - (pd.x - pb.x)*(pa.y - pb.y); + if (oadb >= -EPSILON) { + return false; + } + + float oadc = (pa.x - pc.x)*(pd.y - pc.y) - (pd.x - pc.x)*(pa.y - pc.y); + if (oadc <= EPSILON) { + return false; + } + return true; +} + +} + +#endif + diff --git a/src/3rdparty/poly2tri/poly2tri.h b/src/3rdparty/poly2tri/poly2tri.h new file mode 100644 index 00000000..042cb3dc --- /dev/null +++ b/src/3rdparty/poly2tri/poly2tri.h @@ -0,0 +1,39 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef POLY2TRI_H +#define POLY2TRI_H + +#include "common/shapes.h" +#include "sweep/cdt.h" + +#endif + diff --git a/src/3rdparty/poly2tri/poly2tri.pro b/src/3rdparty/poly2tri/poly2tri.pro new file mode 100644 index 00000000..04fd7b34 --- /dev/null +++ b/src/3rdparty/poly2tri/poly2tri.pro @@ -0,0 +1,20 @@ +TEMPLATE = lib +TARGET = poly2tri + +CONFIG += staticlib +CONFIG -= qt + +*-g++* { + QMAKE_CXXFLAGS += -O3 -ftree-vectorize -ffast-math -funsafe-math-optimizations +} + +SOURCES += common/shapes.cpp \ + sweep/sweep_context.cpp \ + sweep/cdt.cpp \ + sweep/sweep.cpp \ + sweep/advancing_front.cpp + +# We don't need to install this lib, it's only used for building qtlocation +# However we do have to make sure that 'make install' builds it. +dummytarget.CONFIG = dummy_install +INSTALLS += dummytarget diff --git a/src/3rdparty/poly2tri/sweep/advancing_front.cpp b/src/3rdparty/poly2tri/sweep/advancing_front.cpp new file mode 100644 index 00000000..db4ef558 --- /dev/null +++ b/src/3rdparty/poly2tri/sweep/advancing_front.cpp @@ -0,0 +1,109 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "advancing_front.h" + +namespace p2t { + +AdvancingFront::AdvancingFront(Node& head, Node& tail) +{ + head_ = &head; + tail_ = &tail; + search_node_ = &head; +} + +Node* AdvancingFront::LocateNode(const float& x) +{ + Node* node = search_node_; + + if (x < node->value) { + while ((node = node->prev) != NULL) { + if (x >= node->value) { + search_node_ = node; + return node; + } + } + } else { + while ((node = node->next) != NULL) { + if (x < node->value) { + search_node_ = node->prev; + return node->prev; + } + } + } + return NULL; +} + +Node* AdvancingFront::FindSearchNode(const float& x) +{ + (void)x; // suppress compiler warnings "unused parameter 'x'" + // TODO: implement BST index + return search_node_; +} + +Node* AdvancingFront::LocatePoint(const Point* point) +{ + const float px = point->x; + Node* node = FindSearchNode(px); + const float nx = node->point->x; + + if (px == nx) { + if (point != node->point) { + // We might have two nodes with same x value for a short time + if (point == node->prev->point) { + node = node->prev; + } else if (point == node->next->point) { + node = node->next; + } else { + assert(0); + } + } + } else if (px < nx) { + while ((node = node->prev) != NULL) { + if (point == node->point) { + break; + } + } + } else { + while ((node = node->next) != NULL) { + if (point == node->point) + break; + } + } + if (node) search_node_ = node; + return node; +} + +AdvancingFront::~AdvancingFront() +{ +} + +} + diff --git a/src/3rdparty/poly2tri/sweep/advancing_front.h b/src/3rdparty/poly2tri/sweep/advancing_front.h new file mode 100644 index 00000000..d3f32733 --- /dev/null +++ b/src/3rdparty/poly2tri/sweep/advancing_front.h @@ -0,0 +1,118 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef ADVANCED_FRONT_H +#define ADVANCED_FRONT_H + +#include "../common/shapes.h" + +namespace p2t { + +struct Node; + +// Advancing front node +struct Node { + Point* point; + Triangle* triangle; + + Node* next; + Node* prev; + + float value; + + Node(Point& p) : point(&p), triangle(NULL), next(NULL), prev(NULL), value(p.x) + { + } + + Node(Point& p, Triangle& t) : point(&p), triangle(&t), next(NULL), prev(NULL), value(p.x) + { + } + +}; + +// Advancing front +class AdvancingFront { +public: + +AdvancingFront(Node& head, Node& tail); +// Destructor +~AdvancingFront(); + +Node* head(); +void set_head(Node* node); +Node* tail(); +void set_tail(Node* node); +Node* search(); +void set_search(Node* node); + +/// Locate insertion point along advancing front +Node* LocateNode(const float& x); + +Node* LocatePoint(const Point* point); + +private: + +Node* head_, *tail_, *search_node_; + +Node* FindSearchNode(const float& x); +}; + +inline Node* AdvancingFront::head() +{ + return head_; +} +inline void AdvancingFront::set_head(Node* node) +{ + head_ = node; +} + +inline Node* AdvancingFront::tail() +{ + return tail_; +} +inline void AdvancingFront::set_tail(Node* node) +{ + tail_ = node; +} + +inline Node* AdvancingFront::search() +{ + return search_node_; +} + +inline void AdvancingFront::set_search(Node* node) +{ + search_node_ = node; +} + +} + +#endif diff --git a/src/3rdparty/poly2tri/sweep/cdt.cpp b/src/3rdparty/poly2tri/sweep/cdt.cpp new file mode 100644 index 00000000..e0b3ec79 --- /dev/null +++ b/src/3rdparty/poly2tri/sweep/cdt.cpp @@ -0,0 +1,72 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "cdt.h" + +namespace p2t { + +CDT::CDT(std::vector polyline) +{ + sweep_context_ = new SweepContext(polyline); + sweep_ = new Sweep; +} + +void CDT::AddHole(std::vector polyline) +{ + sweep_context_->AddHole(polyline); +} + +void CDT::AddPoint(Point* point) { + sweep_context_->AddPoint(point); +} + +void CDT::Triangulate() +{ + sweep_->Triangulate(*sweep_context_); +} + +std::vector CDT::GetTriangles() +{ + return sweep_context_->GetTriangles(); +} + +std::list CDT::GetMap() +{ + return sweep_context_->GetMap(); +} + +CDT::~CDT() +{ + delete sweep_context_; + delete sweep_; +} + +} + diff --git a/src/3rdparty/poly2tri/sweep/cdt.h b/src/3rdparty/poly2tri/sweep/cdt.h new file mode 100644 index 00000000..e7b703de --- /dev/null +++ b/src/3rdparty/poly2tri/sweep/cdt.h @@ -0,0 +1,105 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef CDT_H +#define CDT_H + +#include "advancing_front.h" +#include "sweep_context.h" +#include "sweep.h" + +/** + * + * @author Mason Green + * + */ + +namespace p2t { + +class CDT +{ +public: + + /** + * Constructor - add polyline with non repeating points + * + * @param polyline + */ + CDT(std::vector polyline); + + /** + * Destructor - clean up memory + */ + ~CDT(); + + /** + * Add a hole + * + * @param polyline + */ + void AddHole(std::vector polyline); + + /** + * Add a steiner point + * + * @param point + */ + void AddPoint(Point* point); + + /** + * Triangulate - do this AFTER you've added the polyline, holes, and Steiner points + */ + void Triangulate(); + + /** + * Get CDT triangles + */ + std::vector GetTriangles(); + + /** + * Get triangle map + */ + std::list GetMap(); + + private: + + /** + * Internals + */ + + SweepContext* sweep_context_; + Sweep* sweep_; + +}; + +} + +#endif diff --git a/src/3rdparty/poly2tri/sweep/sweep.cpp b/src/3rdparty/poly2tri/sweep/sweep.cpp new file mode 100644 index 00000000..8aaa8f63 --- /dev/null +++ b/src/3rdparty/poly2tri/sweep/sweep.cpp @@ -0,0 +1,813 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include +#include "sweep.h" +#include "sweep_context.h" +#include "advancing_front.h" +#include "../common/utils.h" + +namespace p2t { + +// Triangulate simple polygon with holes +void Sweep::Triangulate(SweepContext& tcx) +{ + tcx.InitTriangulation(); + tcx.CreateAdvancingFront(nodes_); + // Sweep points; build mesh + SweepPoints(tcx); + // Clean up + FinalizationPolygon(tcx); +} + +void Sweep::SweepPoints(SweepContext& tcx) +{ + for (int i = 1; i < tcx.point_count(); i++) { + Point& point = *tcx.GetPoint(i); + Node* node = &PointEvent(tcx, point); + for (unsigned int i = 0; i < point.edge_list.size(); i++) { + EdgeEvent(tcx, point.edge_list[i], node); + } + } +} + +void Sweep::FinalizationPolygon(SweepContext& tcx) +{ + // Get an Internal triangle to start with + Triangle* t = tcx.front()->head()->next->triangle; + Point* p = tcx.front()->head()->next->point; + while (!t->GetConstrainedEdgeCW(*p)) { + t = t->NeighborCCW(*p); + } + + // Collect interior triangles constrained by edges + tcx.MeshClean(*t); +} + +Node& Sweep::PointEvent(SweepContext& tcx, Point& point) +{ + Node& node = tcx.LocateNode(point); + Node& new_node = NewFrontTriangle(tcx, point, node); + + // Only need to check +epsilon since point never have smaller + // x value than node due to how we fetch nodes from the front + if (point.x <= node.point->x + EPSILON) { + Fill(tcx, node); + } + + //tcx.AddNode(new_node); + + FillAdvancingFront(tcx, new_node); + return new_node; +} + +void Sweep::EdgeEvent(SweepContext& tcx, Edge* edge, Node* node) +{ + tcx.edge_event.constrained_edge = edge; + tcx.edge_event.right = (edge->p->x > edge->q->x); + + if (IsEdgeSideOfTriangle(*node->triangle, *edge->p, *edge->q)) { + return; + } + + // For now we will do all needed filling + // TODO: integrate with flip process might give some better performance + // but for now this avoid the issue with cases that needs both flips and fills + FillEdgeEvent(tcx, edge, node); + EdgeEvent(tcx, *edge->p, *edge->q, node->triangle, *edge->q); +} + +void Sweep::EdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* triangle, Point& point) +{ + if (IsEdgeSideOfTriangle(*triangle, ep, eq)) { + return; + } + + Point* p1 = triangle->PointCCW(point); + Orientation o1 = Orient2d(eq, *p1, ep); + if (o1 == COLLINEAR) { + if ( triangle->Contains(&eq, p1)) { + triangle->MarkConstrainedEdge(&eq, p1 ); + // We are modifying the constraint maybe it would be better to + // not change the given constraint and just keep a variable for the new constraint + tcx.edge_event.constrained_edge->q = p1; + triangle = &triangle->NeighborAcross(point); + EdgeEvent( tcx, ep, *p1, triangle, *p1 ); + } else { + std::runtime_error("EdgeEvent - collinear points not supported"); + assert(0); + } + return; + } + + Point* p2 = triangle->PointCW(point); + Orientation o2 = Orient2d(eq, *p2, ep); + if (o2 == COLLINEAR) { + if ( triangle->Contains(&eq, p2)) { + triangle->MarkConstrainedEdge(&eq, p2 ); + // We are modifying the constraint maybe it would be better to + // not change the given constraint and just keep a variable for the new constraint + tcx.edge_event.constrained_edge->q = p2; + triangle = &triangle->NeighborAcross(point); + EdgeEvent( tcx, ep, *p2, triangle, *p2 ); + } else { + std::runtime_error("EdgeEvent - collinear points not supported"); + assert(0); + } + return; + } + + if (o1 == o2) { + // Need to decide if we are rotating CW or CCW to get to a triangle + // that will cross edge + if (o1 == CW) { + triangle = triangle->NeighborCCW(point); + } else{ + triangle = triangle->NeighborCW(point); + } + EdgeEvent(tcx, ep, eq, triangle, point); + } else { + // This triangle crosses constraint so lets flippin start! + FlipEdgeEvent(tcx, ep, eq, triangle, point); + } +} + +bool Sweep::IsEdgeSideOfTriangle(Triangle& triangle, Point& ep, Point& eq) +{ + int index = triangle.EdgeIndex(&ep, &eq); + + if (index != -1) { + triangle.MarkConstrainedEdge(index); + Triangle* t = triangle.GetNeighbor(index); + if (t) { + t->MarkConstrainedEdge(&ep, &eq); + } + return true; + } + return false; +} + +Node& Sweep::NewFrontTriangle(SweepContext& tcx, Point& point, Node& node) +{ + Triangle* triangle = new Triangle(point, *node.point, *node.next->point); + + triangle->MarkNeighbor(*node.triangle); + tcx.AddToMap(triangle); + + Node* new_node = new Node(point); + nodes_.push_back(new_node); + + new_node->next = node.next; + new_node->prev = &node; + node.next->prev = new_node; + node.next = new_node; + + if (!Legalize(tcx, *triangle)) { + tcx.MapTriangleToNodes(*triangle); + } + + return *new_node; +} + +void Sweep::Fill(SweepContext& tcx, Node& node) +{ + Triangle* triangle = new Triangle(*node.prev->point, *node.point, *node.next->point); + + // TODO: should copy the constrained_edge value from neighbor triangles + // for now constrained_edge values are copied during the legalize + triangle->MarkNeighbor(*node.prev->triangle); + triangle->MarkNeighbor(*node.triangle); + + tcx.AddToMap(triangle); + + // Update the advancing front + node.prev->next = node.next; + node.next->prev = node.prev; + + // If it was legalized the triangle has already been mapped + if (!Legalize(tcx, *triangle)) { + tcx.MapTriangleToNodes(*triangle); + } + +} + +void Sweep::FillAdvancingFront(SweepContext& tcx, Node& n) +{ + + // Fill right holes + Node* node = n.next; + + while (node->next) { + // if HoleAngle exceeds 90 degrees then break. + if (LargeHole_DontFill(node)) break; + Fill(tcx, *node); + node = node->next; + } + + // Fill left holes + node = n.prev; + + while (node->prev) { + // if HoleAngle exceeds 90 degrees then break. + if (LargeHole_DontFill(node)) break; + Fill(tcx, *node); + node = node->prev; + } + + // Fill right basins + if (n.next && n.next->next) { + float angle = BasinAngle(n); + if (angle < PI_3div4) { + FillBasin(tcx, n); + } + } +} + +// True if HoleAngle exceeds 90 degrees. +bool Sweep::LargeHole_DontFill(Node* node) { + + Node* nextNode = node->next; + Node* prevNode = node->prev; + if (!AngleExceeds90Degrees(node->point, nextNode->point, prevNode->point)) + return false; + + // Check additional points on front. + Node* next2Node = nextNode->next; + // "..Plus.." because only want angles on same side as point being added. + if ((next2Node != NULL) && !AngleExceedsPlus90DegreesOrIsNegative(node->point, next2Node->point, prevNode->point)) + return false; + + Node* prev2Node = prevNode->prev; + // "..Plus.." because only want angles on same side as point being added. + if ((prev2Node != NULL) && !AngleExceedsPlus90DegreesOrIsNegative(node->point, nextNode->point, prev2Node->point)) + return false; + + return true; +} + +bool Sweep::AngleExceeds90Degrees(Point* origin, Point* pa, Point* pb) { + float angle = Angle(*origin, *pa, *pb); + bool exceeds90Degrees = ((angle > PI_div2) || (angle < -PI_div2)); + return exceeds90Degrees; +} + +bool Sweep::AngleExceedsPlus90DegreesOrIsNegative(Point* origin, Point* pa, Point* pb) { + float angle = Angle(*origin, *pa, *pb); + bool exceedsPlus90DegreesOrIsNegative = (angle > PI_div2) || (angle < 0); + return exceedsPlus90DegreesOrIsNegative; +} + +float Sweep::Angle(Point& origin, Point& pa, Point& pb) { + /* Complex plane + * ab = cosA +i*sinA + * ab = (ax + ay*i)(bx + by*i) = (ax*bx + ay*by) + i(ax*by-ay*bx) + * atan2(y,x) computes the principal value of the argument function + * applied to the complex number x+iy + * Where x = ax*bx + ay*by + * y = ax*by - ay*bx + */ + float px = origin.x; + float py = origin.y; + float ax = pa.x- px; + float ay = pa.y - py; + float bx = pb.x - px; + float by = pb.y - py; + float x = ax * by - ay * bx; + float y = ax * bx + ay * by; + float angle = atan2(x, y); + return angle; +} + +float Sweep::BasinAngle(Node& node) +{ + float ax = node.point->x - node.next->next->point->x; + float ay = node.point->y - node.next->next->point->y; + return atan2(ay, ax); +} + +float Sweep::HoleAngle(Node& node) +{ + /* Complex plane + * ab = cosA +i*sinA + * ab = (ax + ay*i)(bx + by*i) = (ax*bx + ay*by) + i(ax*by-ay*bx) + * atan2(y,x) computes the principal value of the argument function + * applied to the complex number x+iy + * Where x = ax*bx + ay*by + * y = ax*by - ay*bx + */ + float ax = node.next->point->x - node.point->x; + float ay = node.next->point->y - node.point->y; + float bx = node.prev->point->x - node.point->x; + float by = node.prev->point->y - node.point->y; + return atan2(ax * by - ay * bx, ax * bx + ay * by); +} + +bool Sweep::Legalize(SweepContext& tcx, Triangle& t) +{ + // To legalize a triangle we start by finding if any of the three edges + // violate the Delaunay condition + for (int i = 0; i < 3; i++) { + if (t.delaunay_edge[i]) + continue; + + Triangle* ot = t.GetNeighbor(i); + + if (ot) { + Point* p = t.GetPoint(i); + Point* op = ot->OppositePoint(t, *p); + int oi = ot->Index(op); + + // If this is a Constrained Edge or a Delaunay Edge(only during recursive legalization) + // then we should not try to legalize + if (ot->constrained_edge[oi] || ot->delaunay_edge[oi]) { + t.constrained_edge[i] = ot->constrained_edge[oi]; + continue; + } + + bool inside = Incircle(*p, *t.PointCCW(*p), *t.PointCW(*p), *op); + + if (inside) { + // Lets mark this shared edge as Delaunay + t.delaunay_edge[i] = true; + ot->delaunay_edge[oi] = true; + + // Lets rotate shared edge one vertex CW to legalize it + RotateTrianglePair(t, *p, *ot, *op); + + // We now got one valid Delaunay Edge shared by two triangles + // This gives us 4 new edges to check for Delaunay + + // Make sure that triangle to node mapping is done only one time for a specific triangle + bool not_legalized = !Legalize(tcx, t); + if (not_legalized) { + tcx.MapTriangleToNodes(t); + } + + not_legalized = !Legalize(tcx, *ot); + if (not_legalized) + tcx.MapTriangleToNodes(*ot); + + // Reset the Delaunay edges, since they only are valid Delaunay edges + // until we add a new triangle or point. + // XXX: need to think about this. Can these edges be tried after we + // return to previous recursive level? + t.delaunay_edge[i] = false; + ot->delaunay_edge[oi] = false; + + // If triangle have been legalized no need to check the other edges since + // the recursive legalization will handles those so we can end here. + return true; + } + } + } + return false; +} + +bool Sweep::Incircle(Point& pa, Point& pb, Point& pc, Point& pd) +{ + float adx = pa.x - pd.x; + float ady = pa.y - pd.y; + float bdx = pb.x - pd.x; + float bdy = pb.y - pd.y; + + float adxbdy = adx * bdy; + float bdxady = bdx * ady; + float oabd = adxbdy - bdxady; + + if (oabd <= 0) + return false; + + float cdx = pc.x - pd.x; + float cdy = pc.y - pd.y; + + float cdxady = cdx * ady; + float adxcdy = adx * cdy; + float ocad = cdxady - adxcdy; + + if (ocad <= 0) + return false; + + float bdxcdy = bdx * cdy; + float cdxbdy = cdx * bdy; + + float alift = adx * adx + ady * ady; + float blift = bdx * bdx + bdy * bdy; + float clift = cdx * cdx + cdy * cdy; + + float det = alift * (bdxcdy - cdxbdy) + blift * ocad + clift * oabd; + + return det > 0; +} + +void Sweep::RotateTrianglePair(Triangle& t, Point& p, Triangle& ot, Point& op) +{ + Triangle* n1, *n2, *n3, *n4; + n1 = t.NeighborCCW(p); + n2 = t.NeighborCW(p); + n3 = ot.NeighborCCW(op); + n4 = ot.NeighborCW(op); + + bool ce1, ce2, ce3, ce4; + ce1 = t.GetConstrainedEdgeCCW(p); + ce2 = t.GetConstrainedEdgeCW(p); + ce3 = ot.GetConstrainedEdgeCCW(op); + ce4 = ot.GetConstrainedEdgeCW(op); + + bool de1, de2, de3, de4; + de1 = t.GetDelunayEdgeCCW(p); + de2 = t.GetDelunayEdgeCW(p); + de3 = ot.GetDelunayEdgeCCW(op); + de4 = ot.GetDelunayEdgeCW(op); + + t.Legalize(p, op); + ot.Legalize(op, p); + + // Remap delaunay_edge + ot.SetDelunayEdgeCCW(p, de1); + t.SetDelunayEdgeCW(p, de2); + t.SetDelunayEdgeCCW(op, de3); + ot.SetDelunayEdgeCW(op, de4); + + // Remap constrained_edge + ot.SetConstrainedEdgeCCW(p, ce1); + t.SetConstrainedEdgeCW(p, ce2); + t.SetConstrainedEdgeCCW(op, ce3); + ot.SetConstrainedEdgeCW(op, ce4); + + // Remap neighbors + // XXX: might optimize the markNeighbor by keeping track of + // what side should be assigned to what neighbor after the + // rotation. Now mark neighbor does lots of testing to find + // the right side. + t.ClearNeighbors(); + ot.ClearNeighbors(); + if (n1) ot.MarkNeighbor(*n1); + if (n2) t.MarkNeighbor(*n2); + if (n3) t.MarkNeighbor(*n3); + if (n4) ot.MarkNeighbor(*n4); + t.MarkNeighbor(ot); +} + +void Sweep::FillBasin(SweepContext& tcx, Node& node) +{ + if (Orient2d(*node.point, *node.next->point, *node.next->next->point) == CCW) { + tcx.basin.left_node = node.next->next; + } else { + tcx.basin.left_node = node.next; + } + + // Find the bottom and right node + tcx.basin.bottom_node = tcx.basin.left_node; + while (tcx.basin.bottom_node->next + && tcx.basin.bottom_node->point->y >= tcx.basin.bottom_node->next->point->y) { + tcx.basin.bottom_node = tcx.basin.bottom_node->next; + } + if (tcx.basin.bottom_node == tcx.basin.left_node) { + // No valid basin + return; + } + + tcx.basin.right_node = tcx.basin.bottom_node; + while (tcx.basin.right_node->next + && tcx.basin.right_node->point->y < tcx.basin.right_node->next->point->y) { + tcx.basin.right_node = tcx.basin.right_node->next; + } + if (tcx.basin.right_node == tcx.basin.bottom_node) { + // No valid basins + return; + } + + tcx.basin.width = tcx.basin.right_node->point->x - tcx.basin.left_node->point->x; + tcx.basin.left_highest = tcx.basin.left_node->point->y > tcx.basin.right_node->point->y; + + FillBasinReq(tcx, tcx.basin.bottom_node); +} + +void Sweep::FillBasinReq(SweepContext& tcx, Node* node) +{ + // if shallow stop filling + if (IsShallow(tcx, *node)) { + return; + } + + Fill(tcx, *node); + + if (node->prev == tcx.basin.left_node && node->next == tcx.basin.right_node) { + return; + } else if (node->prev == tcx.basin.left_node) { + Orientation o = Orient2d(*node->point, *node->next->point, *node->next->next->point); + if (o == CW) { + return; + } + node = node->next; + } else if (node->next == tcx.basin.right_node) { + Orientation o = Orient2d(*node->point, *node->prev->point, *node->prev->prev->point); + if (o == CCW) { + return; + } + node = node->prev; + } else { + // Continue with the neighbor node with lowest Y value + if (node->prev->point->y < node->next->point->y) { + node = node->prev; + } else { + node = node->next; + } + } + + FillBasinReq(tcx, node); +} + +bool Sweep::IsShallow(SweepContext& tcx, Node& node) +{ + float height; + + if (tcx.basin.left_highest) { + height = tcx.basin.left_node->point->y - node.point->y; + } else { + height = tcx.basin.right_node->point->y - node.point->y; + } + + // if shallow stop filling + if (tcx.basin.width > height) { + return true; + } + return false; +} + +void Sweep::FillEdgeEvent(SweepContext& tcx, Edge* edge, Node* node) +{ + if (tcx.edge_event.right) { + FillRightAboveEdgeEvent(tcx, edge, node); + } else { + FillLeftAboveEdgeEvent(tcx, edge, node); + } +} + +void Sweep::FillRightAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node) +{ + while (node->next->point->x < edge->p->x) { + // Check if next node is below the edge + if (Orient2d(*edge->q, *node->next->point, *edge->p) == CCW) { + FillRightBelowEdgeEvent(tcx, edge, *node); + } else { + node = node->next; + } + } +} + +void Sweep::FillRightBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node) +{ + if (node.point->x < edge->p->x) { + if (Orient2d(*node.point, *node.next->point, *node.next->next->point) == CCW) { + // Concave + FillRightConcaveEdgeEvent(tcx, edge, node); + } else{ + // Convex + FillRightConvexEdgeEvent(tcx, edge, node); + // Retry this one + FillRightBelowEdgeEvent(tcx, edge, node); + } + } +} + +void Sweep::FillRightConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node) +{ + Fill(tcx, *node.next); + if (node.next->point != edge->p) { + // Next above or below edge? + if (Orient2d(*edge->q, *node.next->point, *edge->p) == CCW) { + // Below + if (Orient2d(*node.point, *node.next->point, *node.next->next->point) == CCW) { + // Next is concave + FillRightConcaveEdgeEvent(tcx, edge, node); + } else { + // Next is convex + } + } + } + +} + +void Sweep::FillRightConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node) +{ + // Next concave or convex? + if (Orient2d(*node.next->point, *node.next->next->point, *node.next->next->next->point) == CCW) { + // Concave + FillRightConcaveEdgeEvent(tcx, edge, *node.next); + } else{ + // Convex + // Next above or below edge? + if (Orient2d(*edge->q, *node.next->next->point, *edge->p) == CCW) { + // Below + FillRightConvexEdgeEvent(tcx, edge, *node.next); + } else{ + // Above + } + } +} + +void Sweep::FillLeftAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node) +{ + while (node->prev->point->x > edge->p->x) { + // Check if next node is below the edge + if (Orient2d(*edge->q, *node->prev->point, *edge->p) == CW) { + FillLeftBelowEdgeEvent(tcx, edge, *node); + } else { + node = node->prev; + } + } +} + +void Sweep::FillLeftBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node) +{ + if (node.point->x > edge->p->x) { + if (Orient2d(*node.point, *node.prev->point, *node.prev->prev->point) == CW) { + // Concave + FillLeftConcaveEdgeEvent(tcx, edge, node); + } else { + // Convex + FillLeftConvexEdgeEvent(tcx, edge, node); + // Retry this one + FillLeftBelowEdgeEvent(tcx, edge, node); + } + } +} + +void Sweep::FillLeftConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node) +{ + // Next concave or convex? + if (Orient2d(*node.prev->point, *node.prev->prev->point, *node.prev->prev->prev->point) == CW) { + // Concave + FillLeftConcaveEdgeEvent(tcx, edge, *node.prev); + } else{ + // Convex + // Next above or below edge? + if (Orient2d(*edge->q, *node.prev->prev->point, *edge->p) == CW) { + // Below + FillLeftConvexEdgeEvent(tcx, edge, *node.prev); + } else{ + // Above + } + } +} + +void Sweep::FillLeftConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node) +{ + Fill(tcx, *node.prev); + if (node.prev->point != edge->p) { + // Next above or below edge? + if (Orient2d(*edge->q, *node.prev->point, *edge->p) == CW) { + // Below + if (Orient2d(*node.point, *node.prev->point, *node.prev->prev->point) == CW) { + // Next is concave + FillLeftConcaveEdgeEvent(tcx, edge, node); + } else{ + // Next is convex + } + } + } + +} + +void Sweep::FlipEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* t, Point& p) +{ + Triangle& ot = t->NeighborAcross(p); + Point& op = *ot.OppositePoint(*t, p); + + if (&ot == NULL) { + // If we want to integrate the fillEdgeEvent do it here + // With current implementation we should never get here + //throw new RuntimeException( "[BUG:FIXME] FLIP failed due to missing triangle"); + assert(0); + } + + if (InScanArea(p, *t->PointCCW(p), *t->PointCW(p), op)) { + // Lets rotate shared edge one vertex CW + RotateTrianglePair(*t, p, ot, op); + tcx.MapTriangleToNodes(*t); + tcx.MapTriangleToNodes(ot); + + if (p == eq && op == ep) { + if (eq == *tcx.edge_event.constrained_edge->q && ep == *tcx.edge_event.constrained_edge->p) { + t->MarkConstrainedEdge(&ep, &eq); + ot.MarkConstrainedEdge(&ep, &eq); + Legalize(tcx, *t); + Legalize(tcx, ot); + } else { + // XXX: I think one of the triangles should be legalized here? + } + } else { + Orientation o = Orient2d(eq, op, ep); + t = &NextFlipTriangle(tcx, (int)o, *t, ot, p, op); + FlipEdgeEvent(tcx, ep, eq, t, p); + } + } else { + Point& newP = NextFlipPoint(ep, eq, ot, op); + FlipScanEdgeEvent(tcx, ep, eq, *t, ot, newP); + EdgeEvent(tcx, ep, eq, t, p); + } +} + +Triangle& Sweep::NextFlipTriangle(SweepContext& tcx, int o, Triangle& t, Triangle& ot, Point& p, Point& op) +{ + if (o == CCW) { + // ot is not crossing edge after flip + int edge_index = ot.EdgeIndex(&p, &op); + ot.delaunay_edge[edge_index] = true; + Legalize(tcx, ot); + ot.ClearDelunayEdges(); + return t; + } + + // t is not crossing edge after flip + int edge_index = t.EdgeIndex(&p, &op); + + t.delaunay_edge[edge_index] = true; + Legalize(tcx, t); + t.ClearDelunayEdges(); + return ot; +} + +Point& Sweep::NextFlipPoint(Point& ep, Point& eq, Triangle& ot, Point& op) +{ + Orientation o2d = Orient2d(eq, op, ep); + if (o2d == CW) { + // Right + return *ot.PointCCW(op); + } else if (o2d == CCW) { + // Left + return *ot.PointCW(op); + } else{ + //throw new RuntimeException("[Unsupported] Opposing point on constrained edge"); + assert(0); + } +} + +void Sweep::FlipScanEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle& flip_triangle, + Triangle& t, Point& p) +{ + Triangle& ot = t.NeighborAcross(p); + Point& op = *ot.OppositePoint(t, p); + + if (&t.NeighborAcross(p) == NULL) { + // If we want to integrate the fillEdgeEvent do it here + // With current implementation we should never get here + //throw new RuntimeException( "[BUG:FIXME] FLIP failed due to missing triangle"); + assert(0); + } + + if (InScanArea(eq, *flip_triangle.PointCCW(eq), *flip_triangle.PointCW(eq), op)) { + // flip with new edge op->eq + FlipEdgeEvent(tcx, eq, op, &ot, op); + // TODO: Actually I just figured out that it should be possible to + // improve this by getting the next ot and op before the the above + // flip and continue the flipScanEdgeEvent here + // set new ot and op here and loop back to inScanArea test + // also need to set a new flip_triangle first + // Turns out at first glance that this is somewhat complicated + // so it will have to wait. + } else{ + Point& newP = NextFlipPoint(ep, eq, ot, op); + FlipScanEdgeEvent(tcx, ep, eq, flip_triangle, ot, newP); + } +} + +Sweep::~Sweep() { + + // Clean up memory + for (int i = 0; i < nodes_.size(); i++) { + delete nodes_[i]; + } + +} + +} + diff --git a/src/3rdparty/poly2tri/sweep/sweep.h b/src/3rdparty/poly2tri/sweep/sweep.h new file mode 100644 index 00000000..24f2f8c1 --- /dev/null +++ b/src/3rdparty/poly2tri/sweep/sweep.h @@ -0,0 +1,285 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +/** + * Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V. and + * Zalik, B.(2008)'Sweep-line algorithm for constrained Delaunay triangulation', + * International Journal of Geographical Information Science + * + * "FlipScan" Constrained Edge Algorithm invented by Thomas Åhlén, thahlen@gmail.com + */ + +#ifndef SWEEP_H +#define SWEEP_H + +#include + +namespace p2t { + +class SweepContext; +struct Node; +struct Point; +struct Edge; +class Triangle; + +class Sweep +{ +public: + + /** + * Triangulate + * + * @param tcx + */ + void Triangulate(SweepContext& tcx); + + /** + * Destructor - clean up memory + */ + ~Sweep(); + +private: + + /** + * Start sweeping the Y-sorted point set from bottom to top + * + * @param tcx + */ + void SweepPoints(SweepContext& tcx); + + /** + * Find closes node to the left of the new point and + * create a new triangle. If needed new holes and basins + * will be filled to. + * + * @param tcx + * @param point + * @return + */ + Node& PointEvent(SweepContext& tcx, Point& point); + + /** + * + * + * @param tcx + * @param edge + * @param node + */ + void EdgeEvent(SweepContext& tcx, Edge* edge, Node* node); + + void EdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* triangle, Point& point); + + /** + * Creates a new front triangle and legalize it + * + * @param tcx + * @param point + * @param node + * @return + */ + Node& NewFrontTriangle(SweepContext& tcx, Point& point, Node& node); + + /** + * Adds a triangle to the advancing front to fill a hole. + * @param tcx + * @param node - middle node, that is the bottom of the hole + */ + void Fill(SweepContext& tcx, Node& node); + + /** + * Returns true if triangle was legalized + */ + bool Legalize(SweepContext& tcx, Triangle& t); + + /** + * Requirement:
+ * 1. a,b and c form a triangle.
+ * 2. a and d is know to be on opposite side of bc
+ * 
+   *                a
+   *                +
+   *               / \
+   *              /   \
+   *            b/     \c
+   *            +-------+
+   *           /    d    \
+   *          /           \
+   *
+ * Fact: d has to be in area B to have a chance to be inside the circle formed by + * a,b and c
+ * d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW
+ * This preknowledge gives us a way to optimize the incircle test + * @param a - triangle point, opposite d + * @param b - triangle point + * @param c - triangle point + * @param d - point opposite a + * @return true if d is inside circle, false if on circle edge + */ + bool Incircle(Point& pa, Point& pb, Point& pc, Point& pd); + + /** + * Rotates a triangle pair one vertex CW + *
+   *       n2                    n2
+   *  P +-----+             P +-----+
+   *    | t  /|               |\  t |
+   *    |   / |               | \   |
+   *  n1|  /  |n3           n1|  \  |n3
+   *    | /   |    after CW   |   \ |
+   *    |/ oT |               | oT \|
+   *    +-----+ oP            +-----+
+   *       n4                    n4
+   *
+ */ + void RotateTrianglePair(Triangle& t, Point& p, Triangle& ot, Point& op); + + /** + * Fills holes in the Advancing Front + * + * + * @param tcx + * @param n + */ + void FillAdvancingFront(SweepContext& tcx, Node& n); + + // Decision-making about when to Fill hole. + // Contributed by ToolmakerSteve2 + bool LargeHole_DontFill(Node* node); + bool AngleExceeds90Degrees(Point* origin, Point* pa, Point* pb); + bool AngleExceedsPlus90DegreesOrIsNegative(Point* origin, Point* pa, Point* pb); + float Angle(Point& origin, Point& pa, Point& pb); + + /** + * + * @param node - middle node + * @return the angle between 3 front nodes + */ + float HoleAngle(Node& node); + + /** + * The basin angle is decided against the horizontal line [1,0] + */ + float BasinAngle(Node& node); + + /** + * Fills a basin that has formed on the Advancing Front to the right + * of given node.
+ * First we decide a left,bottom and right node that forms the + * boundaries of the basin. Then we do a reqursive fill. + * + * @param tcx + * @param node - starting node, this or next node will be left node + */ + void FillBasin(SweepContext& tcx, Node& node); + + /** + * Recursive algorithm to fill a Basin with triangles + * + * @param tcx + * @param node - bottom_node + * @param cnt - counter used to alternate on even and odd numbers + */ + void FillBasinReq(SweepContext& tcx, Node* node); + + bool IsShallow(SweepContext& tcx, Node& node); + + bool IsEdgeSideOfTriangle(Triangle& triangle, Point& ep, Point& eq); + + void FillEdgeEvent(SweepContext& tcx, Edge* edge, Node* node); + + void FillRightAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node); + + void FillRightBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); + + void FillRightConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); + + void FillRightConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); + + void FillLeftAboveEdgeEvent(SweepContext& tcx, Edge* edge, Node* node); + + void FillLeftBelowEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); + + void FillLeftConcaveEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); + + void FillLeftConvexEdgeEvent(SweepContext& tcx, Edge* edge, Node& node); + + void FlipEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle* t, Point& p); + + /** + * After a flip we have two triangles and know that only one will still be + * intersecting the edge. So decide which to contiune with and legalize the other + * + * @param tcx + * @param o - should be the result of an orient2d( eq, op, ep ) + * @param t - triangle 1 + * @param ot - triangle 2 + * @param p - a point shared by both triangles + * @param op - another point shared by both triangles + * @return returns the triangle still intersecting the edge + */ + Triangle& NextFlipTriangle(SweepContext& tcx, int o, Triangle& t, Triangle& ot, Point& p, Point& op); + + /** + * When we need to traverse from one triangle to the next we need + * the point in current triangle that is the opposite point to the next + * triangle. + * + * @param ep + * @param eq + * @param ot + * @param op + * @return + */ + Point& NextFlipPoint(Point& ep, Point& eq, Triangle& ot, Point& op); + + /** + * Scan part of the FlipScan algorithm
+ * When a triangle pair isn't flippable we will scan for the next + * point that is inside the flip triangle scan area. When found + * we generate a new flipEdgeEvent + * + * @param tcx + * @param ep - last point on the edge we are traversing + * @param eq - first point on the edge we are traversing + * @param flipTriangle - the current triangle sharing the point eq with edge + * @param t + * @param p + */ + void FlipScanEdgeEvent(SweepContext& tcx, Point& ep, Point& eq, Triangle& flip_triangle, Triangle& t, Point& p); + + void FinalizationPolygon(SweepContext& tcx); + + std::vector nodes_; + +}; + +} + +#endif diff --git a/src/3rdparty/poly2tri/sweep/sweep_context.cpp b/src/3rdparty/poly2tri/sweep/sweep_context.cpp new file mode 100644 index 00000000..85c5b5dc --- /dev/null +++ b/src/3rdparty/poly2tri/sweep/sweep_context.cpp @@ -0,0 +1,202 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "sweep_context.h" +#include +#include "advancing_front.h" + +namespace p2t { + +SweepContext::SweepContext(std::vector polyline) +{ + basin = Basin(); + edge_event = EdgeEvent(); + + points_ = polyline; + + InitEdges(points_); +} + +void SweepContext::AddHole(std::vector polyline) +{ + InitEdges(polyline); + for (unsigned int i = 0; i < polyline.size(); i++) { + points_.push_back(polyline[i]); + } +} + +void SweepContext::AddPoint(Point* point) { + points_.push_back(point); +} + +std::vector SweepContext::GetTriangles() +{ + return triangles_; +} + +std::list SweepContext::GetMap() +{ + return map_; +} + +void SweepContext::InitTriangulation() +{ + float xmax(points_[0]->x), xmin(points_[0]->x); + float ymax(points_[0]->y), ymin(points_[0]->y); + + // Calculate bounds. + for (unsigned int i = 0; i < points_.size(); i++) { + Point& p = *points_[i]; + if (p.x > xmax) + xmax = p.x; + if (p.x < xmin) + xmin = p.x; + if (p.y > ymax) + ymax = p.y; + if (p.y < ymin) + ymin = p.y; + } + + float dx = kAlpha * (xmax - xmin); + float dy = kAlpha * (ymax - ymin); + head_ = new Point(xmax + dx, ymin - dy); + tail_ = new Point(xmin - dx, ymin - dy); + + // Sort points along y-axis + std::sort(points_.begin(), points_.end(), cmp); + +} + +void SweepContext::InitEdges(std::vector polyline) +{ + int num_points = polyline.size(); + for (int i = 0; i < num_points; i++) { + int j = i < num_points - 1 ? i + 1 : 0; + edge_list.push_back(new Edge(*polyline[i], *polyline[j])); + } +} + +Point* SweepContext::GetPoint(const int& index) +{ + return points_[index]; +} + +void SweepContext::AddToMap(Triangle* triangle) +{ + map_.push_back(triangle); +} + +Node& SweepContext::LocateNode(Point& point) +{ + // TODO implement search tree + return *front_->LocateNode(point.x); +} + +void SweepContext::CreateAdvancingFront(std::vector nodes) +{ + + (void) nodes; + // Initial triangle + Triangle* triangle = new Triangle(*points_[0], *tail_, *head_); + + map_.push_back(triangle); + + af_head_ = new Node(*triangle->GetPoint(1), *triangle); + af_middle_ = new Node(*triangle->GetPoint(0), *triangle); + af_tail_ = new Node(*triangle->GetPoint(2)); + front_ = new AdvancingFront(*af_head_, *af_tail_); + + // TODO: More intuitive if head is middles next and not previous? + // so swap head and tail + af_head_->next = af_middle_; + af_middle_->next = af_tail_; + af_middle_->prev = af_head_; + af_tail_->prev = af_middle_; +} + +void SweepContext::RemoveNode(Node* node) +{ + delete node; +} + +void SweepContext::MapTriangleToNodes(Triangle& t) +{ + for (int i = 0; i < 3; i++) { + if (!t.GetNeighbor(i)) { + Node* n = front_->LocatePoint(t.PointCW(*t.GetPoint(i))); + if (n) + n->triangle = &t; + } + } +} + +void SweepContext::RemoveFromMap(Triangle* triangle) +{ + map_.remove(triangle); +} + +void SweepContext::MeshClean(Triangle& triangle) +{ + if (&triangle != NULL && !triangle.IsInterior()) { + triangle.IsInterior(true); + triangles_.push_back(&triangle); + for (int i = 0; i < 3; i++) { + if (!triangle.constrained_edge[i]) + MeshClean(*triangle.GetNeighbor(i)); + } + } +} + +SweepContext::~SweepContext() +{ + + // Clean up memory + + delete head_; + delete tail_; + delete front_; + delete af_head_; + delete af_middle_; + delete af_tail_; + + typedef std::list type_list; + + for (type_list::iterator iter = map_.begin(); iter != map_.end(); ++iter) { + Triangle* ptr = *iter; + delete ptr; + } + + for (unsigned int i = 0; i < edge_list.size(); i++) { + delete edge_list[i]; + } + +} + +} diff --git a/src/3rdparty/poly2tri/sweep/sweep_context.h b/src/3rdparty/poly2tri/sweep/sweep_context.h new file mode 100644 index 00000000..08bba8cb --- /dev/null +++ b/src/3rdparty/poly2tri/sweep/sweep_context.h @@ -0,0 +1,186 @@ +/* + * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors + * http://code.google.com/p/poly2tri/ + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, + * are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * * Neither the name of Poly2Tri nor the names of its contributors may be + * used to endorse or promote products derived from this software without specific + * prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef SWEEP_CONTEXT_H +#define SWEEP_CONTEXT_H + +#include +#include +#include + +namespace p2t { + +// Inital triangle factor, seed triangle will extend 30% of +// PointSet width to both left and right. +const float kAlpha = 0.3; + +struct Point; +class Triangle; +struct Node; +struct Edge; +class AdvancingFront; + +class SweepContext { +public: + +/// Constructor +SweepContext(std::vector polyline); +/// Destructor +~SweepContext(); + +void set_head(Point* p1); + +Point* head(); + +void set_tail(Point* p1); + +Point* tail(); + +int point_count(); + +Node& LocateNode(Point& point); + +void RemoveNode(Node* node); + +void CreateAdvancingFront(std::vector nodes); + +/// Try to map a node to all sides of this triangle that don't have a neighbor +void MapTriangleToNodes(Triangle& t); + +void AddToMap(Triangle* triangle); + +Point* GetPoint(const int& index); + +Point* GetPoints(); + +void RemoveFromMap(Triangle* triangle); + +void AddHole(std::vector polyline); + +void AddPoint(Point* point); + +AdvancingFront* front(); + +void MeshClean(Triangle& triangle); + +std::vector GetTriangles(); +std::list GetMap(); + +std::vector edge_list; + +struct Basin { + Node* left_node; + Node* bottom_node; + Node* right_node; + float width; + bool left_highest; + + Basin() : left_node(NULL), bottom_node(NULL), right_node(NULL), width(0.0), left_highest(false) + { + } + + void Clear() + { + left_node = NULL; + bottom_node = NULL; + right_node = NULL; + width = 0.0; + left_highest = false; + } +}; + +struct EdgeEvent { + Edge* constrained_edge; + bool right; + + EdgeEvent() : constrained_edge(NULL), right(false) + { + } +}; + +Basin basin; +EdgeEvent edge_event; + +private: + +friend class Sweep; + +std::vector triangles_; +std::list map_; +std::vector points_; + +// Advancing front +AdvancingFront* front_; +// head point used with advancing front +Point* head_; +// tail point used with advancing front +Point* tail_; + +Node *af_head_, *af_middle_, *af_tail_; + +void InitTriangulation(); +void InitEdges(std::vector polyline); + +}; + +inline AdvancingFront* SweepContext::front() +{ + return front_; +} + +inline int SweepContext::point_count() +{ + return points_.size(); +} + +inline void SweepContext::set_head(Point* p1) +{ + head_ = p1; +} + +inline Point* SweepContext::head() +{ + return head_; +} + +inline void SweepContext::set_tail(Point* p1) +{ + tail_ = p1; +} + +inline Point* SweepContext::tail() +{ + return tail_; +} + +} + +#endif diff --git a/src/3rdparty/poly2tri_legal.qdoc b/src/3rdparty/poly2tri_legal.qdoc new file mode 100644 index 00000000..acbb2646 --- /dev/null +++ b/src/3rdparty/poly2tri_legal.qdoc @@ -0,0 +1,37 @@ +/*! +\page legal-poly2tri.html +\title Poly2Tri Polygon Triangulation Library +\ingroup licensing + +\legalese +\code +Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors +http://code.google.com/p/poly2tri/ + +All rights reserved. +Redistribution and use in source and binary forms, with or without modification, +are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. +* Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. +* Neither the name of Poly2Tri nor the names of its contributors may be + used to endorse or promote products derived from this software without specific + prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR +CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +\endcode +\endlegalese +*/ diff --git a/src/imports/location/location.pro b/src/imports/location/location.pro index f17ce858..34fa41e7 100644 --- a/src/imports/location/location.pro +++ b/src/imports/location/location.pro @@ -12,6 +12,9 @@ INCLUDEPATH += ../../location/maps INCLUDEPATH *= $$PWD DEFINES += TOUCH_EVENT_WORKAROUND +LIBS += -L../../3rdparty/poly2tri -lpoly2tri +win32:LIBS += -L../../3rdparty/poly2tri/release -L../../3rdparty/poly2tri/debug + # On some platforms, build both versions because debug and release # versions are incompatible #win32|mac:!wince*:!win32-msvc:!macx-xcode:CONFIG += debug_and_release @@ -114,3 +117,4 @@ INSTALLS += target qmldir OTHER_FILES += \ plugin.json + diff --git a/src/imports/location/qdeclarativecirclemapitem.cpp b/src/imports/location/qdeclarativecirclemapitem.cpp index 599734f3..47836b5d 100644 --- a/src/imports/location/qdeclarativecirclemapitem.cpp +++ b/src/imports/location/qdeclarativecirclemapitem.cpp @@ -192,6 +192,10 @@ QDeclarativeCircleMapItem::QDeclarativeCircleMapItem(QQuickItem *parent): this, SLOT(updateMapItemAssumeDirty())); QObject::connect(&border_, SIGNAL(widthChanged(qreal)), this, SLOT(updateMapItemAssumeDirty())); + + // assume that circles are not self-intersecting + // to speed up processing + geometry_.setAssumeSimple(true); } QDeclarativeCircleMapItem::~QDeclarativeCircleMapItem() diff --git a/src/imports/location/qdeclarativepolygonmapitem.cpp b/src/imports/location/qdeclarativepolygonmapitem.cpp index a07f8439..fa7db6c4 100644 --- a/src/imports/location/qdeclarativepolygonmapitem.cpp +++ b/src/imports/location/qdeclarativepolygonmapitem.cpp @@ -47,6 +47,10 @@ #include #include +/* poly2tri triangulator includes */ +#include "../../3rdparty/poly2tri/common/shapes.h" +#include "../../3rdparty/poly2tri/sweep/cdt.h" + QT_BEGIN_NAMESPACE /*! @@ -116,7 +120,7 @@ struct Vertex }; QGeoMapPolygonGeometry::QGeoMapPolygonGeometry(QObject *parent) : - QGeoMapItemGeometry(parent) + QGeoMapItemGeometry(parent), assumeSimple_(false) { } @@ -131,6 +135,7 @@ void QGeoMapPolygonGeometry::updateSourcePoints(const QGeoMap &map, // build the actual path QPointF origin; + QPointF lastPoint; srcPath_ = QPainterPath(); for (int i = 0; i < path.size(); ++i) { const QGeoCoordinate &coord = path.at(i); @@ -149,12 +154,20 @@ void QGeoMapPolygonGeometry::updateSourcePoints(const QGeoMap &map, origin = point; srcOrigin_ = coord; srcPath_.moveTo(point - origin); + lastPoint = point; } else { - srcPath_.lineTo(point - origin); + const QPointF diff = (point - lastPoint); + if (diff.x() * diff.x() + diff.y() * diff.y() >= 3.0) { + srcPath_.lineTo(point - origin); + lastPoint = point; + } } } srcPath_.closeSubpath(); + if (!assumeSimple_) + srcPath_ = srcPath_.simplified(); + sourceBounds_ = srcPath_.boundingRect(); } @@ -195,25 +208,51 @@ void QGeoMapPolygonGeometry::updateScreenPoints(const QGeoMap &map) ppi.translate(-bb.left(), -bb.top()); firstPointOffset_ = -1 * bb.topLeft(); - screenOutline_ = ppi; + ppi.closeSubpath(); - QTriangleSet ts = qTriangulate(ppi); - qreal *vx = ts.vertices.data(); + screenOutline_ = ppi; - screenIndices_.reserve(ts.indices.size()); - screenVertices_.reserve(ts.vertices.size()); + std::vector curPts; + curPts.reserve(ppi.elementCount()); + + for (int i = 0; i < ppi.elementCount(); ++i) { + const QPainterPath::Element e = ppi.elementAt(i); + if (e.isMoveTo() || i == ppi.elementCount() - 1 + || (qAbs(e.x - curPts.front()->x) < 0.1 + && qAbs(e.y - curPts.front()->y) < 0.1)) { + if (curPts.size() > 2) { + p2t::CDT *cdt = new p2t::CDT(curPts); + cdt->Triangulate(); + std::vector tris = cdt->GetTriangles(); + + screenVertices_.reserve(screenVertices_.size() + tris.size()); + + for (int i = 0; i < tris.size(); ++i) { + p2t::Triangle *t = tris.at(i); + + for (int j = 0; j < 3; ++j) { + p2t::Point *p = t->GetPoint(j); + screenVertices_ << Point(p->x, p->y); + } + } + + delete cdt; + } + curPts.clear(); + curPts.reserve(ppi.elementCount() - i); + curPts.push_back(new p2t::Point(e.x, e.y)); + } else if (e.isLineTo()) { + curPts.push_back(new p2t::Point(e.x, e.y)); + } else { + qWarning("Unhandled element type in polygon painterpath"); + } + } - if (ts.indices.type() == QVertexIndexVector::UnsignedInt) { - const quint32 *ix = reinterpret_cast(ts.indices.data()); - for (int i = 0; i < (ts.indices.size()/3*3); ++i) - screenIndices_ << ix[i]; - } else { - const quint16 *ix = reinterpret_cast(ts.indices.data()); - for (int i = 0; i < (ts.indices.size()/3*3); ++i) - screenIndices_ << ix[i]; + if (curPts.size() > 0) { + for (int i = 0; i < curPts.size(); ++i) + delete curPts.at(i); + curPts.clear(); } - for (int i = 0; i < (ts.vertices.size()/2*2); i += 2) - screenVertices_ << Point(vx[i], vx[i + 1]); screenBounds_ = ppi.boundingRect(); } diff --git a/src/imports/location/qdeclarativepolygonmapitem_p.h b/src/imports/location/qdeclarativepolygonmapitem_p.h index 9059e7cd..1347a346 100644 --- a/src/imports/location/qdeclarativepolygonmapitem_p.h +++ b/src/imports/location/qdeclarativepolygonmapitem_p.h @@ -59,6 +59,8 @@ class QGeoMapPolygonGeometry : public QGeoMapItemGeometry public: explicit QGeoMapPolygonGeometry(QObject *parent = 0); + inline void setAssumeSimple(bool value) { assumeSimple_ = value; } + void updateSourcePoints(const QGeoMap &map, const QList &path); @@ -66,6 +68,7 @@ public: private: QPainterPath srcPath_; + bool assumeSimple_; }; class QDeclarativePolygonMapItem : public QDeclarativeGeoMapItemBase diff --git a/src/src.pro b/src/src.pro index 3b54b67b..2a616cc8 100644 --- a/src/src.pro +++ b/src/src.pro @@ -1,4 +1,4 @@ TEMPLATE = subdirs -CONFIG+=ordered -SUBDIRS += location plugins imports +CONFIG += ordered +SUBDIRS += 3rdparty location plugins imports -- cgit v1.2.1