Существует много способов взвешивания расстояний для построения многоугольников Тиссена. Основная идея их построения основана на сравнении расстояния между произвольной точкой x и двумя неподвижными точками p и q ; вам нужно решить, является ли x «ближе» к p, чем к q или нет. Для этого - по крайней мере, концептуально - мы рассматриваем расстояния dp = d ( x , p ) и dq = d ( x , q ). Взвешивание обычно происходит двумя способами: точкам могут быть заданы положительные числовые веса wp и wq, а сами расстояния могут быть преобразованы.
Чтобы иметь смысл, преобразование (которое я напишу как f ) должно увеличиваться с увеличением расстояний; то есть f (d ')> f (d) всякий раз, когда d'> d> = 0. Примерами таких преобразований являются f (d) = d + 1, f (d) = d ^ 2 (закон розничной гравитации Рейли ), f (d) = 1 - 1 / d (при условии, что все расстояния меньше 1), f (d) = log (d), f (d) = exp (d) -1.
Тогда мы бы сказали, что x «ближе» к p, чем к q , когда
f (d ( x , p )) / wp <f (d ( x , q )) / wq.
Обратите внимание на деление на веса, а не на умножение: это означает, что большие веса будут стремиться «тянуть» точки на больших расстояниях. Вы увидите это в работающем примере ниже.
Вот прекрасная вещь и весь смысл этого несколько абстрактного изложения: хотя получающиеся области Тиссена могут иметь сложные, чрезвычайно трудные для вычисления границы, их относительно легко вычислить, используя представление на основе сетки. Вот рецепт:
Для каждой входной точки p вычислите ее евклидову сетку расстояний [d (p)].
Используйте Алгебру карт, чтобы применить f и веса, таким образом повторно выражая каждую сетку расстояний как
[fp] = f ([d (p)]) / wp.
Вот пример использования f (d) = 100 + d ^ (3/2); масштаб 400 на 600.
По мере увеличения f (d) значение становится темнее. Очевидно, что расстояние в этом примере соответствует центральной красной точке; остальные четыре точки получают свои расчеты расстояния отдельно (не показаны). Площади точек пропорциональны их весам, которые составляют 2, 10, 3, 4 и 5.
Вычислите локальный минимум всех этих сеток [fp]. Назовите это [f]. Вот пример.
Сравнивая [f] с каждым [fp], каждой ячейке сетки назначают идентификатор первого p, для которого [f]> = [fp]. (Это может быть сделано, например, за один шаг с самой низкой позицией .)
(Я сомневаюсь, что где-нибудь существует алгоритм, который вычислит решение векторного формата для этой весовой функции f.)
Очевидно, что если у вас больше, чем несколько точек p, вы запишете это в сценарий, и если их число исчисляется тысячами, вы, вероятно, откажетесь от этой попытки, поскольку она неосуществима с вычислительной точки зрения (хотя существуют способы ускорить вычисление путем его разбиения).
Другой пример, показывающий полигоны Тиссена на эллипсоиде, можно найти по адресу /gis//a/17377/ .
Вам нужна взвешенная диаграмма Вороного: http://en.wikipedia.org/wiki/Weighted_Voronoi_diagram также известна как круговая тесселяция Дирихле, когда она выполняется с мультипликативными весами в 2-мерной плоскости. Кто-то, кажется, создал расширение Arcgis 9 для их создания: http://arcscripts.esri.com/details.asp?dbid=15481 С руководством пользователя доступно здесь http://geography.unt.edu/~pdong/software .htm и статья, опубликованная в Dong, P., 2008. Создание и обновление мультипликативно взвешенных диаграмм Вороного для точечных, линейных и многоугольных объектов в ГИС. Компьютеры и науки о Земле, том 34, выпуск 4, страницы 411-421.
Для этого есть недавняя статья о векторном алгоритме (я предполагаю, что алгоритм П Донга основан на растре). http://www.sciencedirect.com/science/article/pii/S0098300411003037 Аннотация говорит, что код C # включен.
источник