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

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

введите здесь описание изображения

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

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

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


python algorithm computational-geometry voronoi operations-research
person user1071530    schedule 29.11.2011    source источник
comment
по поводу вашего первого вопроса (о Mahotas.segmentation.gvoronoi): пробовали? Каковы были результаты?   -  person bpgergo    schedule 29.11.2011
comment
Это функция обработки изображения. Я попытался выполнить тессалат без DN (черных узлов) и присвоил исходному узлу несколько цветов (вместо синего). Я получил сегментацию, аналогичную этой ссылке   -  person user1071530    schedule 29.11.2011
comment
Этот сайт назначает узлы: vpartition.meteor.com   -  person FullStack    schedule 17.08.2015

Ответы (6)


arrow_upward
8
arrow_downward

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

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

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

person wye.bee    schedule 29.11.2011
comment
Спасибо! Я рассмотрю этот метод. - person user1071530; 29.11.2011
comment
вы также можете использовать kdtree в SciPy (scipy.spatial.kdtree) - person Jason Sundram; 30.11.2011
comment
@ wye.bee Я использовал предложенный вами метод дерева kd, и он помог мне решить эту проблему и другие ее случаи. Несмотря на то, что я вижу использование этого алгоритма, я не могу интуитивно понять, как он работает. Порекомендуете ли вы какие-либо книги или учебные пособия, которые могут помочь. - person user1071530; 06.12.2011
comment
Википедия — хорошее место для начала (обратите внимание, что внизу есть дополнительные ссылки на соответствующие материалы). en.wikipedia.org/wiki/K-d_tree - person Tim Gee; 27.12.2011

arrow_upward
2
arrow_downward

Я просто искал то же самое и нашел это:

https://github.com/Softbass/py_geo_voronoi

person Malcolm Murdoch    schedule 10.07.2012

arrow_upward
1
arrow_downward

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

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

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

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

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

person Community    schedule 29.11.2011
comment
Спасибо, Пол, но это всего лишь небольшой экземпляр, и я также буду работать над более крупными экземплярами. - person user1071530; 30.11.2011

arrow_upward
1
arrow_downward

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

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

person Tim Gee    schedule 27.12.2011

arrow_upward
0
arrow_downward

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

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

Диаграмма Вороного

person Joseph O'Rourke    schedule 30.11.2011

arrow_upward
0
arrow_downward

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

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

введите здесь описание изображения

person Karim Bahgat    schedule 25.06.2015