4
$\begingroup$

My math is a little rusty here but I'm trying to come up with a formula which I can then turn into a python program I'm writing.

Given

I have a circle located at $(cx,cy)$ with radius $r$ and I have a line segment between points $p_1= (x_1,y_1)$ and $p_2 =(x_2,y_2)$

What is the distance between the segment and the circle?

Is there a simple formula which can satisfy my condition - or do I need to look at multiple cases, for example the distance from each end point to the circle and then the distance from the closest point on the line segment?

Thanks!

$\endgroup$
  • $\begingroup$ The solutions below seem fine for lines. For a line segment, check the endpoints also. Take smallest distance. $\endgroup$ – T.J. Gaffney Dec 23 '14 at 5:14
  • $\begingroup$ It doesn't suffice to "take the smallest distance". The distance to the line will always be the smallest, regardless of the position of the point relative to the segment. What you need is to find if the projection of the point on the line lies on the segment or outside of it. $\endgroup$ – fonini Dec 23 '14 at 20:13
1
$\begingroup$

What you want is the distance from the center of the circle to the line, minus the radius.

You must start deriving the equation of your line in the form $ax+by=c$. Substitute $\left(x,y\right)$ for (x1,y1), and then for (x2,y2) to find out the values of $a,b,c$. You will have to choose them so that $a^2+b^2=1$ (or choose as you like, and then divide the whole equation by $a^2+b^2$). You have the following three equations to determine $a,b,c$: $$ax_1+by_1=c$$ $$ax_2+by_2=c$$ $$a^2+b^2=1$$ This will have two solutions: one $\left(a,b,c\right)$ and one $\left(-a,-b,-c\right)$. You can choose either. One easy way is to always use $c>0$.

Now, the distance from a random point $\left(x,y\right)$ to the line will be just $ax+by-c$.

EDIT: Actually, the value $ax+by-c$ will be positive if the point $\left(x,y\right)$ is on one side of the line, and negative if it is on the other side. The distance is, of course, its absolute value.

By the way, the point $\left(a,b\right)$ represents the vector perpendicular to the line, and $c$ is the distance from the origin of the coordinate system to the line.

EDIT 2: At first, I thought you wanted the distance to the line, but it has been pointed out in the comment below that you want the distance to the segment. Well, one way is to observe the point $\left(x-ta,y-tb\right)$, where $t=ax+by-c$. This point is the projection of $\left(x,y\right)$ onto the line. If this point is inside the segment, then the distance to the line is the same as the distance to the segment. If this point is not inside the segment, then the distance to the segment is just the distance to the nearest endpoint.

For the point $\left(x-ta,y-tb\right)$ to be inside the segment, its distance to each endpoint must be less than or equal to the segment length.

$\endgroup$
  • 1
    $\begingroup$ I think distance to a line and distance to a segment are different, if the foot of perpendicular from the point is outside the segment. $\endgroup$ – peterwhy Dec 23 '14 at 2:29
  • $\begingroup$ You're right, I will correct it. $\endgroup$ – fonini Dec 23 '14 at 2:33
1
$\begingroup$

Here is an example Python code that solves the optimization problem suggested by @DeepSea

import casadi as ca
opti = ca.Opti()

# Line segment
t = opti.variable()
line_seg = opti.bounded(0, t, 1)
p0 = (-4.0, 0.5)
p1 = (-2.0, 1.5)
x = (1 - t) * p0 + t * p1

# Circle
y = opti.variable(2)
circ = y[0]**2 + y[1]**2 == 1

# Optimization problem
dist_squared = (x[0] - y[0])**2 + (x[1] - y[1])**2
opti.minimize(dist_squared)
opti.subject_to(line_seg)
opti.subject_to(circ)

# Solve
opti.solver('ipopt')
sol = opti.solve()

# Result
print(f"Distance = {sol.value(ca.sqrt(dist_squared))}")
print(f"Point on line segment: {sol.value(x)}")
print(f"Point on circle: {sol.value(y)}")
$\endgroup$
0
$\begingroup$

Hint: Let $P = (x_1,y_1)t + (1-t)(x_2,y_2)$ be a point on the segment $P_1P_2$, $t \in [0,1]$, and let $A = (x,y)$ be a point on the circle $C: (x-c_x)^2+ (y-c_y)^2 = r^2$, you need to find $AP^2 = f(t)$ and use Lagrange Multiplier to find $t$ which minimizes $f$.

$\endgroup$
0
$\begingroup$

Assuming that you are talking about the perpendicular distance of a point on the circle closest to the given line.

equation of line $P_1P_2$ is $(y-y_1)=\dfrac{y_2-y_1}{x_2-x_1}(x-x_1)$

The formulae for the distance will be $\perp$ distance from the center of the circle to the line - radius of the circle. because the closest point on any curve from a line lies on the common normal to both of them and common normal in this case is the $\perp$ from center to the line.

So the "simple formula" is, $\dfrac{|(y_c-y_1)-\dfrac{y_2-y_1}{x_2-x_1}(x_c-x_1)|}{\sqrt{1+(\dfrac{y_2-y_1}{x_2-x_1})^2}}-r$

$\endgroup$
  • $\begingroup$ And I guess you would then compare the distance to the two endpoints of the segment? $\endgroup$ – Jeef Dec 23 '14 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.