我有一些 r=1 的已知圆圈（下图，4 个圆圈称为 C1 到 C4）。我想在圆圈内找到离 (0,0) 最近的点。有任何多项式算法吗？
问问题
119 次
4 回答
1
离原点最近的点将是以下之一：
两个圆的交点
圆与连接该圆心与原点的直线的交点
原点本身，如果它不位于任何圆圈内
如果这个圆心在原点，圆上有无限个点
检查所有这些点，并找到其中最接近的点，条件是该点不在某个圆圈内。
它会给你复杂度 O(n^3)。
于 2012-12-30T17:11:41.793 回答
1
这不是一个完全可以立即使用的答案，而只是一个供您遵循的草稿（请让我们知道您下次尝试了什么）。
如果 (0,0) 没有被任何圆圈覆盖，则答案将是 (0,0)
如果 (0,0) 被 1 个或多个圆圈覆盖：
（1）这些圆上没有被任何圆覆盖的最近点（可以通过将圆心连接并延伸到（0,0）来计算）应为候选；
（2）这些圆的所有没有被任何圆覆盖的交叉点都应该是候选。
(3)如果(0,0)是1个或多个圆的中心，检查这些圆是否被其他圆完全覆盖。如果没有，则将这些圆圈上未被任何其他圆圈覆盖的任何点添加到候选人中。
找出候选人中的最小值。
于 2012-12-30T17:13:47.723 回答
0
您可以找到圆圈内每个点的距离（0,0）点的长度，然后找到不在圆圈内的邻域的最小值。
于 2012-12-30T16:43:23.503 回答
0
所需点位于以原点为中心并最大内切于某个输入圆 Cn 的所有圆的联合边界上。
算法：
对于每个以 O_i 为中心的半径为 r_i 的输入圆 C_i（其中 O_i 距离原点 d_i，Oi_1^2 + Oi_2^2 = d_i^2），计算内接半径 u_i = r_i - d_i，并找到它们的最大值。远离原点的某个点 u_max 是解决方案
要找到实际点，假设某些 i 的 u_i = u_max。那么你想要的点是 - O_i * u_i / d_i。如果 d_i = 0，那么任何远离原点的点 r_i 都有效。
于 2012-12-30T18:17:53.040 回答