Find the closest point to a line from an array of points

Question

I have the problem of finding the point which is closest to a line from an array of x- and y-data. The line is semi-infinite originating from the origin at (0,0) and running into the direction of a given angle.

The x,y data of the points are given in relation to the origin.

How do I find the closest point (and its distance) to the line in line direction (not opposite)?

This is an example of the data I have:

  import numpy as np
  import matplotlib.pyplot as plt

  def main():
    depth = np.random.random((100))*20+50
    angle = np.linspace(0, 2*np.pi, 100)
    x,y = depth2xy(depth, angle)

    line = np.random.random_sample()*2*np.pi

    # fig, ax = plt.subplots(subplot_kw={'projection': 'polar'})
    plt.scatter(x, y)
    plt.plot([0,100*np.cos(line)], [0, 100*np.sin(line)], markersize=10, color = "r")
    plt.show()

  def depth2xy(depth, angle):
    x, y = np.zeros(len(depth)), np.zeros(len(depth))
    for i in range(len(depth)):
      x[i] = depth[i]*np.cos(angle[i])
      y[i] = depth[i]*np.sin(angle[i])
    return x,y

  if __name__ == "__main__": main()

I could try a brute force approach, iterating over different distances along the line to find the ultimate smallest distance.

But as time efficiency is critical my case and the algorithm would not perform as well as I think it could, I would rather try an analytical approach.

I also thought about scipy.spatial.distance, but I am not sure how this would work for a line.

Answer 1

Let P be a point from your know data set. Let Q be the projection of this point on the line. You can use an analytic approach to determine the exact location of Q:

• OQ is the segment from the origin to the Q point. It is aligned to the line.
• PQ is the distance of the point P to the line.
• from geometry, the dot product between QP and OQ is zero (the two segments are orthogonal to each other). From this equation we can compute the point Q.

After that, you simply compute all distances and find the shortest one.

I'm going to use SymPy for the analytical part, Numpy for the numerical part and Matplotlib for plotting:

from sympy import *
import numpy as np
import matplotlib.pyplot as plt

xq, xp, yq, yp, m = symbols("x_Q, x_P, y_Q, y_P, m")
A = Matrix([xq - xp, yq - yp])
B = Matrix([xq, yq])
# this equations contains two unkowns: xq, yq
eq = A.dot(B)

# but we know the line equation: yq = m * xq, so we substitute it into
# eq and solve for xq
xq_expr = solve(eq.subs(yq, m * xq), xq)[1]
print(xq_expr)
# (m*y_P + x_P)/(m**2 + 1)

# generate data
mv = -0.5
xp_vals = np.random.uniform(2, 10, 30)
yp_vals = np.random.uniform(2, 10, 30)

# convert the symbolic expression to a numerical function
f = lambdify([m, xp, yp], xq_expr)
# compute the projections on the line
xq_vals = f(mv, xp_vals, yp_vals)
yq_vals = mv * xq_vals

# compute the distance
d = np.sqrt((xp_vals - xq_vals)**2 + (yp_vals - yq_vals)**2)
# find the index of the shortest distance
idx = d.argmin()

fig, ax = plt.subplots()
xline = np.linspace(0, 10)
yline = mv * xline
ax.plot(xline, yline, "k:", label="line")
ax.scatter(xq_vals, yq_vals, label="Q", marker=".")
ax.scatter(xp_vals, yp_vals, label="P", marker="*")
ax.plot([xp_vals[idx], xq_vals[idx]], [yp_vals[idx], yq_vals[idx]], "r", label="min distance")
ax.set_aspect("equal")
ax.legend()
plt.show()

Answer 2

Your assigned line passes through the origin, its parametric equation is

x = u cos(a)
y = u sin(a)

and you can see the parameter u is simply the (oriented) distance beteween the origin and a point on the assigned line.

Now, consider a point of coordinates X and Y, a line perpendicular to the assigned one has the parametric equation

x = X - v sin(a)
y = Y + v cos(a)

and again, the parameter v is simply the (oriented) distance between (X, Y) and a point on a line passing per (X, Y) and perpendicular to the assigned one.

The intersection is given by the equation

X = u cos(a) + v sin(a)
Y = u sin(a) - v cos(a)

you can check by inspection that the solution of the system is

u = X cos(a) + Y sin(a)
v = X sin(a) - Y cos(a)

The distance of the point (X, Y) from the assigned line is hence

d = | X sin(a) - Y cos(a) |

---

A Python Implementation

import numpy as np
import matplotlib.pyplot as plt

np.random.seed(20221126)

X = 2*np.random.random(32)-1
Y = 2*np.random.random(32)-1

fig, ax = plt.subplots()
ax.set_xlim((-1.2, 1.2))
ax.set_ylim((-1.2, 1.2))
ax.grid(1)
ax.set_aspect(1)

ax.scatter(X, Y, s=80, ec='k', color='y')

a = 2*np.random.random()*np.pi
s, c = np.sin(a), np.cos(a)

plt.plot((0, c), (0, s), color='k')
plt.plot((-s, s), (c, -c), color='r')

# strike out "bad" points
bad = X*c+Y*s<0
plt.scatter(X[bad], Y[bad], marker='x', color='k')

# consider only good (i.e., not bad) points
Xg, Yg = X[~bad], Y[~bad]

# compute all distances (but for good points only)
d = np.abs(Xg*s-Yg*c)
# find the nearest point and hilight it
imin = np.argmin(d)
plt.scatter(Xg[imin], Yg[imin], ec='k', color='r')
plt.show()

---

An OVERDONE Example

import numpy as np
import matplotlib.pyplot as plt

np.random.seed(20221126)

X = 2*np.random.random(32)-1
Y = 2*np.random.random(32)-1

fig, axs = plt.subplots(2, 4, figsize=(10,5), layout='constrained')
for ax, a in zip(axs.flat,
                 (2.8, 1.8, 1.4, 0.2,
                  3.4, 4.5, 4.9, 6.0)): 
  ax.set_xlim((-1.2, 1.2))
  ax.set_xticks((-1, -0.5, 0, 0.5, 1.0))
  ax.set_ylim((-1.2, 1.2))
  ax.grid(1)
  ax.set_aspect(1)
  ax.set_title('$\\alpha \\approx %d^o$'%round(np.rad2deg(a)))

  ax.scatter(X, Y, s=80, ec='k', color='yellow')

  s, c = np.sin(a), np.cos(a)

  ax.arrow(0, 0, 1.2*c, 1.2*s, fc='k',
     length_includes_head=True,
     head_width=0.08, head_length=0.1)

  # divide the drawing surface in two semiplanes    
  if abs(c)>abs(s):
    if c>0:
      ax.plot((1.2*s, -1.2*s), (-1.2, 1.2))
    else:
      ax.plot((-1.2*s, 1.2*s), (-1.2, 1.2))
  elif abs(s)>=abs(c):
    if s>0:
      ax.plot((-1.2, 1.2), (1.2*c, -1.2*c))  
    else:
      ax.plot((-1.2, 1.2), (-1.2*c, 1.2*c))          

  # strike out "bad" points
  bad = X*c+Y*s<0
  ax.scatter(X[bad], Y[bad], marker='x', color='k')

  # consider only good (i.e., not bad) points
  Xg, Yg = X[~bad], Y[~bad]

  # compute all distances (but for good points only)
  d = np.abs(Xg*s-Yg*c)
  # find the nearest point and hilight it
  imin = np.argmin(d)
  ax.scatter(Xg[imin], Yg[imin], s=80, ec='k', color='yellow')
  ax.scatter(Xg[imin], Yg[imin], s= 10, color='k', alpha=1.0)
plt.show()