algorithm - 使用固定半径圆平分一组点的算法

Question

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

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

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

Answer 1

您可能想研究点集的最小封闭圆的算法。

一个有点贪心的算法是一次简单地删除点 1，直到圆半径小于或等于 r。

Answer 2

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

第 1 步：查找轴

• 对于相距小于 2r的所有点对，计算有多少点位于连接线的两侧
• 选择平衡最差的一对
• 计算将这两个点平分为轴的线（“最大凹度轴”）

第 2 步：找到中心

• 从远离 (>2r) 一侧的轴开始，在第 1 步中具有较低点数的一侧（凹侧）
• 移动轴上的中心，直到到达所需的点。这可以通过以 sqrt(delta) 的步长向上移动来完成，其中 delta 是集合中 2 个点之间的最小距离，如果超出，则向后移动半步等。