|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Iassenev 2:5020/400 10 Jul 2003 12:18:29
To : Dmitriy Iassenev
Subject : Re: Перетаскивание ребер и вершин. Может попроще сначала задачку?
--------------------------------------------------------------------------------
> > А каким методом делается поиск ближайшего соседа за O(logN)? И N тут
> именно
> > количество точек, а не ребер? Можно как-нибудь на пальцах объяснить или
> > ссылку, а то я не могу сообразить. Если допустим двигаться начиная с
> > произвольного ребра, поворачивая все время по ветке, более близкой к
> искомой
> > точке, до тех пор пока не зациклимся, то там по-моему больше чем
O(logN),
> а
> > больше ничего придумать не могу.
>
> Сам по себе метод весьма нетривиален. Могу дать ссылку на книгу
> "Вычислительная геометрия", авторы Препарата и Шеймос ("Геометрический
поиск
> : Задача локализации точки, метод детализации триангуляции Киркпатрика"),
> впрочем реализаций диаграммы Вороного для любых размерностей полно в
> интернете (в том числе и с запросами на локализацию точки). В этом методе
> используется граф, двойственный диаграмме Вороного (триангуляция Делоне).
Я ошибся, в методе детализации триангуляции Киркпатрика триангуляция Делоне
не используется.
По сути, для того, чтобы отыскать вершину, ближайшую к заданной, нам нужно
найти ячейку диаграммы Вороного, которая содержит заданную точку - вершина,
соответствующая этой ячейке, и будет ближайшей. Ограничим какими-то большими
значениями бесконечные рёбра диаграммы Вороного и опишем вокруг неё
треугольник. Далее триангулируем получившийся ППЛГ (планарный прямолинейный
граф), а далее метод детализации триангуляции Киркпатрика строит
последовательности триангуляций с целью получить древовидную структуру, по
которой поиск треугольника, содержащего заданную точку, осуществляется за
O(logN).
В принципе, можно использовать и более простые методы нахождения
принадлежности точки простому многоугольнику, но они требуют больше памяти
(метод полос - О(N^2)) или дают неоптимальное время ответа на запрос (метод
цепей - О((logN)^2)).
Hа практике, часто имеет смысл затратить больше памяти, но получить очень
высокую скорость ответа на запрос (т.е. получить очень маленькую константу
при логарифме). Для этого можно использовать k-d деревья (что уже было
замечено в этом топике).
Вообще, советовать что-то Вам очень сложно, поскольку метод выбирается в
зависимости специфики конкретной задачи.
С уважением,
Дмитрий Ясенев.
--- ifmail v.2.15dev5
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
