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.
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.
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
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).
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
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
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.
Trig functions, multiply by r, and add pX or pY as appropriate.
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).
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.
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).
