Update poly2tri external library (minor changes only)

qgis · Dec 5, 2019 · a9d02da · a9d02da
1 parent a6c563c
commit a9d02da
Show file tree

Hide file tree

Showing 12 changed files with 115 additions and 48 deletions.
diff --git a/external/poly2tri/common/shapes.cc b/external/poly2tri/common/shapes.cc
@@ -1,6 +1,6 @@
 /*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
+ * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
+ * https://github.com/jhasse/poly2tri
  *
  * All rights reserved.
  *
@@ -29,10 +29,16 @@
  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 #include "shapes.h"
+
+#include <cassert>
 #include <iostream>
 
 namespace p2t {
 
+std::ostream& operator<<(std::ostream& out, const Point& point) {
+  return out << point.x << "," << point.y;
+}
+
 Triangle::Triangle(Point& a, Point& b, Point& c)
 {
   points_[0] = &a; points_[1] = &b; points_[2] = &c;
@@ -356,10 +362,48 @@ Triangle& Triangle::NeighborAcross(const Point& opoint)
 
 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;
+  std::cout << *points_[0] << " " << *points_[1] << " " << *points_[2] << std::endl;
+}
+
+bool Triangle::CircumcicleContains(const Point& point) const
+{
+  assert(IsCounterClockwise());
+  const double dx = points_[0]->x - point.x;
+  const double dy = points_[0]->y - point.y;
+  const double ex = points_[1]->x - point.x;
+  const double ey = points_[1]->y - point.y;
+  const double fx = points_[2]->x - point.x;
+  const double fy = points_[2]->y - point.y;
+
+  const double ap = dx * dx + dy * dy;
+  const double bp = ex * ex + ey * ey;
+  const double cp = fx * fx + fy * fy;
+
+  return (dx * (fy * bp - cp * ey) - dy * (fx * bp - cp * ex) + ap * (fx * ey - fy * ex)) < 0;
+}
+
+bool Triangle::IsCounterClockwise() const
+{
+  return (points_[1]->x - points_[0]->x) * (points_[2]->y - points_[0]->y) -
+             (points_[2]->x - points_[0]->x) * (points_[1]->y - points_[0]->y) >
+         0;
 }
 
-}
+bool IsDelaunay(const std::vector<p2t::Triangle*>& triangles)
+{
+  for (const auto triangle : triangles) {
+    for (const auto other : triangles) {
+      if (triangle == other) {
+        continue;
+      }
+      for (int i = 0; i < 3; ++i) {
+        if (triangle->CircumcicleContains(*other->GetPoint(i))) {
+          return false;
+        }
+      }
+    }
+  }
+  return true;
+}
+
+}
diff --git a/external/poly2tri/common/shapes.h b/external/poly2tri/common/shapes.h
@@ -1,6 +1,6 @@
 /*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
+ * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
+ * https://github.com/jhasse/poly2tri
  *
  * All rights reserved.
  *
@@ -33,10 +33,10 @@
 #ifndef SHAPES_H
 #define SHAPES_H
 
-#include <vector>
-#include <cstddef>
-#include <assert.h>
 #include <cmath>
+#include <cstddef>
+#include <stdexcept>
+#include <vector>
 
 namespace p2t {
 
@@ -119,6 +119,8 @@ struct Point {
 
 };
 
+std::ostream& operator<<(std::ostream&, const Point&);
+
 // Represents a simple polygon's edge
 struct Edge {
 
@@ -130,13 +132,13 @@ struct Edge {
     if (p1.y > p2.y) {
       q = &p1;
       p = &p2;
-    } else if (p1.y == p2.y) {
+    } else if (std::abs(p1.y - p2.y) < 1e-10) {
       if (p1.x > p2.x) {
         q = &p1;
         p = &p2;
-      } else if (p1.x == p2.x) {
+      } else if (std::abs(p1.x - p2.x) < 1e-10) {
         // Repeat points
-        assert(false);
+        throw std::runtime_error("Edge::Edge: p1 == p2");
       }
     }
 
@@ -205,8 +207,12 @@ Triangle& NeighborAcross(const Point& opoint);
 
 void DebugPrint();
 
+bool CircumcicleContains(const Point&) const;
+
 private:
 
+bool IsCounterClockwise() const;
+
 /// Triangle points
 Point* points_[3];
 /// Neighbor list
@@ -318,6 +324,9 @@ inline void Triangle::IsInterior(bool b)
   interior_ = b;
 }
 
+/// Is this set a valid delaunay triangulation?
+bool IsDelaunay(const std::vector<p2t::Triangle*>&);
+
 }
 
-#endif
+#endif
diff --git a/external/poly2tri/common/utils.h b/external/poly2tri/common/utils.h
@@ -1,6 +1,6 @@
 /*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
+ * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
+ * https://github.com/jhasse/poly2tri
  *
  * All rights reserved.
  *
@@ -32,8 +32,18 @@
 #ifndef UTILS_H
 #define UTILS_H
 
+// Otherwise #defines like M_PI are undeclared under Visual Studio
+#define _USE_MATH_DEFINES
+
+#include "shapes.h"
+
+#include <cmath>
 #include <exception>
-#include <math.h>
+
+// C99 removes M_PI from math.h
+#ifndef M_PI
+#define M_PI 3.14159265358979323846264338327
+#endif
 
 namespace p2t {
 

diff --git a/external/poly2tri/poly2tri.h b/external/poly2tri/poly2tri.h
@@ -1,6 +1,6 @@
 /*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
+ * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
+ * https://github.com/jhasse/poly2tri
  *
  * All rights reserved.
  *
@@ -35,4 +35,4 @@
 #include "common/shapes.h"
 #include "sweep/cdt.h"
 
-#endif
+#endif
diff --git a/external/poly2tri/sweep/advancing_front.cc b/external/poly2tri/sweep/advancing_front.cc
@@ -1,6 +1,6 @@
 /*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
+ * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
+ * https://github.com/jhasse/poly2tri
  *
  * All rights reserved.
  *
@@ -30,6 +30,8 @@
  */
 #include "advancing_front.h"
 
+#include <cassert>
+
 namespace p2t {
 
 AdvancingFront::AdvancingFront(Node& head, Node& tail)
@@ -105,4 +107,4 @@ AdvancingFront::~AdvancingFront()
 {
 }
 
-}
+}
diff --git a/external/poly2tri/sweep/advancing_front.h b/external/poly2tri/sweep/advancing_front.h
@@ -1,6 +1,6 @@
 /*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
+ * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
+ * https://github.com/jhasse/poly2tri
  *
  * All rights reserved.
  *
@@ -115,4 +115,4 @@ inline void AdvancingFront::set_search(Node* node)
 
 }
 
-#endif
+#endif
diff --git a/external/poly2tri/sweep/cdt.cc b/external/poly2tri/sweep/cdt.cc
@@ -1,6 +1,6 @@
 /*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
+ * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
+ * https://github.com/jhasse/poly2tri
  *
  * All rights reserved.
  *
@@ -68,4 +68,4 @@ CDT::~CDT()
   delete sweep_;
 }
 
-}
+}
diff --git a/external/poly2tri/sweep/cdt.h b/external/poly2tri/sweep/cdt.h
@@ -1,6 +1,6 @@
 /*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
+ * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
+ * https://github.com/jhasse/poly2tri
  *
  * All rights reserved.
  *
@@ -102,4 +102,4 @@ class CDT
 
 }
 
-#endif
+#endif
diff --git a/external/poly2tri/sweep/sweep.cc b/external/poly2tri/sweep/sweep.cc
@@ -1,6 +1,6 @@
 /*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
+ * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
+ * https://github.com/jhasse/poly2tri
  *
  * All rights reserved.
  *
@@ -28,19 +28,21 @@
  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
-#include <stdexcept>
 #include "sweep.h"
 #include "sweep_context.h"
 #include "advancing_front.h"
 #include "../common/utils.h"
 
+#include <cassert>
+#include <stdexcept>
+
 namespace p2t {
 
 // Triangulate simple polygon with holes
 void Sweep::Triangulate(SweepContext& tcx)
 {
   tcx.InitTriangulation();
-  tcx.CreateAdvancingFront(nodes_);
+  tcx.CreateAdvancingFront();
   // Sweep points; build mesh
   SweepPoints(tcx);
   // Clean up
@@ -791,3 +793,4 @@ Sweep::~Sweep() {
 }
 
 }
+
diff --git a/external/poly2tri/sweep/sweep.h b/external/poly2tri/sweep/sweep.h
@@ -1,6 +1,6 @@
 /*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
+ * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
+ * https://github.com/jhasse/poly2tri
  *
  * All rights reserved.
  *
@@ -282,4 +282,4 @@ class Sweep
 
 }
 
-#endif
+#endif
diff --git a/external/poly2tri/sweep/sweep_context.cc b/external/poly2tri/sweep/sweep_context.cc
@@ -1,6 +1,6 @@
 /*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
+ * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
+ * https://github.com/jhasse/poly2tri
  *
  * All rights reserved.
  *
@@ -120,10 +120,9 @@ Node& SweepContext::LocateNode(const Point& point)
   return *front_->LocateNode(point.x);
 }
 
-void SweepContext::CreateAdvancingFront(const std::vector<Node*>& nodes)
+void SweepContext::CreateAdvancingFront()
 {
 
-  (void) nodes;
   // Initial triangle
   Triangle* triangle = new Triangle(*points_[0], *tail_, *head_);
 

diff --git a/external/poly2tri/sweep/sweep_context.h b/external/poly2tri/sweep/sweep_context.h
@@ -1,6 +1,6 @@
 /*
- * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
- * http://code.google.com/p/poly2tri/
+ * Poly2Tri Copyright (c) 2009-2018, Poly2Tri Contributors
+ * https://github.com/jhasse/poly2tri
  *
  * All rights reserved.
  *
@@ -70,7 +70,7 @@ Node& LocateNode(const Point& point);
 
 void RemoveNode(Node* node);
 
-void CreateAdvancingFront(const std::vector<Node*>& nodes);
+void CreateAdvancingFront();
 
 /// Try to map a node to all sides of this triangle that don't have a neighbor
 void MapTriangleToNodes(Triangle& t);