Find points farthest from each other in an array
I have 5 points with coordinates x,y
and I also have a valid offset x,y
. I can apply this offset to each point to move both positively and negatively. This means that there are four possible locations for each point, after all permitted movements have been applied.
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()
The origin points are shown below in black and their 4 possible new positions are colored (same color for 4 offset positions for each point):
I need to find a combination of 5 "new" offset positions for all points so that the sum of the distance between each point and the nearest one will be maximized.
+3
source to share
1 answer
Ok then ... an approximate solution algorithm ...
- Calculate the center of gravity of existing points.
- For each point of the 4 selection, choose one of the farthest from the center of gravity.
- Calculate total distance; this is your first approximation.
- For each point in the set, test the effect of the transition on each of the other three options. If any of these give the best overall distance, move to that position.
- Repeat step 4 until no further changes are made.
+1
source to share