3

I have 5 points with x,y coordinates and I also have an allowed x,y offset. I can apply this offset to each point to move it both positively and negatively. This means that there are four possible locations for each point, after applying all allowed displacements.

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 original points are shown below in black, with their 4 possible new positions colored (same color for the 4 offset positions for each point):

enter image description here

I need to find the combination of the 5 "new" displaced positions for all points, such that the sum of the distance between each point and the closest one is maximized.

Gabriel
  • 40,504
  • 73
  • 230
  • 404
  • 1
    First of all, how do you define "they are located as far from each other as possible"? Do you want to maximise the sum of the distances? – Alex Hall Apr 06 '17 at 16:10
  • 1
    Anyway, to get the distance between each pair of points, use `itertools.combinations(xy, 2)`. Then add two more nested loops for the offsets. – Alex Hall Apr 06 '17 at 16:18
  • Sorry @AlexHall, you are right, I should have been more precise about what I mean by "farthest distance"; I'll fix that. Your definition (max sum of individual distances) is valid one, so I could use that. – Gabriel Apr 06 '17 at 16:56
  • 1
    Is the problem limited to the 5 points, or are you trying to generalize a fast solution for many points? If it's just 5, then you can use the simple brute-force method @Alex already outlined: 10 distances for each of 4^5 (1024) permutations won't take long. If your population can grow larger, such that you need heuristic ways to prune the search, then you're looking for an algorithm (and probably need to be on MathExchange.com, not here). – Prune Apr 06 '17 at 17:01
  • It's not just limited to 5, but I don't expect it to grow larger than ~30 points. – Gabriel Apr 06 '17 at 17:02
  • 1
    Scratch "two more nested loops for the offsets", that was the wrong idea. @Prune is right that a brute force solution is exponential. 4^30 is way too much. I'd be surprised if there's a plausible provably exact solution. What about an approximate solution, i.e. one that's right or almost right most of the time? I'm thinking a hill-climbing algorithm would work well here. – Alex Hall Apr 06 '17 at 21:29
  • I'm open to approximate solutions. I actually wanted to solve this issue as an approach to a semi-smart [text positioning for scatter plots](http://stackoverflow.com/a/14434334/1391441) (the idea being that the annotated text should not overlap either the scatter points or each other). After seeing that it was substantially more complicated than I expected, I went with a simpler approach. I'd still be interested in seeing how this problem can be tackled though. – Gabriel Apr 06 '17 at 21:38

1 Answers1

1

Okay then ... approximate solution algorithm ...

  1. Compute the centroid of the existing points.
  2. For each point's 4 choices, choose the one farthest from the centroid.
  3. Compute the total distance; this is your first approximation.
  4. For each point in the set, check the effect of moving to each of the other three choices. If any of those gives a better total distance, change to that position.
  5. Repeat step 4 until there are no further changes.
Prune
  • 76,765
  • 14
  • 60
  • 81