Улучшение производительности оценки объема Вороного

Question

Мне нужно оценить объемы, связанные с множеством клеток Вороного в многомерном пространстве. Из этого вопроса Объем ячейки Вороного (python) Я проверял этот ответ , и он работает, но он действительно медленный.

В приведенном ниже коде, получив объемы занимают почти 90% времени:

import numpy as np
from scipy.spatial import Voronoi
from scipy.spatial import ConvexHull
import time as t

points = np.random.uniform(0., 100., (5000, 4))

s = t.time()
v = Voronoi(points)
print(t.time() - s)

s = t.time()
vol = np.zeros(v.npoints)
for i, reg_num in enumerate(v.point_region):
    indices = v.regions[reg_num]
    if -1 in indices:  # non-closed regions
        vol[i] = np.inf
    else:
        vol[i] = ConvexHull(v.vertices[indices]).volume
print(t.time() - s)

Эти 90% почти полностью используются звонками на scipy.spatial.ConvexHull.

Может ли это быть улучшилось в любом случае?

Answer 1

Вызов scipy.spatial.ConvexHull создает много накладных расходов. При вызове атрибута volume объект должен сначала определиться со своими внешними точками, которые по сути являются наименьшей окружностью вокруг всех пройденных точек (в данном случае). Следовательно, использование функции, которая вычисляет площадь поверхности многоугольника по n точкам, должно быть достаточным. См. Площадь выпуклого многоугольника для реализации такой функции в предположении, что клетки вороной выпуклые (что обычно имеет место.)

См. this StackOverflow ответ для Python специфицированной c реализации.