logo标签列表

寻找圆上离给定点最近的点的最佳方法

algorithmlanguage-agnosticgeometry
40
给定一个点 (pX, pY) 和一个已知圆心 (cX,cY) 和半径 (r) 的圆，您能想出最短的代码来找到距离 (pX, pY) 最近的圆上的点吗？
我有一些代码可以工作，但它涉及将圆转换为形式为 (x-cX)^2 + (y-cY)^2 = r^2（其中 r 是半径）的方程，并使用从点 (pX, pY) 到 (cX, cY) 的线的方程创建要解决的二次方程。
一旦我解决了 bug，它就可以工作，但这似乎是一个不太优雅的解决方案。
3
原文：Was actually for a game but got the solution nonetheless.翻译：这实际上是为了一个游戏，但我仍然找到了解决方案。 - Matt Mitchell
9个回答
71

在适合的“数学”语言中，P是点，C是圆心，R是半径：

V = (P - C); Answer = C + V / |V| * R;

其中|V|表示V的长度。

好的，好的。

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;

易于扩展到>2维。

我在你写出代码之前实现了你发布的数学部分。然而，我发现我需要使用pX - vX而不是pX + pY来获取最近的边。无论如何，谢谢你 - 我很好奇是否有更短的解决方案。 - Matt Mitchell
1
而且，如果半径为零，那还算是圆吗？ - WW.
如果你只是说从圆心到所需点找到标题，标准化并乘以半径。你可以简化一下解释（在我看来）。因此，如果向量A =中心，向量B =所述圆内或外的点 A +（B-A）。normalized * radius;现在，这一切都假设您正在使用结构体或类似的东西进行矢量计算，或者至少已经为您的矢量定义了基本的数学运算符/函数... OP没有提到他们这样做，但我认为这会使您所做的更清晰，然后您可以提供必要的操作来标准化。 - James McGhee
1
@MattMitchell 还有一种特殊情况是 P=C，此时所有点的距离相同，上述建议将因除以0而崩溃。这不会经常成为问题，但可能需要明确处理。 - FirefoxMetzger
1
谢谢，对我来说可以。但是，如果点恰好在圆的中心，则会发生零除以零的情况，请注意。 - Martin Melichar
显示剩余6条评论
7
我会从中心点到该点绘制一条线，并计算图形与圆O的交点。我认为这并不难。
1
......或者穿过圆圈，如果在圆圈内部。 - Brad Gilbert
3
首先通过数学方法解决问题，然后再将其转化为代码。请记住，点与圆边缘之间的最短距离也会经过其中心（正如@litb所说）。
2

  1. 最短距离点位于圆周与通过中心和输入点的直线的交点处。同时，中心、输入和输出点位于一条直线上。

  2. 设中心为(xc, yc)，输入点(xi, yi)到最短点为(x,y)，则sqrt((xc-x)^2 + (yc-y)^2) = r。

  3. 由于中心、输入和输出点位于一条直线上，因此任意两个点之间计算的斜率应相同。

(yc-yi)/(xc-xi) = (y-yc)/(x-xc)

4.解方程2和3应该能给我们最短点。

1

三角函数，乘以r，并根据需要添加pX或pY。

你为什么要避免在三角函数问题中使用三角函数？ - mmcdole
三角函数相对于其他方法通常非常缓慢。一个例子是计算点与线段之间的最短距离; 矩阵代数解法比三角函数快得多。 - MusiGenesis
2
一般来说，如果你正在使用三角函数，那么你可能做错了。通常可以使用向量或其他结构更简单/更快的方法。 - phkahler
1

将圆的中心视为原点，将（pX，pY）的坐标转换为极坐标（theta，r'），将r'替换为原始圆的r并转换回笛卡尔坐标系（并调整原点）。

1
用图片的方式来思考，把它转换成代码很容易：从中心点到目标点的向量（pX - cX, pY - cY）。将其除以长度sqrt(blah blah blah)，再乘以半径。然后加上中心点坐标(cX, cY)即可。
1

你要求最短的代码，这里就是。只需要四行代码，虽然仍然是二次的。 我认为点在圆外面。 我没有考虑如果点直接在圆心上方或下方会发生什么，也就是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] 获取连接点和圆心的线的方程。

2] 沿着该线移动一个半径的距离，以找到圆上的点。即：半径=a^2+b^2，即：r=((cY-Y)+(cX-X))^(1/2)

3] 进行二次求解。X=quadratic_solver(r=((cY-Y)+(cX-X))^(1/2),X)，如果您将Y=m*X+b代入其中，您将得到上面的公式。

4] X和Y是您在圆上的结果。

我相当确定我在某个地方犯了错误，请留言告诉我。当然，它是退化的，一个答案是最远离您的点，另一个答案是最接近的。

这看起来很熟悉。在编程比赛中，我的一个队友使用了这个解决方案，并最终得到了两个类似的解决方案。我们已经完成了所有其他问题，所以我们一起合作，但是找不到哪个解决方案更接近和哪个更远的规则。我选择了暴力破解。这不是作业，它是... - Windows programmer
0
这是我在 Unity 中使用的一个简单方法......针对数学小白们。 它依赖于变换方向，但效果很好。我正在执行 postion.z = 0，但只是加粗您未使用的 2D 圆的轴。
//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);
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接