Прямолинейное остовное дерево: различия между версиями

Перейти к навигации Перейти к поиску
Строка 48: Строка 48:
Пусть даны две точки p, q в одном и том же сегменте (октанте) восьмиугольного разбиения плоскости относительно точки s. Согласно свойству единственности, ||pq|| < max(||sp||; ||sq||). Рассмотрим цикл с точками s, p и q. Согласно свойству циклов, только одну точку с минимальным расстоянием до s необходимо соединить с s. Интересное свойство восьмиугольного разбиения заключается в том, что контур равноудаленных от s точек формирует отрезок прямой в каждой области. В областях <math>R_1, R_2, R_5, R_6 \;</math> эти сегменты описываются уравнением вида x + y = c; в областях <math>R_3, R_4, R_7, R_8 \;</math> – уравнением вида x - y = c.
Пусть даны две точки p, q в одном и том же сегменте (октанте) восьмиугольного разбиения плоскости относительно точки s. Согласно свойству единственности, ||pq|| < max(||sp||; ||sq||). Рассмотрим цикл с точками s, p и q. Согласно свойству циклов, только одну точку с минимальным расстоянием до s необходимо соединить с s. Интересное свойство восьмиугольного разбиения заключается в том, что контур равноудаленных от s точек формирует отрезок прямой в каждой области. В областях <math>R_1, R_2, R_5, R_6 \;</math> эти сегменты описываются уравнением вида x + y = c; в областях <math>R_3, R_4, R_7, R_8 \;</math> – уравнением вида x - y = c.


Для каждой точки s необходимо найти ближайшего к ней соседа в каждом октанте. Опишем, как эффективно вычислить соседей в октанте <math>R_1 \;</math> для всех точек. Случаи остальных октантов симметричны. Для октанта <math>R_1 \;</math> алгоритм с заметающей прямой исполняется для всех точек в порядке неубывания x + y. В процессе заметания поддерживается [[активное множество]], состоящее из точек, для которых ближайшие соседи в <math>R_1 \;</math> еще не найдены. После обработки точки p будут найдены все точки активного множества, содержащие p в их областях <math>R_1 \;</math>. Если такая точка содержится в активном множестве, то, поскольку точки проверяются в порядке неубывания x + y, p должна быть ближайшей точкой для s в <math>R_1 \;</math>.  
Для каждой точки s необходимо найти ближайшего к ней соседа в каждом октанте. Опишем, как эффективно вычислить соседей в октанте <math>R_1 \;</math> для всех точек. Случаи остальных октантов симметричны. Для октанта <math>R_1 \;</math> алгоритм с заметающей прямой исполняется для всех точек в порядке неубывания x + y. В процессе заметания поддерживается [[активное множество]], состоящее из точек, для которых ближайшие соседи в <math>R_1 \;</math> еще не найдены. После обработки точки p будут найдены все точки активного множества, содержащие p в их областях <math>R_1 \;</math>. Если такая точка содержится в активном множестве, то, поскольку точки проверяются в порядке неубывания x + y, p должна быть ближайшей точкой для s в <math>R_1 \;</math>. Таким образом, будет добавлено ребро sp и точка s будет удалена из активного множества. После обработки этих активных точек точка p будет добавлена в активное множество. Каждая точка будет добавлена в активное множество и удалена из него только один раз.
 
Таким образом, будет добавлено ребро sp и точка s будет удалена из активного множества. После обработки этих активных точек точка p будет добавлена в активное множество. Каждая точка будет добавлена в активное множество и удалена из него только один раз.




Источник — http://pco.iis.nsk.su/wega/index.php/Прямолинейное_остовное_дерево