约束 Qhull 生成的 Voronoi 顶点的域

简而言之，我的问题是：是否可以约束 Qhull 生成的 Voronoi 顶点的域？如果是的话，怎样才能做到这一点呢？

我的上下文问题：我正在研究数据可视化，其中我在 2D 字段中有点。这些点有一点重叠，所以我稍微“抖动”它们，以使它们不重叠。

我目前执行此任务的方法是使用劳埃德算法 https://en.wikipedia.org/wiki/Lloyd%27s_algorithm移动点。劳埃德算法本质上采用初始点位置，计算 Voronoi 图，并在算法的每次迭代期间将每个点移动到其 Voronoi 区域的中心。

下面是一个 Python 示例：

from scipy.spatial import Voronoi
from scipy.spatial import voronoi_plot_2d
import matplotlib.pyplot as plt
import numpy as np
import sys

class Field():
  '''
  Create a Voronoi map that can be used to run Lloyd relaxation on an array of 2D points.
  For background, see: https://en.wikipedia.org/wiki/Lloyd%27s_algorithm
  '''

  def __init__(self, arr):
    '''
    Store the points and bounding box of the points to which Lloyd relaxation will be applied
    @param [arr] arr: a numpy array with shape n, 2, where n is number of points
    '''
    if not len(arr):
      raise Exception('please provide a numpy array with shape n,2')

    x = arr[:, 0]
    y = arr[:, 0]
    self.bounding_box = [min(x), max(x), min(y), max(y)]
    self.points = arr
    self.build_voronoi()

  def build_voronoi(self):
    '''
    Build a Voronoi map from self.points. For background on self.voronoi attrs, see:
    https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.spatial.Voronoi.html
    '''
    eps = sys.float_info.epsilon
    self.voronoi = Voronoi(self.points)
    self.filtered_regions = [] # list of regions with vertices inside Voronoi map
    for region in self.voronoi.regions:
      inside_map = True    # is this region inside the Voronoi map?
      for index in region: # index = the idx of a vertex in the current region

          # check if index is inside Voronoi map (indices == -1 are outside map)
          if index == -1:
            inside_map = False
            break

          # check if the current coordinate is in the Voronoi map's bounding box
          else:
            coords = self.voronoi.vertices[index]
            if not (self.bounding_box[0] - eps <= coords[0] and
                    self.bounding_box[1] + eps >= coords[0] and
                    self.bounding_box[2] - eps <= coords[1] and
                    self.bounding_box[3] + eps >= coords[1]):
              inside_map = False
              break

      # store hte region if it has vertices and is inside Voronoi map
      if region != [] and inside_map:
        self.filtered_regions.append(region)

  def find_centroid(self, vertices):
    '''
    Find the centroid of a Voroni region described by `vertices`, and return a
    np array with the x and y coords of that centroid.

    The equation for the method used here to find the centroid of a 2D polygon
    is given here: https://en.wikipedia.org/wiki/Centroid#Of_a_polygon

    @params: np.array `vertices` a numpy array with shape n,2
    @returns np.array a numpy array that defines the x, y coords
      of the centroid described by `vertices`
    '''
    area = 0
    centroid_x = 0
    centroid_y = 0
    for i in range(len(vertices)-1):
      step = (vertices[i, 0] * vertices[i+1, 1]) - (vertices[i+1, 0] * vertices[i, 1])
      area += step
      centroid_x += (vertices[i, 0] + vertices[i+1, 0]) * step
      centroid_y += (vertices[i, 1] + vertices[i+1, 1]) * step
    area /= 2
    centroid_x = (1.0/(6.0*area)) * centroid_x
    centroid_y = (1.0/(6.0*area)) * centroid_y
    return np.array([centroid_x, centroid_y])

  def relax(self):
    '''
    Moves each point to the centroid of its cell in the Voronoi map to "relax"
    the points (i.e. jitter them so as to spread them out within the space).
    '''
    centroids = []
    for region in self.filtered_regions:
      vertices = self.voronoi.vertices[region + [region[0]], :]
      centroid = self.find_centroid(vertices) # get the centroid of these verts
      centroids.append(list(centroid))

    self.points = centroids # store the centroids as the new point positions
    self.build_voronoi() # rebuild the voronoi map given new point positions

##
# Visualize
##

# built a Voronoi diagram that we can use to run lloyd relaxation
field = Field(points)

# plot the points with no relaxation relaxation
plt = voronoi_plot_2d(field.voronoi, show_vertices=False, line_colors='orange', line_alpha=0.6, point_size=2)
plt.show()

# relax the points several times, and show the result of each relaxation
for i in range(6): 
  field.relax() # the .relax() method performs lloyd relaxation
  plt = voronoi_plot_2d(field.voronoi, show_vertices=False, line_colors='orange', line_alpha=0.6, point_size=2)
  plt.show()

正如我们所看到的，在每次迭代期间（第 2 帧和第 3 帧），原始数据集中的点（第 1 帧，顶部）重叠越来越少，这很棒！

这种方法的问题是我目前正在从图中删除那些 voronoi 区域边界超出初始数据集域的点。 （如果我不这样做，最外面的点很快就会射入超空间并远离其他点。）这最终意味着我最终会丢弃点，这不好。

我认为我可以通过约束 Qhull Voronoi 域来解决这个问题，以便仅在原始数据域内创建 Voronoi 顶点。

可以这样约束Qhull吗？其他人可以提供的任何帮助将不胜感激！

Update

在收到@tfinniga 的出色回复后，我整理了一个博客文章 https://douglasduhaime.com/posts/lloyd-iteration.html详细介绍了有界和无界形式的劳埃德迭代。我还整理了一个小包lloyd https://github.com/duhaime/lloyd以便更轻松地在数据集上运行有界 Lloyd 迭代。我想分享这些资源，以防它们帮助其他人进行相关分析。

您遇到的核心问题是劳埃德算法没有任何限制，因此点会爆炸。有两种方法可以解决此问题：

1. 获取您获得的 voronoi 图，并在计算质心之前手动将其剪切到边界矩形。这将为您提供正确的解决方案 - 您可以根据维基百科文章中链接的示例对其进行测试，并确保其匹配。

2. 添加点的人工边界。例如，您可以在边界框的 4 个角处添加点，或者在每侧添加一些点，但不要移动这些点。这些将阻止内部点爆炸。这不会为您提供劳埃德算法的“正确”结果，但可能会为您提供对可视化有用的输出，并且更容易实现。