4551
правка
Прямолинейное остовное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
м
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 00:06, 29 апреля 2016
, 29 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 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 будет добавлена в активное множество. Каждая точка будет добавлена в активное множество и удалена из него только один раз. | |||