iphone - 数组中两点之间的最大距离

Question

假设我有一个带有 CGPoints 的数组（用NSValues包装）。我怎样才能得到彼此最远的两个点。我的意思是这两点之间的距离最大？我可以每两点检查一次，但这看起来效率不高。有没有更好的方法来做到这一点？

感谢帮助！

Answer 1

如果没有太多点（最多 1000，但如果是密集的，大约 100），请使用朴素的蛮力方法 O(n ² )。

我还没有阅读详细信息，但最大距离可能可以用凸包算法+旋转卡尺在 O(nlog n) 中计算。