Короче, мой вопрос: возможно ли ограничить область вершин Вороного, порожденных Qhull?Если да, то как можно это сделать?
Мой вопрос с контекстом: я работаю над визуализацией данных, в которой у меня есть точки в 2D-поле.Точки немного перекрывают друг друга, поэтому я слегка «дрожу» их, чтобы они не перекрывались.
Мой текущий подход к этой задаче - использовать алгоритм Ллойда для перемещения точек,Алгоритм Ллойда, по сути, берет начальные точки, вычисляет карту Вороного и перемещает каждую точку в центр области Вороного во время каждой итерации алгоритма.
Вот пример на 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, вверху) перекрываются все меньше и меньше, что здорово!
Проблема этого подхода заключается в том, что в настоящее время я удаляю из графика те точки, границы областей вороной которых лежат за пределами области начального набора данных.(Если я этого не сделаю, крайние точки быстро вылетят в гиперпространство и отойдут очень далеко от остальных точек.) В конечном итоге это означает, что я в итоге отбрасываю точки, что не годится.
IЯ подумал, что смогу решить эту проблему, ограничив область Qhull Voronoi так, чтобы создавать вершины Voronoi только в исходной области данных.
Можно ли таким образом ограничить Qhull?Буду очень признателен за любую помощь, которую могут предложить другие!
Обновление
После получения отличного ответа @ tfinniga я собрал сообщение в блоге , подробно описывающее итерацию Ллойда в ее ограниченном виде.и неограниченные формы.Я также собрал небольшой пакет lloyd , чтобы упростить запуск ограниченных итераций Ллойда в наборе данных.Я хотел бы поделиться этими ресурсами на случай, если они помогут другим в проведении соответствующего анализа.