你如何确定是否可以在一组点周围绘制一个圆,使得另一组中的点不在其中？
14 algorithm math geometry set computational-geometry
我想知道一个返回true或false的算法,告诉我是否可以围绕一组点A绘制一个圆,这样点B组中的任何点都不在其中,或者反过来(可能)围绕一组点B绘制圆圈,使得来自点集A的任何点不在其内部).
基本上,你有两组点作为输入,你需要确定是否可以围绕任何一个绘制一个圆,这样另一个点的任何一个点都不在其中.
我已经看过Megiddo的线性时间算法来解决最小的圆周问题,但问题是它只绘制了最小的圆,这意味着它在你需要一个大圆的情况下不起作用.
这是我的意思的图片:
在这张图片中,可以围绕红点集绘制一个非常大的圆圈,这样任何一个绿点都不在其中,因此Megiddo的算法将无法工作.
Jos*_*rke 12
在本文中,我们减少检测平面中的两组点是否可以用圆分隔,以确定3D中点的线性可分离性:
O'Rourke,Joseph,S.Rao Kosaraju和Nimrod Megiddo."计算循环可分性." 离散&计算几何,1 0.1(1986):105-113.(PDF下载.)
- @Jongware Megiddo的算法表明,3d中的线性规划问题可以在线性时间内得到解决.Megiddo还提供了使用找到最小封闭圆的算法的示例.这个例子不是OP想要的.然而,这里的论文显示了一个确实允许Megiddo算法应用的不同公式.(想法是将点投射到抛物面,然后找到一个分离平面.) (5认同)
试试这个:使用立体投影将你的点投射到球体上.然后,您需要找到穿过球体的平面,该球体切割球体,使第一组中的所有点都位于平面的一侧,第二组中的所有点都位于平面的另一侧.平面和球体的交点是一个圆,它在原始平面上映射回一个圆(或在极少数情况下,一条线).原始平面上的结果圆具有您想要的属性.
将问题从一个关于平面上的圆的问题更改为关于三维平面的问题(线性对象)意味着您可以使用来自线性编程和凸集的想法来帮助.一种方法是使用超平面分离定理来表明,当且仅当A和B中的点的图像的凸包不相交时,才能找到分离点族的图像的平面.
硬件和软件中有许多用于确定两个凸体是否相交的快速方法:它是碰撞检测的问题,例如在视频游戏中很重要.关于该问题已经做了很多工作(参见,例如,https://www.medien.ifi.lmu.de/lehre/ss10/ps/Ausarbeitung_Beispiel.pdf,声称该算法在O(n)中运行时间),肯定是免费提供的代码.
总结:通过公式给出的立体投影将点(X,Y)映射到单位球体(x,y,z)上
(x,y,z) = (2*X/(R^2+1), 2*Y/(R^2+1), (R^2-1)/(R^2+1)), R^2 = X^2+Y^2
然后使用Gilbert-Johnson-Keerthi算法或一些其他碰撞检测算法来确定一组中的点的图像的凸包是否与另一组中的点的图像的凸包不相交.这回答了圆是否存在的问题.要实际找到圆,您需要在两个凸体之间存在一个分离平面,然后将其与球体相交以在球体上获得一个圆,然后通过立体投影的倒数将其映射回平面.
如果我理解正确,可以在O(n)时间内完成上述操作.