Вороной Тесселяция в Python - PullRequest
Новая
       29

Вороной Тесселяция в Python

6 голосов
/ 29 ноября 2011

Проблема с назначением узлов

enter image description here

Проблема, которую я хочу решить, состоит в том, чтобы создать тесселяцию карты, заданной синими узлами (исходными узлами), в качестве заданных точек ввода, как только я смогудля этого я хотел бы увидеть, сколько черных узлов (узлов спроса) попадает в каждую ячейку, и назначить их синему узлу, связанному с этой ячейкой.

Я хотел бы знать, существует ли более простой способДелая это, не используя алгоритм Fortune. Я столкнулся с этой функцией под названием Mahotas Mahotas.segmentation.gvoronoi (image) source .Но я не уверен, решит ли это мою проблему.

Также, пожалуйста, предложите мне, если есть лучший способ сделать эту сегментацию (кроме тесселяции Вороного).Я не уверен, что алгоритмы кластеризации будут хорошим выбором.Я новичок в программировании.

Ответы [ 6 ]

7 голосов
/ 29 ноября 2011

Вот альтернативный подход к использованию тесселяции Вороного:

Построение дерева kd над исходными узлами.Затем для каждого узла спроса используйте дерево kd, чтобы найти ближайший исходный узел, и увеличьте счетчик, связанный с этим соседним узлом источника.

Реализация дерева kd, найденного в http://code.google.com/p/python-kdtree/, должна быть полезной.

2 голосов
/ 10 июля 2012

Я только что искал ту же вещь и нашел это:

https://github.com/Softbass/py_geo_voronoi

1 голос
/ 27 декабря 2011

Я думаю, что ответ пространственного индекса на https://stackoverflow.com/users/1062447/wye-bee (например, kd-дерево) - самое простое решение вашей проблемы.

Кроме того, вы также спросили, есть ли более простая альтернатива алгоритму Фортуны, и на этот конкретный вопрос я отсылаю вас: Самый простой алгоритм реализации диаграммы Вороного?

1 голос
/ 30 ноября 2011

Запустите этот код в Mathematica.Это впечатляюще!(Да, я знаю, что это не Python, но ...) 

pts3 = RandomReal[1, {50, 3}];
ListDensityPlot[pts3, 
    InterpolationOrder -> 0, ColorFunction -> "SouthwestColors", Mesh -> All]

Voronoi Diagram

1 голос
/ 30 ноября 2011

На вашей диаграмме не так много точек. Это говорит о том, что для каждого узла спроса можно просто выполнить итерацию по всем исходным узлам и найти ближайший.

Возможно, это: 

def distance(a, b):
    return sum((xa - xb) ** 2 for (xa, xb) in zip(a, b))

def clusters(sources, demands):
    result = dict((source, []) for source in sources)
    for demand in demands:
        nearest = min(sources, key=lambda s: distance(s, demand))
        result[nearest].append(demand)
    return result

Этот код даст вам словарь, отображающий исходные узлы в список всех узлов спроса, которые находятся ближе к этому исходному узлу, чем любой другой.

Это не особенно эффективно, но очень просто!

0 голосов
/ 25 июня 2015

Вы не сказали, почему хотели избежать алгоритма Фортуны.Я предполагаю, что вы имели в виду, что вы просто не хотели реализовывать это самостоятельно, но это уже было реализовано в сценарии Биллом Саймонсом и Карстоном Фармером, поэтому вычисление диаграммы вороного не должно быть сложным.

Опираясь на их скрипт, я сделал его еще проще и загрузил его в PyPi под именем Pytess .Таким образом, вы можете использовать функцию pytess.voronoi (), основанную на синих точках, в качестве входных данных, возвращая исходные точки с их вычисленными полигонами вороной.Затем вам нужно будет назначить каждую черную точку с помощью тестирования точки в полигоне, которое вы можете основать на http://geospatialpython.com/2011/08/point-in-polygon-2-on-line.html.

enter image description here

...