你如何确定是否可以围绕一组点画一个圆圈，这样另一组点不在圆圈内？
How do you determine if you can draw a circle around a set of points, such that the points from the other set aren't inside it?
我想知道一个算法 returns 是真还是假，告诉我是否可以围绕一组点 A 画一个圆，这样点组 B 中的任何点都不在里面它，或者反过来（可以围绕一组点 B 画一个圆圈，这样一组点 A 中的任何点都不在其中）。
基本上，您有 2 组点作为输入，您需要确定是否可以围绕其中一个点画一个圆圈，这样另一个点的任何点都不在其中。
我看过Megiddo's linear time algorithm for the smallest enclosing circle problem，但问题是它只画了最小的圆，这意味着它在你需要大圆的情况下不起作用。
这是我的意思的图片：
在这幅图中，可以在一组红点周围画一个非常大的圆圈，这样任何一个绿点都不在其中，因此 Megiddo 的算法将不起作用。
如果您要测试很多潜在的中心点（例如在网格上），那么对于每个点，到任何红点的最大距离必须小于到任何绿点的最小距离，以便有一个只包含红色点而没有绿色点的圆。
我想通过从稀疏网格开始并监控 "largest distance to any red point"、"smallest distance to any green point" 值，您可以使一些有前途的区域越来越精细（巧妙分割）以最终捕捉到一个点或一个区域与所需的 属性.
您甚至可以使用一些导数，例如进入 "largest distance to any red point" 与 "smallest distance to any green point" 比率下降最快的方向。另一方面，问题可能是非凸的，可能无法保证收敛。
试试这个：使用 stereographic projection 将您的点投影到球体上。然后你需要找到一个通过球体的平面切割球体，使得第一组中的所有点都在平面的一侧，第二组中的所有点都在平面的另一侧。平面和球体的交点是一个圆，它映射回原始平面上的一个圆（或在极少数情况下，一条线）。原始平面上生成的圆具有您想要的属性。
将问题从关于平面上的圆圈的问题更改为关于三维平面（线性对象）的问题意味着您可以使用线性规划和凸集的思想来提供帮助。一种方法是使用 hyperplane separation theorem 来表明当且仅当 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)时间内完成。
在本文中，我们减少检测平面上的两组点是否
可以用圆隔开，对3D点的线性可分性：
O'Rourke, Joseph, S. Rao Kosaraju, and Nimrod Megiddo. "Computing circular separability." Discrete & Computational Geometry, 1.1 (1986): 105-113.
(PDF download.)
只是一个想法：取所有红点和绿点对。
对于每一对，计算正交中心线。
直线上的这些点是到绿点和红点的距离相等的点，所以以此为圆心的圆是没有意义的。
但是红点所在的直线同一侧的区域也是潜在中心点所在的区域。
对于每一对 {red,green}，您将得到一条线和一个区域，圆的中心点就是该区域。
如果您将所有对的所有区域相交，您将获得所有圆的所有潜在中心点。
在你的例子中，把两个绿色和红色的点放在它们之间。您将在垂直轴左右 1/2 处得到两条线。
拿左边的绿点和所有的红点，你会得到从左上到右下的线，圆心在它们上面。
右边的绿色圆点和红色圆点的作用大致相同。所以在这种情况下，你会得到一个结果区域（多边形），它离垂直轴不太远，至少比水平轴高出一定距离，并延伸到无穷远。
对于另一组点，交点可能导致一个空集，这意味着您不能在不包含一些绿色点的情况下围绕红色点绘制这样的圆。
这将始终计算出正确的结果，但我不知道，与 Joseph 的算法相比，性能有多好。也许他可以看看？
我想知道一个算法 returns 是真还是假，告诉我是否可以围绕一组点 A 画一个圆，这样点组 B 中的任何点都不在里面它，或者反过来（可以围绕一组点 B 画一个圆圈，这样一组点 A 中的任何点都不在其中）。
基本上，您有 2 组点作为输入，您需要确定是否可以围绕其中一个点画一个圆圈，这样另一个点的任何点都不在其中。
我看过Megiddo's linear time algorithm for the smallest enclosing circle problem，但问题是它只画了最小的圆，这意味着它在你需要大圆的情况下不起作用。
这是我的意思的图片：
在这幅图中，可以在一组红点周围画一个非常大的圆圈，这样任何一个绿点都不在其中，因此 Megiddo 的算法将不起作用。
如果您要测试很多潜在的中心点（例如在网格上），那么对于每个点，到任何红点的最大距离必须小于到任何绿点的最小距离，以便有一个只包含红色点而没有绿色点的圆。
我想通过从稀疏网格开始并监控 "largest distance to any red point"、"smallest distance to any green point" 值，您可以使一些有前途的区域越来越精细（巧妙分割）以最终捕捉到一个点或一个区域与所需的 属性.
您甚至可以使用一些导数，例如进入 "largest distance to any red point" 与 "smallest distance to any green point" 比率下降最快的方向。另一方面，问题可能是非凸的，可能无法保证收敛。
试试这个：使用 stereographic projection 将您的点投影到球体上。然后你需要找到一个通过球体的平面切割球体，使得第一组中的所有点都在平面的一侧，第二组中的所有点都在平面的另一侧。平面和球体的交点是一个圆，它映射回原始平面上的一个圆（或在极少数情况下，一条线）。原始平面上生成的圆具有您想要的属性。
将问题从关于平面上的圆圈的问题更改为关于三维平面（线性对象）的问题意味着您可以使用线性规划和凸集的思想来提供帮助。一种方法是使用 hyperplane separation theorem 来表明当且仅当 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)时间内完成。
在本文中，我们减少检测平面上的两组点是否 可以用圆隔开，对3D点的线性可分性：
O'Rourke, Joseph, S. Rao Kosaraju, and Nimrod Megiddo. "Computing circular separability." Discrete & Computational Geometry, 1.1 (1986): 105-113. (PDF download.)
只是一个想法：取所有红点和绿点对。
对于每一对，计算正交中心线。
直线上的这些点是到绿点和红点的距离相等的点，所以以此为圆心的圆是没有意义的。
但是红点所在的直线同一侧的区域也是潜在中心点所在的区域。
对于每一对 {red,green}，您将得到一条线和一个区域，圆的中心点就是该区域。
如果您将所有对的所有区域相交，您将获得所有圆的所有潜在中心点。
在你的例子中，把两个绿色和红色的点放在它们之间。您将在垂直轴左右 1/2 处得到两条线。
拿左边的绿点和所有的红点，你会得到从左上到右下的线，圆心在它们上面。
右边的绿色圆点和红色圆点的作用大致相同。所以在这种情况下，你会得到一个结果区域（多边形），它离垂直轴不太远，至少比水平轴高出一定距离，并延伸到无穷远。
对于另一组点，交点可能导致一个空集，这意味着您不能在不包含一些绿色点的情况下围绕红色点绘制这样的圆。
这将始终计算出正确的结果，但我不知道，与 Joseph 的算法相比，性能有多好。也许他可以看看？