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) ?
给定一个点(pX,pY)和一个具有已知中心(cX,cY)和半径(r)的圆,你可以想出最短的代码量来找到最接近(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.
我有一些代码工作,但它涉及将圆转换为形式的方程(x - cX)^ 2 +(y - cY)^ 2 = r ^ 2(其中r是半径)并使用方程从点(pX,pY)到(cX,cY)的线,以创建要求解的二次方程。
Once I iron out the bugs it'll do, but it seems such an inelegant solution.
一旦我解决了它会做的错误,但它似乎是一个不优雅的解决方案。
8 个解决方案
#1
60
where P is the point, C is the center, and R is the radius, in a suitable "mathy" language:
其中P是点,C是中心,R是半径,用合适的“mathy”语言:
V = (P - C); Answer = C + V / |V| * R;
where |V| is length of V.
其中| V |是长度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.
易于扩展到> 2维。
#2
8
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
我会从中心到点做一条线,并且在那个图形穿过圆圈的地方进行计算oO我觉得不那么困难
#3
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).
首先用数学方法解决,然后转换成代码。请记住,点和圆的边缘之间的最短线也将穿过其中心(如@litb所述)。
#4
2
-
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
让中心为(xc,yc),输入(xi,yi)的最短点为(x,y),然后是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)
(yc-yi)/(xc-xi)=(y-yc)/(x-xc)
4.solving equations 2&3 should give us the shortest point.
解决方程式2和3应该给我们最短的点。
#5
1
Trig functions, multiply by r, and add pX or pY as appropriate.
Trig函数,乘以r,并根据需要添加pX或pY。
#6
1
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).
将圆形的中心作为原点,将(pX,pY)的坐标转换为极坐标,(theta,r')将r'替换为原始圆的r并转换回笛卡尔坐标(并调整原点)。
#7
1
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.
你问了最短的代码,所以在这里。在四行中可以完成,尽管仍然存在二次曲线。我认为要点在圈外。我没有考虑如果点直接位于圆心的上方或下方,即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.
1]获取连接点和圆心的直线的等式。
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)
2]沿着线移动距离中心一个半径的距离,以找到圆上的点。即:radius = a ^ 2 + b ^ 2,即: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.
3]以二次方式求解。 X = quadratic_solver(r =((cY-Y)+(cX-X))^(1/2),X)如果你在Y = m * X + b中替换你就会得到上面的地狱。
4] X and Y are your results on the circle.
4] X和Y是圆圈上的结果。
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.
我确信我在某个地方犯了错误,如果有人发现某事,请发表评论。当然它是退化的,一个答案离你的观点最远,另一个答案最接近。
#8
1
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).
从图片的角度考虑它很容易,并且很容易变成代码:从中心到点的矢量(pX - cX,pY - cY)。除以它的长度sqrt(等等等等),乘以半径。将其添加到(cX,cY)。
#1
60
where P is the point, C is the center, and R is the radius, in a suitable "mathy" language:
其中P是点,C是中心,R是半径,用合适的“mathy”语言:
V = (P - C); Answer = C + V / |V| * R;
where |V| is length of V.
其中| V |是长度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.
易于扩展到> 2维。
#2
8
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
我会从中心到点做一条线,并且在那个图形穿过圆圈的地方进行计算oO我觉得不那么困难
#3
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).
首先用数学方法解决,然后转换成代码。请记住,点和圆的边缘之间的最短线也将穿过其中心(如@litb所述)。
#4
2
-
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
让中心为(xc,yc),输入(xi,yi)的最短点为(x,y),然后是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)
(yc-yi)/(xc-xi)=(y-yc)/(x-xc)
4.solving equations 2&3 should give us the shortest point.
解决方程式2和3应该给我们最短的点。
#5
1
Trig functions, multiply by r, and add pX or pY as appropriate.
Trig函数,乘以r,并根据需要添加pX或pY。
#6
1
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).
将圆形的中心作为原点,将(pX,pY)的坐标转换为极坐标,(theta,r')将r'替换为原始圆的r并转换回笛卡尔坐标(并调整原点)。
#7
1
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.
你问了最短的代码,所以在这里。在四行中可以完成,尽管仍然存在二次曲线。我认为要点在圈外。我没有考虑如果点直接位于圆心的上方或下方,即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.
1]获取连接点和圆心的直线的等式。
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)
2]沿着线移动距离中心一个半径的距离,以找到圆上的点。即:radius = a ^ 2 + b ^ 2,即: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.
3]以二次方式求解。 X = quadratic_solver(r =((cY-Y)+(cX-X))^(1/2),X)如果你在Y = m * X + b中替换你就会得到上面的地狱。
4] X and Y are your results on the circle.
4] X和Y是圆圈上的结果。
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.
我确信我在某个地方犯了错误,如果有人发现某事,请发表评论。当然它是退化的,一个答案离你的观点最远,另一个答案最接近。
#8
1
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).
从图片的角度考虑它很容易,并且很容易变成代码:从中心到点的矢量(pX - cX,pY - cY)。除以它的长度sqrt(等等等等),乘以半径。将其添加到(cX,cY)。