CODEWITHSUNDEEP
algorithmlanguage-agnosticgeometry
Matt Mitchell
Matt Mitchell

Reputation: 41823

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

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.

Upvotes: 43

Views: 41409

Answers (10)

Jack Copeland
Jack Copeland

Reputation: 1

Here's a Python program I've been using for awhile. (p2X,p2Y) is the closest point from (pX,pY) to (cX,cY) It does use trig, and the fact that it's in Python probably makes it pretty slow, but it is only 5 lines.

import math

pX, pY = 1, 1
cX, cY = 0, 0
r = 25

slopeX = pX-cX
slopeY = pY-cY
dir=(math.atan(slopeX/slopeY)+(180*(slopeY<0)))
p2X = cX+math.sin(dir)*r
p2Y = cY+math.cos(dir)*r

Upvotes: 0

Gullie667
Gullie667

Reputation: 135

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

Upvotes: -1

user830818
user830818

Reputation: 417

  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.

Upvotes: 3

Mike Kantor
Mike Kantor

Reputation: 1454

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

Upvotes: 1

Alex
Alex

Reputation: 8881

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.

Upvotes: 2

Mike Dunlavey
Mike Dunlavey

Reputation: 40659

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.

Upvotes: 74

Rob Walker
Rob Walker

Reputation: 47452

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

Upvotes: 1

Daniel Spiewak
Daniel Spiewak

Reputation: 55113

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

Upvotes: 3

Johannes Schaub - litb
Johannes Schaub - litb

Reputation: 506877

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

Upvotes: 7

Windows programmer
Windows programmer

Reputation: 8065

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

Upvotes: 1

Related Questions