Merge https://gitlab.com/inkscape/inkscape into selectable-knots

1 files changed, 83 insertions, 6 deletions

diff --git a/src/libavoid/geometry.cpp b/src/libavoid/geometry.cpp
index 2523375cf..7f50800dc 100644
--- a/src/libavoid/geometry.cpp
+++ b/src/libavoid/geometry.cpp
@@ -3,7 +3,7 @@
  *
  * libavoid - Fast, Incremental, Object-avoiding Line Router
  *
- * Copyright (C) 2004-2009  Monash University
+ * Copyright (C) 2004-2011  Monash University
  *
  * --------------------------------------------------------------------
  * Much of the code in this module is based on code published with
@@ -29,18 +29,22 @@
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
  *
- * Author(s):   Michael Wybrow <mjwybrow@users.sourceforge.net>
+ * Author(s):  Michael Wybrow
 */
 
 
+// For M_PI:
+#define _USE_MATH_DEFINES
 #include <cmath>
 
+#include <limits>
+
 #include "libavoid/graph.h"
 #include "libavoid/geometry.h"
 #include "libavoid/assertions.h"
 
-namespace Avoid {
 
+namespace Avoid {
 
 
 // Returns true iff the point c lies on the closed segment ab.
@@ -50,11 +54,13 @@ namespace Avoid {
 //
 bool inBetween(const Point& a, const Point& b, const Point& c)
 {
+    double epsilon = std::numeric_limits<double>::epsilon();
+
     // We only call this when we know the points are collinear,
     // otherwise we should be checking this here.
-    COLA_ASSERT(vecDir(a, b, c, 0.0001) == 0);
+    COLA_ASSERT(vecDir(a, b, c, epsilon) == 0);
 
-    if ((fabs(a.x - b.x) > 1) && (a.x != b.x))
+    if (fabs(a.x - b.x) > epsilon)
     {
         // not vertical
         return (((a.x < c.x) && (c.x < b.x)) ||
@@ -68,11 +74,52 @@ bool inBetween(const Point& a, const Point& b, const Point& c)
 }
 
 
+// Returns true iff the three points are colinear.
+//
+bool colinear(const Point& a, const Point& b, const Point& c,
+        const double tolerance)
+{
+
+    // Do this a bit more optimally for orthogonal AB line segments.
+    if (a == b)
+    {
+        return true;
+    }
+    else if (a.x == b.x)
+    {
+        return (a.x == c.x);
+    }
+    else if (a.y == b.y)
+    {
+        return (a.y == c.y);
+    }
+
+    // Or use the general case.
+    return (vecDir(a, b, c, tolerance) == 0);
+    
+}
+
+
 // Returns true iff the point c lies on the closed segment ab.
 //
 bool pointOnLine(const Point& a, const Point& b, const Point& c, 
         const double tolerance)
 {
+    // Do this a bit more optimally for orthogonal AB line segments.
+    if (a.x == b.x)
+    {
+        return (a.x == c.x) &&
+                (((a.y < c.y) && (c.y < b.y)) ||
+                 ((b.y < c.y) && (c.y < a.y)));
+    }
+    else if (a.y == b.y)
+    {
+        return (a.y == c.y) &&
+                (((a.x < c.x) && (c.x < b.x)) ||
+                 ((b.x < c.x) && (c.x < a.x)));
+    }
+
+    // Or use the general case.
     return (vecDir(a, b, c, tolerance) == 0) && inBetween(a, b, c);
 }
 
@@ -341,7 +388,7 @@ bool inPolyGen(const PolygonInterface& argpoly, const Point& q)
     std::vector<Point>& P = poly.ps;
     size_t    n = poly.size();
 
-    // Shift so that q is the origin. This is done for pedogical clarity.
+    // Shift so that q is the origin. This is done for pedagogical clarity.
     for (size_t i = 0; i < n; ++i)
     {
         P[i].x = P[i].x - q.x;
@@ -559,6 +606,36 @@ int rayIntersectPoint(const Point& a1, const Point& a2,
     return DO_INTERSECT;
 }
 
+// Returns the rotationalAngle, between 0 and 360, of this point from (0,0).
+//
+double rotationalAngle(const Point& p)
+{
+    if (p.y == 0)
+    {
+        return ((p.x < 0) ? 180 : 0);
+    }
+    else if (p.x == 0)
+    {
+        return ((p.y < 0) ? 270 : 90);
+    }
+    
+    double ang = atan(p.y / p.x);
+    ang = (ang * 180) / M_PI;
+
+    if (p.x < 0)
+    {
+        ang += 180;
+    }
+    else if (p.y < 0)
+    {
+        ang += 360;
+    }
+    COLA_ASSERT(ang >= 0);
+    COLA_ASSERT(ang <= 360);
+
+    return ang;
+}
+
 
 }