Полигоны Тиссена

10. Точечные распределения могут также характеризоваться с помощью полигонов Тиссена (Thiessen polygons) (называемых также диаграммами Дирихле (Dirichlet diagrams) и диаграммами Вороного (Voronoi diagrams)). Они основаны на идее, что мы можем нарастить полигоны вокруг точек, чтобы показать их возможные зоны влияния на другие точки покрытия. Например, как мы увидим при работе с моделью гравитации, можно считать, что между точками действуют силы притяжения.

11. Вдобавок, размер точки - например, города - часто напрямую связан с силой такого влияния. Мы ограничимся случаем равной величины всех точек, что упрощает описание.

12. 284 Глава 11

13. Создание полигонов Тиссена довольно просто концептуально, но может стать запутанным, если количество точек велико. Чтобы понять, как их строить, давайте вначале разберемся, что эти фигуры должны представлять. Если у нас есть несколько точечных объектов, таких как города (опять же, одного размера), мы можем представить себе, что каждая точка окружена одиночным неправильным многоугольником. Но многоугольник имеет одно важное свойство - любая точка внутри него находится ближе к очерченной точке, чем любая другая точка покрытия. И наоборот, каждая точка вне полигона ближе к некоторой иной, нежели к очерченной. Другими словами, граница каждого полигона дает окружаемой точке наименьшую возможную область влияния. Каждая точка покрытия будет иметь свой собственный полигон Тиссена, показывающий область исключительно ее влияния [Clarke, 1990]. Теперь давайте подумаем, как мы могли бы сделать это.

14. Возьмем простой набор точек (Рисунок 11.3). Образование полигонов Тиссена можно представить как результат роста мыльных пузырей с центром в каждой из точек. В конце концов границы пузырей превращаются в прямые линии, а сами пузыри - в многоугольники. Стороны этих многоугольников ориентированы перпендикулярно линиям, соединяющим соседние точки. Причем длины двух отрезков, получившихся с обеих сторон границы, одинаковы.

15.

16. Рисунок 11.3. Создание полигонов Тиссена. а) расположение точек; b) построение связанных с ними полигонов Тиссена.

17. Алгоритмы создания полигонов Тиссена разрабатывались на протяжении десятилетий как для систем компьютерной картографии, так и для ГИС, как векторных [Brassel and Reif, 1979], так даже и на структуре данных