Katkat
Back

Compute point-to-segment minimum distance

LinkedInMachine Learning Engineer · Technical Screen
EasyMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to apply vector projections and geometric constraints to find the shortest distance from a point to a line segment in a 2D plane.

Problem Statement

Given a point P (px, py) and a line segment defined by two endpoints A (ax, ay) and B (bx, by), compute the minimum Euclidean distance between the point P and any point on the segment AB.

Function Signature

def min_distance_to_segment(px, py, ax, ay, bx, by) -> float:

Constraints

  • Coordinates are floating-point numbers.
  • A and B may be the same point (the segment is a point).
  • The result should be accurate to within 1e-6.

Examples

Example 1:

  • Input: P=(0, 1), A=(0, 0), B=(2, 0)
  • Output: 1.0
  • Explanation: The projection of P onto the line containing AB falls outside the segment (at (0, 0)), so the distance is the distance to A.

Example 2:

  • Input: P=(1, 1), A=(0, 0), B=(2, 0)
  • Output: 1.0
  • Explanation: The projection of P onto the line containing AB is (1, 0), which lies on the segment, so the distance is the perpendicular distance.

Edge Cases

  • The segment AB is a single point (A == B).
  • The point P lies exactly on the segment.
  • The point P aligns with one of the endpoints A or B.

Hints

Hint 1

Represent the segment as a vector V = B - A and the point as a vector W = P - A.

Hint 2

Calculate the projection factor `t` by taking the dot product of W and V, normalized by the squared length of V, to determine where P projects onto the line.

Hint 3

Clamp the value of `t` to the interval [0, 1] to ensure the closest point remains within the boundaries of the segment.

Follow-up questions

  • How would you modify this solution to work in 3D space?
  • If you had to find the minimum distance between two segments AB and CD, how would you approach it?
  • What potential numerical stability issues arise when the segment AB is extremely short, and how could you handle them?