Algorithm to spread / declutter points in 1 dimension (on a line)

Small general-purpose mathematical-optimization based demo:

• LP/QP might differ as penalties are weighted differently!
• cvxpy does give us the necessary linearizations / reformulations for free (e.g. abs)

import cvxpy as cp
import numpy as np
import matplotlib.pyplot as plt

points = np.array([3, 4, 10, 13, 14, 15]) 
min_distance = 2

def solve(quadratic):
  # vars
  x = cp.Variable(points.shape[0])

  # constraints
  constrs = [x[i] - x[i-1] >= min_distance for i in range(1, points.shape[0])]

  # objective
  if not quadratic:
    obj = cp.Minimize(sum(cp.abs(x - points)))
  else:
    obj = cp.Minimize(cp.sum_squares(x - points))

  # setup problem + solve
  problem = cp.Problem(obj, constrs)
  problem.solve()

  return x.value

linear_sol = solve(False)
quad_sol = solve(True)

# visualize
f, (ax0, ax1, ax2) = plt.subplots(3, sharex=True)

colors = [plt.cm.tab10(i) for i in range(points.shape[0])]

ax0.set_title('Input data')
ax1.set_title('linear / abs | LP')
ax2.set_title('quadratic / sum-squares | QP')

for ind, _ in enumerate(points):
  ax0.axvline(points[ind], color=colors[ind])
  ax1.axvline(linear_sol[ind], color=colors[ind])
  ax2.axvline(quad_sol[ind], color=colors[ind])

f.suptitle("Min distance = {}".format(min_distance))
plt.show()

which behaves like:

Here is a possible algorithm.

• Classify every distance between adjacent points as either Large or small. On your example image, we get L,s,L,L,s,s,s,L.
• Note how every Large distance separates two clusters of points.
• Replace every small distance by the "minimal fixed distance" you want.
• Decrease every large distance by half the total distance that was added to the cluster on its left and half the total distance that was added to the cluster on its right.

The algorithm takes two parameters: the minimal_distance wanted between adjacent points, and a threshold to differentiate between large distances and small distances.

Implementation in python

import itertools  # groupby, accumulate

points = [0, 5, 6, 11, 16, 17, 18, 19, 24]

def get_distances(points):
  return [(b-a) for a,b in zip(points, points[1:])]

def group_by_large_or_small(distances, threshold):
  return itertools.groupby(distances, key=lambda d: (d > threshold))

def spread_cluster(cluster, minimal_distance):
  added_distance = 0
  new_cluster = []
  for d in cluster:
    new_cluster.append(max(d, minimal_distance))
    added_distance += (d - new_cluster[-1])
  return new_cluster, added_distance

def increase_small_distances(grouped_distances, minimal_distance):
  new_groups = []
  for k,g in grouped_distances:
    if k:
      new_groups.append((k, list(g), 0))
    else:
      new_cluster, added_distance = spread_cluster(g, minimal_distance)
      new_groups.append((k, new_cluster, added_distance))
  return new_groups

def decrease_large_distances(grouped_distances):
  distances = []
  for i, (k, g, a) in enumerate(grouped_distances):
    if k:
      g[0] += grouped_distances[i-1][2] / 2 if (i > 0 and not grouped_distances[i-1][0]) else 0
      g[-1] += grouped_distances[i+1][2] / 2 if (i+1 < len(grouped_distances) and not grouped_distances[i+1][0]) else 0
    distances.extend(g)
  return distances

def get_points(distances):
  return list(itertools.accumulate(distances, initial=0))

def spread_points(points, threshold, minimal_distance):
  distances = get_distances(points)
  grouped_distances = group_by_large_or_small(distances, threshold)
  grouped_distances = increase_small_distances(grouped_distances, minimal_distance)
  distances = decrease_large_distances(grouped_distances)
  return get_points(distances)

import matplotlib.pyplot as plt

points = [0, 5, 6, 11, 16, 17, 18, 19, 24]
new_points = spread_points(points, 3, 1.6)

plt.scatter(points, [2 for _ in points])
plt.scatter(new_points, [1 for _ in points])
plt.show()

Output