Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
(а) (Ь)
Рис. 7.9. Иллюстрация к доказательству того, что алгоритм находит по крайней мере одну точку пересечения, если Р и Q пересекаются.
пересечения. Пусть pi-ipi — текущее ребро Р — содержит точку пересечения v с ребром qr-\qr, так что qr^h(pi) (рис. 7.9). Обозначим через w следующую точку пересечения в серпе, начавшемся в точке v; существуют еще две важные точки в Q: вершина qr, уже определенная, и вершина qs, наиболее удаленная в h(pi) от прямой, несущей ребро pt-ipt. Граница Q разбивается этими двумя вершинами на две ориентированные цепи Сг и Cs, которые оканчиваются в вершинах qr и qs соответственно. Считая, как обычно, что qi-iq,- обозначает текущее ребро в Q, будем различать следующие два случая:
(1) qj^Cr. Подпрограмма ДВИЖЕНИЕ последовательно обрабатывает случаи (каждый из которых может оказаться пустым) (2), (4), (1) и (3), как показано на рис. 7.9(a). Продвижение ведется вдоль Q, в то время как ребро pi-\pi остается неизменным вплоть до того, как обнаруживается v.
(2) ^,eCs (рис. 7.9(b)). Пусть / — прямая, несущая qT^iqJ-Существуют две опорные прямые к Р, параллельные /. Пусть рт — та вершина, принадлежащая одной из этих опорных пря-
Гл. 7. Пересечения
мых, которая встретится первой при просмотре границы Р, начиная с pi. Очевидно, что подпрограмма ДВИЖЕНИЕ (случаи (2) и (4)) проходит от р,- до рт, в то время как ребро q,-iqi остается неизменным. Затем, если pm^.h(qj), то ДВИЖЕНИЕ далее проследует к первой вершине pt^h(qj). В любом случае текущими вершинами остаются qs и р'еР (р* — рт или Р* — Pt), лежащие внутри h(qj). Заметим, что данная ситуация не отличается от такой, как если бы одна вершина q заменила подцепь (qr, qr+i, <7/-i), где q — пересечение прямых, несущих qr-iqr и <J7_i<7/ соответственно. Поэтому можно считать, как будто <?/ и р* принадлежат к одному и тому же серпу, а в этом случае подпрограмма ДВИЖЕНИЕ обязательно приведет к конечной точке этого серпа.
Если ребро, подобное p<-ip;, существует (т. е. границы Р и Q пересекаются), то после (L -4- М) шагов подпрограммы ДВИЖЕНИЕ оно обязательно будет достигнуто; действительно, после (L-f-Af) шагов граница по крайней мере одного многоугольника будет полностью пройдена, а каждый многоугольник имеет по крайней мере одно ребро, подобное p,_iPi. Легко убедиться в том, что затем понадобится еще не более (L-\-М)
Рис. 7.10. Иллюстрация работы алгоритма О'Рурка и др. Ребро, помеченное числом /, обрабатывается подпрограммой ДВИЖЕНИЕ на /-Й итерации. Начальные ребра выделены жирной линией.
дополнительных шагов подпрограммы ДВИЖЕНИЕ, чтобы построить всю границу Pf]Q- Итак, заключаем, что если после 2(L + M) шагов подпрограммы ДВИЖЕНИЕ данный алгоритм не смог обнаружить ни одной точки пересечения, то границы исходных многоугольников вовсе не пересекаются. С точки зрения оценки работы ДВИЖЕНИЕ завершается за время O(L-fM); кроме того, 0(L-\-M) шагов нужны, чтобы сделать выбор, если это необходимо, между следующими альтернативами: PsQ, Q^P, P[)Q = 0. Поэтому данный метод служит еще одним доказательством теоремы 7.3.
Иллюстрация работы этого алгоритма дана на рис. 7.10. Ребро там получает метку /, если цикл repeat (шаг подпрограммы ДВИЖЕНИЕ) достигает его на /-й итерации. Пара исходных ребер (одно из Р и одно из Q выделены жирными линиями) корректно помечена нулями.
7.2. Плоские приложения
7.2.2. Пересечение звездных многоугольников
Поскольку звездные многоугольники легко описывать в полярной системе координат — таким же свойством обладают и выпуклые многоугольники, — то можно было бы ожидать, что и их пересечения удастся находить столь же быстро. Однако это не так, что и показано на рис. 7.11.
Пересечение Р п Q уже само по себе оказывается не многоугольником, а объединением многих многоугольников. Если и Р, и Q имеют по N вершин, а каждое ребро Р пересекает каждое ребро Q, то их пересечение имеет порядок N2 вершин. Отсюда получаем тривиальную нижнюю оценку:
Теорема 7.4. Поиск пересечения двух звездных N-угольников занимает в худшем случае Q(N2) вре-
Это означает, что задача об удалении невидимых линий для произвольных многоугольников также должна потребо- гоугольнш вать в худшем случае
квадратичного времени просто потому, что для того, чтобы нарисовать их пересечения, необходимо Q{N2) векторов. В следующем разделе будет показан удивительный результат, состоящий в том, что если нужно установить только факт пересечения Р и Q, то нет необходимости тратить так много времени.
7.2.3. Пересечение прямолинейных отрезков
Один из главных выводов вычислительной геометрии состоит в том, что большой набор, казалось бы, независимых задач можно решить одним и тем же способом, если только удается выделить общие для них алгоритмические особенности. В данном разделе показано, как множество различных приложений можно унифицировать и свести к решению задачи о том, будут или нет попарно непересекающимися N прямолинейных отрезков из заданного множества.
Задача С.2.1 (ПРОВЕРКА ПЕРЕСЕЧЕНИЯ ПРЯМОЛИНЕЙНЫХ ОТРЕЗКОВ). Даны N прямолинейных отрезков на плоскости. Надо определить факт пересечения хотя бы двух из них.
