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

Question

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

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

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

Answer 1

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

第一步:找轴

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

第二步:寻找中心

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