Proposal: distance from point to line segment

[inkihh]

Hi,

first of all thanks a lot for all the work you do.

Now my questions: How can I calculate the distance between two points on a 2d plane? And how can I calculate the minimum distance between a point and a polygon, also on a 2d plane, the polygon can be convex and concave, and the point is somewhere outside the polygon?

Thanks!

[m93a]

If you store the two points as coordinates, calculating the Euclidean distance between them is very easy:

const { subtract, norm, distance } = math;

let A = [1, 2];
let B = [-5, 8];

let d = norm(subtract(A, B)) // 8.485
// or equivalently
let d = distance(A, B) // 8.485

The easiest way to calculate the distance to a polygon is to calculate the distance to each of its edges and take the smallest one. Calculating the distance to edges isn't implemented in mathjs (yet), but it sounds like a fun excersise to write such a function oneself. The important ideas are outlined in this wiki article.

If you get around to implement it, be sure to share it here! 😁️

[inkihh]

Thanks mate! No idea if I'm going to be able to implement the distance-to-polygon function, but I will try!

[inkihh]

I thought I had the formula for the distance between a point and a line, derived from the wiki article, but the results for all the edges of a polygon were vastly wrong. Then it struck me: The lines don't end at the corners of the polygon, but they stretch infinitely.

[m93a]

Yes, you need to implement a distance checker for line segments, not entire lines. Checking distances to a line segment is a little more complicated, this is the way I'd approach the problem:

1. Compute vectors between the points. Vector d⃗ is the direction vector of the line segment, vector u⃗ is a vector from our point X to one of the endpoints of the line segment, v⃗ is from X to the other endpoint.

2. Decompose one of the vectors (let's say u⃗) to two parts, one is perpendicular to d⃗, one is parallel.

3. There are three possible scenarios, the orthogonal projection of X to the line is either on the line segment, to the left of it, or to the right. We can distinguish between these cases three using the scalar product of d⃗ and u⃗.

4. If the orthogonal projection of X to the line lies on the line segment, the distance vector is u⃗_⊥, if it's outside the line segment and closer to A, then the distance vector is u⃗, and in the third case, the distance vector is v⃗. The distance we're looking for is just the length of the distance vector.

[m93a]

This is how I'd implement the method:

const { subtract, norm, dot, multiply, divide } = math

function distanceToLineSegment(X, A, B) {
  const d = subtract(A, B) // direction vector of the line segment
  const u = subtract(A, X) // displacement vector from X to A

  const dSq = dot(d, d)

  const uParallel = multiply( divide(dot(u, d), dSq), d )

  const uParallelDotD = dot(uParallel, d)

  if (uParallelDotD < 0) return norm(u) // distance to A
  if (uParallelDotD > dSq) return norm(subtract(B, X)) // distance to B

  const uPerpendicular = subtract( u, uParallel )
  return norm(uPerpendicular)
}