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

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.

Answer 1

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 2

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 3

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.

Answer 4

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

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