Finding the Best Line for a Point Problem

point_line.js

/*
Here's the approach that I would take. In the description that follows,
P denotes the point where the user clicked, which has coordinates (x_p, y_p).
Each of these steps will involve checking pairs of points against the point
where the user clicked, denoted as A and B, with coordinates (x_a, y_a)
and (x_b, y_b).

We will move forward in three steps:
  first, we will identify those pairs of points that could possibly be our point;
  second, we will calculate the distance from the point to the line defined by
    each of the potential pairs of points;
  third, we select the lines with the shortest distance.
  If we still have an ambiguity, fail.

We could add a fourth step where we pick the line with the closest endpoints, but
in what case would that be necessary?

To run this, execute:
  npm install --save-dev underscore
  npm point_line.js
*/
var _ = require("underscore");

// See http://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line#Cartesian_coordinates
function pointToLineDistance(x, y, a, b, c) {
  var numer = Math.abs(a * x + b * y + c);
  var denom = Math.sqrt(a * a + b * b);
  return numer / denom;
}

// Ring defining the polygon. See the polygon at:
// http://www.wolframalpha.com/share/clip?f=d41d8cd98f00b204e9800998ecf8427e2b939a11cg
var ringPoints = [
  [0,0],
  [0,1],
  [1,1],
  [2,2],
  [3,0]
];
var ringPairs = _(ringPoints).map(function(it,idx) {
  var nextIdx = (idx + 1) % ringPoints.length;
  return [it, ringPoints[nextIdx]];
});

// Point the user clicked on
var userPoint = [1.4,1.6];
var xp = userPoint[0];
var yp = userPoint[1];

// Print out what we are calculating
console.log("Ring Pairs: ");
console.dir(ringPairs);
console.log("User Point: " + userPoint);

// Variable holding the potential pairs
var pairs = ringPairs;

// Remove those elements that could not possibly be our points
pairs = _(pairs).select(function(pair) {
  // Decompose the pair into variables
  var a = pair[0], b = pair[1];
  var xa = a[0], ya = a[1];
  var xb = b[0], yb = b[1];

  // Get the boundaries
  var minX = Math.min(xa, xb);
  var maxX = Math.max(xa, xb);
  var minY = Math.min(ya, yb);
  var maxY = Math.max(ya, yb);

  // Potential pair if pair bounds P on either x or y axis
  return (minX < xp && maxX > xp) ||
         (minY < yp && maxY > yp);
}).map(function(pair) { // Map from pair to the distance to the line
  // Decompose the pair into variables
  var a = pair[0], b = pair[1];
  var xa = a[0], ya = a[1];
  var xb = b[0], yb = b[1];

  var distance;
  if(xa == xb) { // Vertical line
    distance = Math.abs(xp - xa);
  } else if(ya == yb) { // Horizontal line
    distance = Math.abs(yp - ya);
  } else { // Angled line
    // Let "m" be the slope
    var m = (ya - yb) / (xa - xb);
    // The equation for the line is y - ya = m*(x-xa), or 0 = -1*m*x + 1*y + (m*xa - ya)
    // so for pointToLineDistance function, a = -1 * m, b = 1, c = m * xa - ya
    distance = pointToLineDistance(xp, yp, -1 * m, 1, m * xa - ya);
  }

  console.log("Distance from line([" + a + "],[" + b + "]) to [" + userPoint + "] is " + distance);
  return [[a, b], distance];
}).reduce(function(memo, pairWithDistance) { // find smallest distance from point to the lines
 var previousSmallest = memo[0];
 var previousPairs = memo[1];
 var pair = pairWithDistance[0];
 var distance = pairWithDistance[1];
 console.log("Distance to [" + pair[0] + "],[" + pair[1] + "] is " + distance + ", current shortest is " + previousSmallest);
 if(distance < previousSmallest) {
   console.log("\t(New shortest; selecting)");
   return [distance, [pair]];
 } else if(distance == previousSmallest) {
   console.log("\t(Tied for shortest; pushing)");
   previousPairs.push(pair);
   return [distance, previousPairs];
 } else {
   console.log("\t(Longer than shortest; ignoring)");
   return memo;
 }
}, [Number.POSITIVE_INFINITY, []]
).reduce(function(distance,pairs) { // Unwrap the pairs
  console.log("Shortest distance to a line: " + distance);
  return pairs;
});

if(pairs.length == 0) {
  console.error("NO PAIRS FOUND!");
} else if(pairs.length == 1) {
  console.log("Found your pair:");
  console.dir(pairs[0]);
} else {
  console.log("Multiple pairs found!");
  console.dir(pairs);
}