From 75b25cd91334bc793e02d2d48f67de91abe29399 Mon Sep 17 00:00:00 2001
From: Paul Davis <paul@linuxaudiosystems.com>
Date: Mon, 9 Dec 2013 13:35:07 -0500
Subject: add a utility function to Canvas to compute distance from a point to
 a line segment

---
 libs/canvas/utils.cc | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)

(limited to 'libs/canvas/utils.cc')

diff --git a/libs/canvas/utils.cc b/libs/canvas/utils.cc
index b431042c35..bdc8fad039 100644
--- a/libs/canvas/utils.cc
+++ b/libs/canvas/utils.cc
@@ -154,3 +154,69 @@ ArdourCanvas::set_source_rgba (Cairo::RefPtr<Cairo::Context> context, Color colo
 		);
 }
 
+ArdourCanvas::Distance
+ArdourCanvas::distance_to_segment_squared (Duple const & p, Duple const & p1, Duple const & p2, double& t, Duple& at)
+{
+	static const double kMinSegmentLenSquared = 0.00000001;  // adjust to suit.  If you use float, you'll probably want something like 0.000001f
+	static const double kEpsilon = 1.0E-14;  // adjust to suit.  If you use floats, you'll probably want something like 1E-7f
+	double dx = p2.x - p1.x;
+	double dy = p2.y - p1.y;
+	double dp1x = p.x - p1.x;
+	double dp1y = p.y - p1.y;
+	const double segLenSquared = (dx * dx) + (dy * dy);
+
+	if (segLenSquared >= -kMinSegmentLenSquared && segLenSquared <= kMinSegmentLenSquared) {
+		// segment is a point.
+		at = p1;
+		t = 0.0;
+		return ((dp1x * dp1x) + (dp1y * dp1y));
+	} 
+
+
+	// Project a line from p to the segment [p1,p2].  By considering the line
+	// extending the segment, parameterized as p1 + (t * (p2 - p1)),
+	// we find projection of point p onto the line. 
+	// It falls where t = [(p - p1) . (p2 - p1)] / |p2 - p1|^2
+		
+	t = ((dp1x * dx) + (dp1y * dy)) / segLenSquared;
+
+	if (t < kEpsilon) {
+		// intersects at or to the "left" of first segment vertex (p1.x, p1.y).  If t is approximately 0.0, then
+		// intersection is at p1.  If t is less than that, then there is no intersection (i.e. p is not within
+		// the 'bounds' of the segment)
+		if (t > -kEpsilon) {
+			// intersects at 1st segment vertex
+			t = 0.0;
+		}
+		// set our 'intersection' point to p1.
+		at = p1;
+		// Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
+		// we were doing PointLineDistanceSquared, then qx would be (p1.x + (t * dx)) and qy would be (p1.y + (t * dy)).
+
+	} else if (t > (1.0 - kEpsilon)) {
+		// intersects at or to the "right" of second segment vertex (p2.x, p2.y).  If t is approximately 1.0, then
+		// intersection is at p2.  If t is greater than that, then there is no intersection (i.e. p is not within
+		// the 'bounds' of the segment)
+		if (t < (1.0 + kEpsilon)) {
+			// intersects at 2nd segment vertex
+			t = 1.0;
+		}
+		// set our 'intersection' point to p2.
+		at = p2;
+		// Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
+		// we were doing PointLineDistanceSquared, then qx would be (p1.x + (t * dx)) and qy would be (p1.y + (t * dy)).
+	} else {
+		// The projection of the point to the point on the segment that is perpendicular succeeded and the point
+		// is 'within' the bounds of the segment.  Set the intersection point as that projected point.
+		at = Duple (p1.x + (t * dx), p1.y + (t * dy));
+	}
+
+	// return the squared distance from p to the intersection point.  Note that we return the squared distance
+	// as an optimization because many times you just need to compare relative distances and the squared values
+	// works fine for that.  If you want the ACTUAL distance, just take the square root of this value.
+	double dpqx = p.x - at.x;
+	double dpqy = p.y - at.y;
+
+	return ((dpqx * dpqx) + (dpqy * dpqy));
+}
+
-- 
cgit v1.2.3