python - 将点移动到最近的未占用网格位置

Question

我在 2D 空间中有一个随机分布的点，如下所示:

from sklearn import datasets
import pandas as pd
import numpy as np

arr, labels = datasets.make_moons()
arr, labels = datasets.make_blobs(n_samples=1000, centers=3)
pd.DataFrame(arr, columns=['x', 'y']).plot.scatter('x', 'y', s=1)

我试图将这些点中的每一个分配到假想的六角网格上最近的未占用插槽，以确保这些点不会重叠。我用来实现此目标的代码生成了下面的图。总体思路是创建十六进制容器，然后迭代每个点并找到允许算法将该点分配给未占用的十六进制容器的最小半径:

from scipy.spatial.distance import euclidean

def get_bounds(arr):
  '''Given a 2D array return the y_min, y_max, x_min, x_max'''
  return [
    np.min(arr[:,1]),
    np.max(arr[:,1]),
    np.min(arr[:,0]),
    np.max(arr[:,0]),
  ]

def create_mesh(arr, h=100, w=100):
  '''arr is a 2d array; h=number of vertical divisions; w=number of horizontal divisions'''
  print(' * creating mesh with size', h, w)
  bounds = get_bounds(arr)
  # create array of valid positions
  y_vals = np.arange(bounds[0], bounds[1], (bounds[1]-bounds[0])/h)
  x_vals = np.arange(bounds[2], bounds[3], (bounds[3]-bounds[2])/w)
  # create the dense mesh
  data = np.tile(
    [[0, 1], [1, 0]],
    np.array([
      int(np.ceil(len(y_vals) / 2)),
      int(np.ceil(len(x_vals) / 2)),
    ]))
  # ensure each axis has an even number of slots
  if len(y_vals) % 2 != 0 or len(x_vals) % 2 != 0:
    data = data[0:len(y_vals), 0:len(x_vals)]
  return pd.DataFrame(data, index=y_vals, columns=x_vals)


def align_points_to_grid(arr, h=100, w=100, verbose=False):
  '''arr is a 2d array; h=number of vertical divisions; w=number of horizontal divisions'''
  h = w = len(arr)/10
  grid = create_mesh(arr, h=h, w=w)

  # fill the mesh
  print(' * filling mesh')
  df = pd.DataFrame(arr, columns=['x', 'y'])
  bounds = get_bounds(arr)
  # store the number of points slotted
  c = 0
  for site, point in df[['x', 'y']].iterrows():
    # skip points not in original points domain
    if point.y < bounds[0] or point.y > bounds[1] or \
       point.x < bounds[2] or point.x > bounds[3]:
      raise Exception('Input point is out of bounds', point.x, point.y, bounds)

    # assign this point to the nearest open slot
    r_y = (bounds[1]-bounds[0])/h
    r_x = (bounds[3]-bounds[2])/w
    slotted = False
    while not slotted:

      bottom = grid.index.searchsorted(point.y - r_y)
      top = grid.index.searchsorted(point.y + r_y, side='right')
      left = grid.columns.searchsorted(point.x - r_x)
      right = grid.columns.searchsorted(point.x + r_x, side='right')
      close_grid_points = grid.iloc[bottom:top, left:right]

      # store the position in this point's radius that minimizes distortion
      best_dist = np.inf
      grid_loc = [np.nan, np.nan]
      for x, col in close_grid_points.iterrows():
        for y, val in col.items():
          if val != 1: continue
          dist = euclidean(point, (x,y))
          if dist < best_dist:
            best_dist = dist
            grid_loc = [x,y]

      # no open slots were found so increase the search radius
      if np.isnan(grid_loc[0]):
        r_y *= 2
        r_x *= 2
      # success! report the slotted position to the user
      else:
        # assign a value other than 1 to mark this slot as filled
        grid.loc[grid_loc[0], grid_loc[1]] = 2
        df.loc[site, ['x', 'y']] = grid_loc
        slotted = True
        c += 1

        if verbose:
          print(' * completed', c, 'of', len(arr), 'assignments')
  return df


# plot sample data
df = align_points_to_grid(arr, verbose=False)
df.plot.scatter('x', 'y', s=1)

我对此算法的结果感到满意，但对性能不满意。

Python 中这种 hexbin 赋值问题有更快的解决方案吗？我感觉其他人更多地接触了Linear Assignment Problem或Hungarian Algorithm可能对这个问题有宝贵的见解。任何建议都会非常有帮助!

Answer 1

事实证明，将每个点分配到其当前半径内的第一个可用网格点的性能足够好。

对于最终到达这里的其他人，我的实验室将此功能封装成一个小 Python package为了方便。您可以pip install pointgrid然后:

from pointgrid import align_points_to_grid
from sklearn import datasets

# create fake data
arr, labels = datasets.make_blobs(n_samples=1000, centers=5)

# get updated point positions
updated = align_points_to_grid(arr)

updated 将是一个与输入数组 arr 形状相同的 numpy 数组。