Дж. С. Дэвис. Статистический анализ данных в геологии. Книга 2
Рис. 5.48. Соединяя Тиссеновских соседей точки А, получаем тре-
угольную сеть вокруг точки А. Процесс затем повторяют для од-
ной из точек В – F и затем опять повторяют
В последние годы наметился возврат к триангуляцион-
ным процедурам благодаря созданию алгоритма, который по-
зволяет получить почти оптимальную сеть на первом шаге [39],
[55]. Эти сети, называемые триангуляцией Делоне, определены
единственным образом для данного множества точек. В допол-
нение к этому образуемые треугольники настолько близки к
равносторонним, насколько это возможно. Это значит, что наи-
большие расстояния, на которых должна производиться интерполяция для нахождения уровней изо-
линий меньше, чем в другой треугольной сети.
Если мы имеем дело с рассеянным множеством точек, то можно себе представить, что каж-
дая точка, лежащая внутри многоугольника, расположена ближе к любой другой точке, содержа-
щейся в нем, чем к точке вне его (рис. 5.45). Наоборот, каждая точка, находящаяся вне заданного
многоугольника, ближе к некоторой другой, чем к точке, лежащей внутри этого многоугольника.
Это – наиболее компактное подразделение пространства из всех возможных. Множества много-
угольников с такими свойствами называются многоугольниками Тиссена, Дирихле, Вороного и воз-
никают во многих областях.
Географы используют многочлены Тиссена для моделирования зон влияния конкурирующих
городов. Модель роста кристаллов в твердеющем растворе в металлургии основана на многогранни-
ках Вороного, являющихся трехмерным обобщением многоугольников. Совокупность мыльных пу-
зырей образует легко наблюдаемую сеть многогранников Вороного.
Многоугольники, непосредственно примыкающие к многоугольнику Тиссена, заключающе-
му заданную точку А, также являются многоугольниками Тиссена, каждый из которых заключает
единственную точку. Эти точки называются тиссеновскими соседями точки А. Если эти точки со-
единить прямыми линиями, то получится треугольная сеть Делоне (рис. 5.46). Для любого размеще-
ния точек как многоугольники Тиссена, так и треугольники Делоне единственны. Процесс триангу-
ляции состоит в определении тиссеновских соседей последовательных точек на карте. На рис. 5.47,
а найдены соседи точки А.
Сначала предположим, что вблизи точки В имеется сосед и построим круг, диаметр которого
определяется отрезком АВ. Если внутри круга нет других точек, то В действительно будет соседом
А. Если некоторая точка внутри круга будет найдена, то она заменит точку В. Поиск следующего
соседа производится против часовой стрелки относительно точки А. Круг разлагается указанным
образом так, чтобы точки А и В были расположены на его периметре. Затем внутренность круга
проверяется на наличие каких-либо заключенных в нем точек. Если будет найдена одна точка, то
она будет вторым тиссеновским соседом. Если будут найдены две или более точки, надо правильно
определить вторую окрестность. Это делается с помощью вычисления угла, образованного точкой б,
точкой-кандидатом и точкой А. Истинный тиссеновский сосед будет образовывать наибольший угол
(рис. 5.47, б). Поиск третьего тиссеновского соседа проводится с помощью вычерчивания такой ок-
ружности, что точка А и точка С, второй сосед, лежат на ее периметре. Проверяют, нет ли внутри
этого круга какой-либо точки, которую можно было считать третьим соседом D (см. рис. 5.47, б).
Далее строится круг, который на своем периметре содержит точки А и D и внутри которого произ-
водится поиск четвертого тиссеновского соседа. Может случиться, что точка В будет снова объяв-
лена тиссеновским соседом; тогда все соседи А должны быть отождествлены (рис. 5.47, г). Соеди-
нив этих соседей, получим треугольную сеть вокруг А (рис. 5.48).
Один из Тиссеновских соседей теперь обозначается через новую точку А, вокруг которой
снова будет производиться поиск, и весь процесс начнется снова. Сеть разрастается, распространя-
ясь, подобно волне, по карте до тех пор, пока каждая точка не будет в нее включена. Для достиже-
ния эффективности вычислений целесообразно предварительно осуществить сортировку координат
точек для того, чтобы при поиске сначала рассматривались наиболее вероятные кандидаты на роль
соседа. Хотя этот процесс довольно трудно описать, МакКаллах и Росс [55] определяют число необ-