Best way to find a point on a circle closest to a given point

Question

Given a point (pX, pY) and a circle with a known center (cX,cY) and radius (r), what is the shortest amount of code you can come up with to find the point on the circle closest to (pX, pY) ?

I've got some code kind of working but it involves converting the circle to an equation of the form (x - cX)^2 + (y - cY)^2 = r^2 (where r is radius) and using the equation of the line from point (pX, pY) to (cX, cY) to create a quadratic equation to be solved.

Once I iron out the bugs it'll do, but it seems such an inelegant solution.

Milieu

Was actually for a game but got the solution nonetheless. – Milieu

Answer 1

where P is the point, C is the center, and R is the radius, in a suitable "mathy" language:

V = (P - C); Answer = C + V / |V| * R;

where |V| is length of V.

OK, OK

double vX = pX - cX;
double vY = pY - cY;
double magV = sqrt(vX*vX + vY*vY);
double aX = cX + vX / magV * R;
double aY = cY + vY / magV * R;

easy to extend to >2 dimensions.

Ethbin

I implemented the Maths bit you posted before you wrote out your code. However, I found I needed to have pX - vX, not pX + pY to get the closest side. Anyway thanks for this - I'm curious to see if there are any shorter solutions. – Milieu

V/|V| is the unit vector from C toward P, so I just multiplied it by R and added it to C. Wouldn't you multiply by -R to get the farther point? – Ethbin

I see my mistake. I should have said C + V/|V| * R – Ethbin

Heh, I was using C + anyway :-) – Milieu

The ratio of distance to success divided by time must set a record. – Ethbin

What about when the ponit given is the same as the centre? Special case you need to deal with. – Pierro

And also if the radius is zero - is that still a circle? – Pierro

@WW ... I see what you did there – Milieu

You could simplify the explination a bit (IMO) if you just said Find the heading from center of circle to the desired point, normalize and multiply by radius. So if vector A = center and vector B = your point inside or outside of said circle A + (B - A).normalized * radius; Now this all assumes your using a struct or similar for vectors or at least have defined basic math operators/funcitons for your vectors ... which the OP didn't say they did but it I think does make what your doing more clear you could then provide the nessisary operations to normalize.. – Generate

@MattMitchell There is also the special case of P=C in which case all points have the same distance and the above suggestion will crash with a divide by 0 error. Won't be a problem very often, but might have to be handled explicitly. – Acrodrome

Thank you, works for me. However, if point is exactly at center of circle, then division of zero by zero happens, so be aware of it. – Gloriane

Answer 2

i would make a line from the center to the point, and calc where that graph crosses the circle oO i think not so difficult

Cytoplasm

... or would cross the circle, if inside the circle. – Pathan

Answer 3

Solve it mathematically first, then translate into code. Remember that the shortest line between a point and the edge of a circle will also pass through its center (as stated by @litb).

Pashto

Answer 4

1. The shortest distance point lies at the intersection of circumference and line passing through the center and the input point. Also center, input and output points lie on a straight line

2. let the center be (xc, yc) and shortest point from input (xi, yi) be (x,y) then sqrt((xc-x)^2 + (yc-y)^2) = r

3. since center, input and output points lie on a straight line, slope calculated between any of two of these points should be same.

(yc-yi)/(xc-xi) = (y-yc)/(x-xc)

4.solving equations 2&3 should give us the shortest point.

Semmes

Answer 5

You asked for the shortest code, so here it is. In four lines it can be done, although there is still a quadratic. I've considered the point to be outside the circle. I've not considered what happens if the point is directly above or below the circle center, that is cX=pX.

m=(cY-pY)/(cX-pX);  //slope
b=cY-m*cX;  //or Py-m*Px.  Now you have a line in the form y=m*x+b
X=(  (2mcY)*((-2*m*cY)^2-4*(cY^2+cX^2-b^2-2*b*cY-r^2)*(-1-m^2))^(1/2)  )/(2*(cY^2+cX^2-b^2-2*bc*Y-r^2));
Y=mX+b;

1] Get an equation for a line connecting the point and the circle center.

2] Move along the line a distance of one radius from the center to find the point on the circle. That is: radius=a^2+b^2 which is: r=((cY-Y)+(cX-X))^(1/2)

3] Solve quadratically. X=quadratic_solver(r=((cY-Y)+(cX-X))^(1/2),X) which if you substitute in Y=m*X+b you get that hell above.

4] X and Y are your results on the circle.

I am rather certain I have made an error somewhere, please leave a comment if anyone finds something. Of course it is degenerate, one answer is furthest from your point and the other is closest.

Waltner

This looks familiar. A teammate in a programming contest used this solution and ended up with two solutions like this. We'd finished all the other questions so we all worked together but couldn't find a rule for which is closest and which is furthest. I punted to brute force. It's not homework, it's – Dupre

Answer 6

Trig functions, multiply by r, and add pX or pY as appropriate.

Dupre

Why would you avoid using trig in a trig problem? – Houlberg

Trigonometry is often (usually) very slow relative to other methods. One example is calculating the shortest distance between a point and a line segment; a matrix algrebra solution is much faster than trig. – Dimitry

As a rule of thumb, if you're using trig you're probably not doing it right. There are almost always simpler/faster methods using vectors or other constructs. – Dissertate

Answer 7

Treat the centre of the circular as your origin, convert the co-ordinates of (pX, pY) to polar co-ordinates, (theta, r') replace r' with the original circle's r and convert back to cartesian co-ordinates (and adjust for the origin).

Fleshings

Answer 8

Easy way to think about it in terms of a picture, and easy to turn into code: Take the vector (pX - cX, pY - cY) from the center to the point. Divide by its length sqrt(blah blah blah), multiply by radius. Add this to (cX, cY).

Adventurous

Answer 9

Here is a simple method I use in unity... for the math kn00bs amongst us. Its dependent on the transform orientation but it works nicely. I am doing a postion.z = 0 but just fatten the axis of the 2d circle you are not using.

//Find closest point on circle
Vector3 closestPoint = transform.InverseTransformPoint(m_testPosition.position);
closestPoint.z = 0;
closestPoint = closestPoint.normalized * m_radius;

Gizmos.color = Color.yellow;
Gizmos.DrawWireSphere(transform.TransformPoint(closestPoint), 0.01f);

Myeloid