Алгоритм Фортуны - Структура данных береговой линии - PullRequest
Новая
       48

Алгоритм Фортуны - Структура данных береговой линии

4 голосов
/ 31 декабря 2011

Мне нужно реализовать алгоритм Fortunes для построения диаграмм Вороного.

Важной частью алгоритма является структура данных, называемая "Структура данных Beach Line".

Itявляется бинарным сбалансированным деревом, похожим на AVL, но отличается тем, что данные хранятся только на листьях (есть и другие различия, но они не важны для вопроса).

Я не уверен, как это реализовать.Очевидно, что использование AVL «как есть» не будет работать, потому что при балансировке конечного узла дерева AVL может стать внутренним узлом, и наоборот.

Я также попытался взглянуть на некоторые другие известные структуры данных в Википедии, но ни одна из них не удовлетворяет потребностям,Я видел несколько реализаций, которые делают это с помощью связанного списка, но это не очень хорошо, потому что поиск связанного списка - это O (n), а для эффективности алгоритм должен быть O (log n).

1 Ответ

3 голосов
/ 09 января 2012

Листья действительно хранят (одиночные) точки, а внутренние узлы структуры события ( "пляжное дерево" ) хранят упорядоченные кортежи точек, параболы / дуги которых лежат рядом друг с другом.Если парабола, которая образует точку P a , находится слева от параболы, образованной P b (и эти две параболы пересекаются)внутренний узел хранит упорядоченный кортеж (P a , P b ) .

Очевидно, что использование AVL «как есть» не будет работать, потому что при балансировке листовой узел дерева AVL может стать внутренним узлом, и наоборот.

Если вы беспокоитесь о сохраненииДля различных типов объектов в дереве AVL простая схема будет хранить листья также как кортежи.Так что не храните точку P j как лист, но храните кортеж (P j , P j ) вместо.Если P j как лист исчезает из дерева событий (линия пляжа), а его родительский элемент равен (P i , P j) , просто измените родителя на (P j , P j ) и, конечно, его родительтакже необходимо изменить с (P j , P ? ) на (P i , P ? ) и т. Д. Как и в случае обычного дерева AVL: вы идете вверх по дереву и модифицируете внутренние узлы, которые необходимо изменить и / или повторно сбалансировать.

Обратите внимание, что хорошийРеализация алгоритма не может быть легко записана в SO-ответе (по крайней мере, не мной!).Правильное объяснение всего алгоритма, включая описание используемых им структур данных, см. В Вычислительная геометрия: алгоритмы и приложения Марка де Берга и др. .Глава 7 посвящена исключительно диаграммам Вороного.

...