使用固定半径的圆二等分一组点的算法

假设我在笛卡尔平面中有一组点，由 (X,Y) 坐标的数组/向量定义。如果任何一组不连续点可以是连续的，那么这组点在坐标平面中将是“连续的”。也就是说，这些点起源于一个矩形网格，其中的点区域被先验算法消除。点勾勒出的形状是任意的，但它的边缘往往会有弧线。

进一步假设我可以创建固定半径的圆 r 。

我想要一个算法，它可以为我找到一个圆的中心 X,Y，该圆将尽可能接近给定点的一半。

最佳答案

好的，试试这个(对不起，如果我的措辞很糟糕:我没有用英语学习我的数学)

第 1 步:查找轴

对于所有相距小于 2r 的点， 计算位于连接线两侧的点数

选择具有 最差 平衡的货币对

计算将这两个点作为轴(“最大凹度的轴”)一分为二的线

第 2 步:查找中心

从远离 (>2r) 的一侧开始，在步骤 1 中点数较低(凹侧)

移动轴的中心，直到到达所需的点。这可以通过向上移动 sqrt(delta) 的步骤来完成，其中 delta 是集合中两点之间的最小距离，如果超出则向后移动一半的步骤等。

关于使用固定半径的圆二等分一组点的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16640108/