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

Question

Hi,

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.

Answer 1

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

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

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).

Answer 4

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).

Answer 5

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.

Answer 6

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.

Answer 7

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).