在我的程序中，我有一些要点。为了进行重新缩放，我正在搜索距离最远的两个节点，然后计算一个乘以所有坐标的因数，以使最大距离等于我定义的某个预定义坐标。
我用来查找最远的两个点的算法，但是对于大的点集是有问题的O(n^2)。伪代码（已计算的距离被跳过）：
O(n^2)
for each point in points: for each other point in points: if distance between point and other point > max max = distance between point and other point
有更快的东西吗？
如果您只需要比例尺而不是精确点，则可以在O（n）时间内执行此操作，并具有一定的误差余量。考虑制作边界框的简单情况。从所有点计算最小x值，最大x，最小y和最大y。这四个数字为您提供了一个最大的包围点，最大误差为1-（1 / sqrt（2））约30％。您可以通过为正方形添加更多边来减少这种情况。考虑一个八边形的情况。要计算另一侧的最小值和最大值，必须旋转坐标系。
错误与运行时间的关系如下所示。
形状-运行时间-最大误差
这是我想出的最大误差的方程式。
angle = 180 / sides max_error = (1 / cos angle) - cos angle
让我知道是否应该添加一个说明图。
