python - 查找数组中彼此最远的点

Question

我有 5 个具有 x,y 坐标的点，我还有一个允许的 x,y 偏移量。我可以将此偏移应用于每个点以将其正向和负向移动。这意味着在应用所有允许的位移后，每个点有四个可能的位置。

import numpy as np
import matplotlib.pyplot as plt

# xy data for 5 points
xy = [[1929.39695287, 1579.6, 1548.0451124, 1561.47793473, 1053.18163361],
      [2020.79329391, 1869.4327316, 1800.71748721, 2112.769, 1840.28]]
xy = zip(*xy)

# Define xy offset
offset = [201.8445, 202.9015]

# Create the 4 possible offset combinations for each of the 5 points
xy_offset = []
for pt in xy:
    xy_offset.append([
        [pt[0] + offset[0], pt[1] + offset[1]],
        [pt[0] + offset[0], pt[1] - offset[1]],
        [pt[0] - offset[0], pt[1] + offset[1]],
        [pt[0] - offset[0], pt[1] - offset[1]]])

plt.scatter(*zip(*xy), c='k')
for xy in xy_offset:
    plt.scatter(*zip(*xy))
plt.show()

原始点在下面以黑色显示，它们的 4 个可能的新位置是彩色的(每个点的 4 个偏移位置颜色相同):

我需要为所有点找到 5 个"new"位移位置的组合，以使每个点与最近点之间的距离之和最大化。

Answer 1

那好吧……近似解算法……

1. 计算现有点的质心。
2. 对于每个点的 4 个选择，选择离质心最远的一个。
3. 计算总距离；这是您的第一个近似值。
4. 对于集合中的每个点，检查移动到其他三个选项中的每一个的效果。如果其中任何一个提供了更好的总距离，请更改到该位置。
5. 重复第 4 步，直到没有进一步的变化。