Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 19

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 13 14 15 16 17 18 < 19 > 20 21 22 23 24 25 .. 180 >> Следующая


для каждой ячейки. Это можно легко проделать для любой из ячеек за время О (Л/), что приводит к общей затрате времени 0(N3) на предобработку; однако для менее наивного подхода ') время предобработки можно снизить до 0(N2).

Если кто-то сочтет затраты памяти и времени на" предобработку для вышеизложенного метода чрезмерными, то он может

Таблица I


Предобработка
Примечание


О (Л/2)
0(N2)
Изложенный ме-

0(log2iV)
0(N\ogN)
O(NlogN)
2)

O(N)
O(N)
0(N)
Без предобра-

') См. работу по региональному поиску [Benlley, Shamos (1977)]. 3) Этот результат, полученный также в [Bentley, Shamos (1977)], будет показан в разд 2.3.4.

2.2. Задачи локализации точки

исследовать другие подходы. Обычно эти исследования демонстрируют общее правило, известное из практики построения алгоритмов, а именно взаимозависимость между различными мерами эффективности. Задача регионального поиска не составляет исключения; в таблице I показаны затраты при комбинировании ресурсов.

Из предыдущих рассуждений вытекают две главные модели для задач геометрического поиска:

1. Задачи локализации, когда файл представляет собой разбиение геометрического пространства на области, а запрос является точкой. Локализация состоит в определении области, содержащей запрошенную точку.

2. Задачи регионального поиска, когда файл содержит набор точек пространства, а запрос есть некая стандартная геометрическая фигура, произвольно перемещаемая в этом пространстве (типичный запрос в 3-мерном пространстве это шар или брус). Региональный поиск состоит в извлечении (задачи отчета) или в подсчете числа (задачи подсчета) всех точек внутри запросного региона (области).

Хотя методы, используемые для решения этих двух типов задач, близки — мы только что видели, как региональный поиск может быть сведен к задаче о локализации точки, — удобно демонстрировать их отдельно. Остаток этой главы посвящен данному вопросу.

2.2. Задачи локализации точки

2.2.1. Общие соображения. Простые случаи

Задачи локализации точки можно также с полным основанием назвать задачами о принадлежности точки. В самом деле, утверждение «точка р лежит в области R» синонимично утверждению «точка р принадлежит области R». Трудоемкость решения этой задачи, безусловно, будет существенно зависеть от природы пространства и от способа его разбиения.

Для современного состояния вычислительной геометрии типично то, что плоская задача хорошо изучена, но весьма мало известно про случай Е3 и даже еще менее — про случаи большего числа измерений.

Даже в самом простом случае плоскости тип разбиения, на котором ведется поиск, определяет для этой задачи сложность, оцениваемую тремя основными мерами, указанными в предыдущем разделе. Рассмотрим сначала разбиения плоскости — или планарные подразбиения, как их обычно называют, — образованные прямолинейными отрезками; затем мы откажемся от этого допущения, которое выглядит ограничивающим. Однако

58

Гл. 2. Геометрический поиск

прежде, чем изложение будет продолжено, необходимо упомянуть об одной технической детали: рассматриваемые нами пленарные подразбиения таковы, что после удаления из плоскости границ областей остающиеся открытые множества связны. Это нужно для того, чтобы пару точек, принадлежащих одной области, можно было соединить кривой, не содержащей граничных точек области.

Первой приходит в голову задача, в которой плоскость разбита на две области, одна из которых бесконечна, а другая является многоугольником Я. Очевидно, что Р — простой многоугольник; это следует из условия разбиения плоскости на две области и из теоремы Жордана для многоугольников (см. разд. 1.3.1). Итак, можно сформулировать:

Задачу П.2 (ПРИНАДЛЕЖНОСТЬ МНОГОУГОЛЬНИКУ). Даны простой многоугольник Р и точка z; определить, находится ли z внутри Р.

Повторим еще раз, что трудоемкость этой задачи зависит от того, обладает ли Я помимо простоты еще какими-нибудь полезными свойствами. Интуитивно выпуклый многоугольник выглядит более простым объектом. Поэтому рассмотрим:

Задачу П.З (ПРИНАДЛЕЖНОСТЬ ВЫПУКЛОМУ МНОГОУГОЛЬНИКУ). Даны выпуклый многоугольник Р и точка г. Находится ли z внутри Я?

Можно сразу же продемонстрировать ее решение для случая уникального запроса, причем этот результат будет справедлив и для невыпуклых многоугольников.

Теорема 2.1. Принадлежность точки z внутренней области простого N-угольника Р можно установить за время O(N) без предобработки.

Доказательство. Проведем через точку z горизонталь I (рис. 2.5). По теореме Жордана внешняя и внутренняя области Я хорошо определены. Если / не пересекает Я, то z — внешняя точка. Поэтому пусть / пересекает Я, и рассмотрим вначале случай, когда / не проходит ни через одну из вершин Я. Пусть L — число точек пересечения / с границей Я слева от г. Поскольку Я ограничен, левый конец / лежит вне Я. Будем двигаться вдоль / от —оо направо вплоть до г. На самом левом пересечении / с границей Я мы попадем внутрь Я, на следующем пересечении выйдем наружу и т. д. Поэтому z лежит внутри тогда и только тогда, когда L нечетно. Теперь рассмотрим вырожденный случай, когда / проходит через вершины Я. Бесконечно малый поворот / вокруг z против часовой стрелки .не изменит классификации (внутри/вне) точки z, но устранит вырожденность. Итак,
Предыдущая << 1 .. 13 14 15 16 17 18 < 19 > 20 21 22 23 24 25 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed