假设我在笛卡尔平面中有一组点,由 (X,Y) 坐标的数组/向量定义。如果任何一组不连续的点可以连续,则这组点在坐标平面中将是“连续的”。也就是说,这些点起源于一个矩形网格,其中的点区域已被先验算法消除。点所勾勒的形状是任意的,但它的边会趋向于圆弧。
进一步假设我可以创建固定半径 r
的圆。
我想要一种算法,它可以找到一个圆的中心 X,Y
,该圆将尽可能接近给定点的一半。
最佳答案
好的,试试这个(抱歉,如果我的措辞很糟糕:我没有用英语学习我的数学)
第一步:找轴
- 对于所有相距小于2r的点对,计算有多少点位于连接线的两侧
- 选择最差平衡的一对
- 计算将这两个点平分的线作为轴(“最大凹度轴”)
第二步:寻找中心
- 从远离 (>2r) 的一侧的轴开始,在第 1 步(凹侧)中具有较低的点数
- 移动轴上的中心,直到到达所需的点。这可以通过向上移动 sqrt(delta) 的步长来完成,其中 delta 是集合中两点之间的最小距离,如果超出范围则向后移动一半等。
关于使用固定半径的圆二等分一组点的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16640108/