在一维（在线）中传播/整理点的算法

Question

是否有非迭代算法来展开/整理线上的点？

示例：

上线：初始情况。下线：点数已分散。

约束条件：

我更愿意有一个解决方案，而不是基于微调点直到它们稳定下来。换句话说，我更喜欢一种算法，例如，求解一组方程，从而“一次性”计算所有点的新位置。
这是一个一维的情况。
生成的点应该尽可能靠近它们的初始位置，但与其相邻点保持一些最小的固定距离。虽然近似值很好。

Answer 1

这是一个可能的算法。

将相邻点之间的每个距离分类为 Large 或 small。在您的示例图片上，我们得到 L,s,L,L,s,s,s,L.
请注意每个 Large 距离如何将两个点群分开。
用你想要的“最小固定距离”替换每个小距离。
将每个大距离减少添加到其左侧集群的总距离的一半和添加到其右侧集群的总距离的一半。

该算法采用两个参数：相邻点之间的 minimal_distance 和区分大距离和小距离的 threshold。

在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()

输出

Answer 2

基于小型通用数学优化的演示：

LP/QP 可能会有所不同，因为处罚的权重不同！
cvxpy 确实免费为我们提供了必要的线性化/重构（例如 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()

其行为类似于：

在一维（在线）中传播/整理点的算法

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

algorithm

line

mathematical-optimization

point

在python

输出