Как вычислить тесселяцию Вороного на основе манхэттенского расстояния в R

Я пытаюсь вычислить тесселяцию Вороного в 2D с расстоянием Манхэттен в R.

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

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


r distance geometry computational-geometry voronoi
person Tom    schedule 23.07.2015    source источник
comment
для ясности - findFn('voronoi') дает ТОННУ результатов, но ни один из них не работает с манхэттенским расстоянием.   -  person Tom    schedule 23.07.2015

Ответы (2)


arrow_upward
4
arrow_downward

Информация: taxicabgeometry.net

Интерактивный: Манхэттен-метрическая диаграмма Вороного (версия для клика)

Я катал свой собственный на python и могу подвести итог здесь: между соседними центроидами находится перпендикулярная линия в манхэттенской метрике - два луча и диагональ 45 градусов, скорее всего, если центроиды генерируются случайным образом, но также может встречаться прямая горизонтальная, вертикальная или диагональная линия под 45 градусов. Учитывая набор таких линий для каждой пары центроидов, ребра, разделяющие области, находятся среди них. Соберите точки пересечения каждой пары линий, которые находятся на равном расстоянии (в пределах эпсилона) в манхэттенской метрике до трех ближайших центроидов. Также соберите две средние точки диагонали 45 градусов, которые одинаково удалены от своих ближайших двух центроидов. Внешние политики не будут закрыты. Как с ними бороться, зависит от того, что вам нужно. Границы полигонов и вершины границ потребуют сортировки, чтобы ваши полигоны не были беспорядочными зигзагами. Порядок намотки можно определить по часовой стрелке или по другому. Можно сделать больше, все зависит от того, что вам нужно.

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

В любом случае, метод грубой силы действительно работает: введите описание изображения здесь

Точка возле курсора - это на самом деле 2 точки крошечной диагонали. Это точный метод, но более сложный, чем может показаться на первый взгляд. Код Java из интерактивной ссылки выше может быть быстрее, но из него трудно получить твердую и точную геометрию.

Извините, я не знаю Р.

person Chronocide    schedule 25.07.2015
comment
Код Java ужасен: /. Десятки фальшивых переменных экземпляра, причудливые переопределения таких функций, как Math.abs и Math.pow, отличные монолитные фрагменты кода, мертвый и / или бесполезный код и переменные повсюду ... На случай, если это кому-то пригодится, у меня есть немного более аккуратная версия кода по адресу gist.github.com/phlummox/95dfc36f500e33f2 / a> edit: Да, и метод для манхэттенского расстояния помечен как евклидово расстояние. jfc. - person phlummox; 10.12.2018

arrow_upward
0
arrow_downward

Может быть, вопрос в том, чтобы найти максимальную площадь квадрата, который соответствует описанной окружности (треугольника). Уравнение для такого квадрата abs (x) + abs (y) = r (www.mat Mathematische-basteleien.de/taxicabgeometry.htm). Когда у вас есть сетка из треугольников, диаграмма Вороного двойственная.

person Gigamegs    schedule 17.08.2015