анти. Guide to Competitive
Скачать 2.39 Mb.
|
Глава 13 Геометрия В этой главе обсуждаются алгоритмы, относящиеся к геометрии. Наша цель – найти способы, позволяющие удобно решать геометрические зада- чи, избегая особых случаев и корявых реализаций. В разделе 13.1 мы познакомимся с классом комплексных чисел из стан- дартной библиотеки C++, в котором имеются полезные средства для ре- шения геометрических задач. Затем мы узнаем о применении векторного произведения для решения таких задач, как проверка пересечения двух отрезков и вычисление расстояния от точки до прямой. Наконец, мы обсу- дим различные способы вычисления площади многоугольников и специ- альные свойства манхэттенского расстояния. Раздел 13.2 посвящен алгоритмам на основе заметающей прямой, ко- торые играют важную роль в вычислительной геометрии. Мы увидим, как такие алгоритмы используются для подсчета точек пересечения, нахожде- ния ближайших точек и построения выпуклой оболочки. 13.1. Технические средства в геометрии При решении геометрических задач возникает общая проблема: найти подход, позволяющий свести количество особых случаев к минимуму, и придумать удобный способ реализации решения. В этом разделе мы рас- смотрим ряд инструментов, упрощающих решение геометрических задач. 13.1.1. Комплексные числа Комплексное число имеет вид x + yi, где i = √–1 – так называемая мнимая единица. Геометрически комплексное число интерпретируется как точка на двумерной плоскости (x, y)или как вектор, соединяющий начало ко- ординат с точкой (x, y). На рис. 13.1 изображено комплексное число 4 + 2i. В стандартной библиотеке C++ имеется класс complex для представления комплексных чисел, он полезен при решении геометрических задач. С по- мощью этого класса мы можем представлять точки и векторы как комп- лексные числа и использовать методы класса для операций над этими объектами. Для этого сначала определим тип координат C. В зависимости от ситуации это может быть тип long long или long double . Вообще го- 248 Глава 13. Геометрия воря, лучше по возможности работать с целочисленными координатами, поскольку вычисления в этом случае точны. (4, 2) Рис. 13.1. Комплексное число 4 + 2i, интерпретируемое как точка и как вектор Вот возможные определения типа координат: typedef long long C; typedef long double C; Затем определим тип комплексного числа P , представляющий точку или вектор: typedef complex Наконец, определим макросы для ссылки на координаты x и y: #define X real() #define Y imag() Например, в следующем фрагменте создается точка p = (4, 2) и печата- ются ее координаты x и y: P p = {4,2}; cout << p.X << "" << p.Y << "\n"; // 4 2 А ниже создаются векторы v = (3, 1)и u = (2, 2), после чего вычисляется их сумма s = v + u. P v = {3,1}; P u = {2,2}; P s = v+u; cout << s.X << "" << s.Y << "\n"; // 5 3 Функции. В классе complex имеются также функции, полезные для ре- шения геометрических задач. Описанные ниже функции следует исполь- зовать, только когда тип координат long double (или другой тип с плаваю- щей точкой). 13.1. Технические средства в геометрии 249 Функция abs (v)вычисляет длину |v| вектора v = (x, y)по формуле √x 2 + y 2 Ее можно также использовать для вычисления расстояния между точка- ми (x 1 , y 1 )и (x 2 , y 2 ), поскольку это расстояние равно длине вектора (x 2 – x 1 , y 2 – y 1 ). В следующем коде вычисляется расстояние между точками (4, 2) и (3, −1). P a = {4,2}; P b = {3,-1}; cout << abs(b-a) << "\n"; // 3.16228 Функция arg (v)вычисляет полярный угол между вектором v = (x, y)и поло- жительным направлением оси x, т. е. для вектора, направленного вправо, угол равен нулю и возрастает против часовой стрелки. Функция возвраща- ет угол в радианах (r радиан равно 180r/π градусов). Функция polar (s, a) конструирует вектор длины s, наклоненный к оси x под углом a, выраженным в радианах. Для поворота вектора на угол a его нужно умножить на вектор длины 1 с полярным углом a. В следующем коде вычисляется полярный угол вектора (4, 2), затем век- тор поворачивается на 1/2 радиана, и снова вычисляется полярный угол: P v = {4,2}; cout << arg(v) << "\n"; // 0.463648 v *= polar(1.0,0.5); cout << arg(v) << "\n"; // 0.963648 13.1.2. Точки и прямые Векторное произведение a × b векторов a = (x 1 , y 1 )и b = (x 2 , y 2 )определяется как x 1 y 2 − x 2 y 1 . Оно дает направление вектора b относительно вектора a. На рис. 13.2 показаны три возможных случая: • a × b > 0: b повернут относительно a влево; • a × b = 0: направления a и b совпадают или противоположны; • a × b < 0: b повернут относительно a вправо. a b a × b > 0 a b a × b = 0 a b a × b < 0 Рис. 13.2. Интерпретация векторного произведения 250 Глава 13. Геометрия Например, векторное произведение векторов a = (4, 2) и b = (1, 2) равно 4 · 2 – 2 · 1 = 6, что соответствует первому случаю на рис. 13.2. Ниже пока- зано, как вычисляется векторное произведение: P a = {4,2}; P b = {1,2}; C p = (conj(a)*b).Y; // 6 Этот код работает, потому что функция conj меняет знак координаты y вектора, а координата y произведения векторов (x 1 , −y 1 )и (x 2 , y 2 )равна x 1 y 2 − x 2 y 1 Рассмотрим некоторые применения векторного произведения. Проверка положения точки относительно прямой. Векторное произведение позволяет узнать, как расположена точка относительно прямой: слева или справа. Предположим, что прямая проходит через точки s 1 и s 2 , что мы смотрим из s 1 в s 2 и что дана точка p. Так, на рис. 13.3 точка p расположена слева от прямой. Положение точки p можно узнать, вычислив векторное произведение (p − s 1 ) × (p − s 2 ). Если оно положительно, то p расположена слева от прямой, если отрицательно, то справа, а если равно нулю, то точки s 1 , s 2 и p лежат на одной прямой. Пересечение отрезков. Предположим теперь, что требуется узнать, пе- ресекаются ли два отрезка ab и cd. Если отрезки пересекаются, то возмож- ны три случая. Случай 1. Отрезки лежат на одной прямой и частично перекрываются. В этом случае количество точек пересечения бесконечно. Так, на рис. 13.4 все точки между c и b яв- ляются точками пересечения. Чтобы рас- познать этот случай, можно воспользовать- ся векторным произведением и проверить, лежат ли все четыре точки на одной пря- мой. Если да, то отсортируем их и проверим, пере крываются ли отрезки. Случай 2.Отрезки имеют общий конец, ко- торый является единственной точкой пере- сечения. На рис. 13.5 точкой пересечения является b = c. Этот случай легко проверить, т. к. всего существует четыре возможные точки пересечения: a = c, a = d, b = c и b = d. s 1 s 2 p Рис. 13.3. Проверка положения точки относительно прямой a d c b Рис. 13.4. Случай 1: отрезки лежат на одной прямой и перекрываются a b = c d Рис. 13.5. Случай 2: отрезки имеют общий конец 13.1. Технические средства в геометрии 251 Случай 3. Существует одна точка пересече- ния, не являющаяся общим концом отрезков. На рис. 13.6 p – точка пересечения. В этом случае отрезки пересекаются тогда и только тогда, когда точки c и d лежат по разные сто- роны от прямой, проходящей через a и b, а точки a и b – по разные стороны от прямой, проходящей через c и d. Это можно прове- рить, вычислив векторные произведения. Расстояние от точки до прямой. Еще одно свойство векторного произведения со- стоит в том, что площадь треугольника мож- но вычислить по формуле |(a − c) × (b − c)| , 2 где a, b и c – вершины треугольника. Зная это, мы можем вывести формулу для вы- числения кратчайшего расстояния меж- ду точкой и прямой. На рис. 13.7 буквой d обозначено кратчайшее расстояние между точкой p и прямой, проходящей через точ- ки s 1 и s 2 Площадь треугольника с вершинами s 1 , s 2 и p можно вычислить двумя способами: 1 2 |s 2 − s 1 |d (стандартная школь- ная формула) и 1 2 ((s 1 − p)× (s 2 − p))(формула с применением векторного произведения). Следовательно, кратчайшее расстояние равно 1 2 2 1 ( ) ( ) s p s p d s s − × − = − Точка внутри многоугольника. Наконец, обсудим, как узнать, нахо- дится ли точка внутри или вне многоугольника. На рис. 13.8 точка a нахо- дится внутри, а точка b – вне многоугольника. Для решения этой задачи удобно провести луч из точки в произвольном направлении и посчитать, сколько раз он пересекает границу многоуголь- ника. Если это число нечетное, то точка находится внутри, а если четное, то вне. Так, на рис. 13.9 лучи, проведенные из точки a, пересекают границу многоугольника 1 и 3 раза, поэтому a находится внутри. Аналогично лучи, проведенные из точки b,пересекают границу 0 и 2 раза, поэтому b нахо- дится вне многоугольника. c d a b p Рис. 13.6. Случай 3: отрезки пересекаются в точке, не являющейся концом s 1 s 2 p d Рис. 13.7. Вычисление расстояния от точки p до прямой 252 Глава 13. Геометрия a b Рис. 13.8. Точка a находится внутри многоугольника, а точка b вне его a b Рис. 13.9. Проведение лучей из точек a и b 13.1.3. Площадь многоугольника Общая формула вычисления площади многоугольника иногда называ- ется формулой шнурования: 1 1 1 1 1 1 1 1 1 ( ) ( ) . 2 2 n n i i i i i i i i p p x y x y − − + + + = = × = − ∑ ∑ Здесь вершины многоугольника p 1 = (x 1 , y 1 ), p 2 = (x 2 , y 2 ), …, p n = (x n , y n ) упорядочены таким образом, что p i и p i +1 – соседние вершины, а первая вершина совпадает с последней, т. е. p 1 = p n (4, 1) (7, 3) (5, 5) (2, 4) (4, 3) Рис. 13.10. Многоугольник площади 17/2 13.1. Технические средства в геометрии 253 Например, площадь многоугольника на рис. 13.10 равна |(2 · 5 − 5 · 4) + (5 · 3 − 7 · 5) + (7 · 1 − 4 · 3) + (4 · 3 − 4 · 1) + (4 · 4 − 2 · 3)| = 17/2. 2 Для вывода этой формулы многоугольник покрывается трапециями, одна сторона которых совпадает со стороной многоугольника, а другая лежит на горизонтальной оси y = 0. На рис. 13.11 показана одна такая трапеция. (4,1) (7,3) (5,5) (2,4) (4,3) Рис. 13.11. Вычисление площади многоугольника методом трапеций Площадь каждой трапеции равна 1 1 ( ) , 2 i i i i y y x x + + + − где (x i , y i ) и (x i +1 , y i +1 ) – координаты вершин p i и p i +1 многоугольника. Если x i +1 > x i , то площадь положительна, а если x i +1 < x i , то отрицательная. Про- суммировав площади всех трапеций, получим формулу площади много- угольника: 1 1 1 1 1 1 1 1 1 ( ) ( ) . 2 2 n n i i i i i i i i i i y y x x x y x y − − + + + + = = + − = − ∑ ∑ Мы берем абсолютную величину, потому что сумма может оказаться положительной или отрицательной в зависимости от направления обхода границы многоугольника. Теорема Пика дает еще один способ вычисления площади много- угольника, все вершины которого имеют целочисленные координаты. Она утверждает, что площадь равна a + b/2 − 1, где a – количество целых точек внутри многоугольника, а b – количест- во целых точек на его границе. Например, площадь многоугольника на рис. 13.12 равна 6 + 7/2 − 1 = 17/2. 254 Глава 13. Геометрия (4,1) (7,3) (5,5) (2,4) (4,3) Рис. 13.12. Вычисление площади многоугольника с помощью теоремы Пика 13.1.4. Метрики Метрика определяет расстояние между двумя точками. Обычное евкли- дово расстояние между точками (x 1 , y 1 )и (x 2 , y 2 ) равно 2 2 2 1 2 1 ) ( ) ( + x x y y − − Манхэттенское расстояние между точками (x 1 , y 1 )и (x 2 , y 2 ) вычисляется по формуле |x 1 − x 2 | + |y 1 – y 2 |. На рис. 13.13 евклидово расстояние между точками равно 2 2 5 ) (2 1 10 ) ( 2 + = − − , а манхэттенское расстояние между ними же равно |5 − 2| + |2 − 1| = 4. (2, 1) (5, 2) (2, 1) (5, 2) Manhattan distance Euclidean distance Евклидово расстояние Манхэттенское расстояние Рис. 13.13. Две метрики На рис. 13.14 показано, как выглядят единичные круги – множества то- чек, удаленных от центра на расстояние, не большее 1, – при использова- нии евклидовой и манхэттенской метрик. 13.1. Технические средства в геометрии 255 Euclidean distance Manhattan distance Евклидово расстояние Манхэттенское расстояние Рис. 13.14. Единичные круги Некоторые задачи проще решить, если использо- вать манхэттенское, а не евклидово расстояние. На- пример, пусть дано множество точек на плоскости и требуется найти пару точек, для которых манхэттен- ское расстояние максимально. Так, на рис. 13.15 ман- хэттенское расстояние между точками B и C макси- мально и равно 5. При работе с манхэттенским расстоянием быва- ет полезно применить преобразование координат (x, y)→ (x + y, y − x). При этом происходят поворот на 45° и масштабирование. На рис. 13.16 показан резуль- тат этого преобразования в нашем примере. Рассмотрим теперь две точки p 1 = (x 1 , y 1 )и p 2 = (x 2 , y 2 ), которые после пре- образования перешли в p' 1 = (x' 1 , y' 1 )и p' 2 = (x' 2 , y' 2 ). Манхэттенское расстояние между p 1 и p 2 можно выразить двумя способами: |x 1 – x 2 | + |y 1 – y 2 | = max(|x' 1 – x' 2 |, |y' 1 – y' 2 |). Например, если p 1 = (1, 0) и p 2 = (3, 3), то пре- образованные координаты равны p' 1 = (1, −1) и p' 2 = (6, 0), а манхэттенское расстояние |1 − 3| + |0 − 3| = max(|1 − 6|, |−1 − 0|) = 5. Преобразование координат дает простой спо- соб работать с манхэттенскими расстояниями, потому что координаты x и y можно рассматри- вать порознь. В частности, чтобы максимизи- ровать манхэттенское расстояние, необходимо найти такие две точки, что их преобразованные координаты доставляют максимум величине max(|x' 1 – x' 2 |, |y' 1 – y' 2 |). Это легко, потому что должна быть максимальна разность горизонталь- ных или вертикальных координат после преобразования. A C B D Рис. 13.15. Манхэт- тенское расстояние между точками B и C максимально A C B D Рис. 13.16. Максималь- ное манхэттенское расстояние после преоб- разования координат 256 Глава 13. Геометрия 13.2. Алгоритмы на основе заметающей прямой Многие геометрические задачи можно решить с помощью заметающей прямой. Идея в том, чтобы представить задачу в виде множества событий, соответствующих точкам на плоскости. Затем события обрабатываются в порядке возрастания координаты x или y. 13.2.1. Точки пересечения Дано множество n горизонтальных и вертикальных отрезков, требуется вычислить количество точек их пересечения. На рис. 13.17 показаны пять отрезков и три точки пересечения. Рис. 13.17. Пять отрезков, пересекающихся в трех точках Задачу легко решить за время O(n 2 ), перебрав все пары отрезков и про- верив, пересекаются они или нет. Но можно ограничиться временем O(n log n), если воспользоваться заметающей прямой и структурой данных для запроса по диапазону. Идея в том, чтобы просматривать концевые точки отрезков слева направо, обрабатывая следующие события: (1) горизонтальный отрезок начался; (2) горизонтальный отрезок закончился; (3) встретился вертикальный отрезок. На рис. 13.18 показаны эти события в нашем примере. 1 2 1 2 1 2 3 3 Рис. 13.18. События, соответствующие отрезкам Создав события, мы пробегаем по ним слева направо, используя струк- туру данных, в которой хранятся координаты y активных горизонтальных 13.2. Алгоритмы на основе заметающей прямой 257 отрезков. При обработке события 1 координата y отрезка добавляется в структуру, а при обработке события 2 удаляется из нее. При обработке со- бытия 3 вычисляются точки пересечения: если координаты концов верти- кального отрезка равны y 1 и y 2 , то мы подсчитываем количество активных горизонтальных отрезков, для которых координата y лежит между y 1 и y 2 , и прибавляем это число к общему числу точек пересечения. Для хранения координат y горизонтальных отрезков можно использо- вать двоичное индексное дерево или дерево отрезков, возможно, со сжа- тием индексов. Обработка одного события занимает время O(log n), так что временная сложность алгоритма равна O(n log n). 13.2.2. Задача о ближайшей паре точек Далее рассмотрим такую задачу: дано множество n точек, требуется найти две точки, евклидово расстояние между которыми наименьшее. На рис. 13.19 изображено множество точек, а ближайшая пара выделена чер- ным. Рис. 13.19. Пример задачи о ближайшей паре точек Это еще один пример задачи, которую можно решить за время O(n log n) с помощью алгоритма на основе заметающей прямой 1 . Мы просматрива- ем точки слева направо и храним значение d: минимальное расстояние между двумя встретившимися до сих пор точками. Если расстояние мень- ше d, то оно становится новым минимальным расстоянием и значение d обновляется. Если (x, y)– текущая точка и слева от нее существует точка, удаленная на расстояние меньше d, то координата x такой точки должна принадлежать диапазону [x − d, x], а координата y – диапазону [y − d, y + d]. Поэтому доста- точно рассмотреть только точки, находящиеся в этой области, что и делает алгоритм эффективным. На рис. 13.20 область внутри штрихового контура содержит точки, которые могут находиться на расстоянии, не большем d от текущей. 1 Создание эффективного алгоритма нахождения ближайшей пары точек когда-то было важной не- решенной задачей вычислительной геометрии. В конце концов, Шамос и Хоуи [30] придумали алго- ритм типа «разделяй и властвуй», работающий за время O(n log n). Представленный в этом разделе алгоритм на основе заметающей прямой имеет с ним общие черты, но проще в реализации. 258 Глава 13. Геометрия d d Рис. 13.20. Область, в которой должна находиться ближайшая точка Эффективность алгоритма основана на том фак- те, что эта область всегда содержит лишь O(1)точек. Чтобы понять, почему это так, обратимся к рис. 13.21. Поскольку текущее минимальное расстояние меж- ду двумя точками равно d, каждый квадрат размера d/2×d/2 может содержать не более одной точки. А раз так, то во всей области не может быть больше восьми точек. Перебрать все точки можно за время O(log n), если хранить множество точек с координатой x в диапазо- не [x − d, x] отсортированными в порядке возрастания координаты y. Временная сложность алгоритма равна O(n log n), поскольку нам нужно просмотреть n точек и для каждой определить ближайшую к ней слева, для чего необходимо время O(log n). 13.2.3. Задача о выпуклой оболочке Выпуклой оболочкой называется наименьший выпуклый многоугольник, содержащий все точки заданного множества. Здесь слово «выпуклый» озна- чает, что если две точки находятся внутри многоугольника, то внутри нахо- дится и весь отрезок между ними. На рис. 13.22 показана выпуклая оболочка множества точек. Рис. 13.22. Выпуклая оболочка множества точек d d Рис. 13.21. Область ближайших точек содержит O(1) точек 13.2. Алгоритмы на основе заметающей прямой 259 Существует много эффективных алгоритмов построения выпуклой обо- лочки. Пожалуй, самым простым является описываемый ниже алгоритм Эндрю [2]. Сначала алгоритм находит самую левую и самую правую точку множества, затем строит верхнюю и нижнюю части выпуклой оболочки. Обе части похожи, так что можно ограничиться только верхней. Сначала точки сортируются по координате x, а если координаты x двух точек совпадают, то по координате y. Затем мы просматриваем все точки и добавляем их в оболочку. Добавив очередную точку в оболочку, мы смот- рим, поворачивает ли последний отрезок налево. Если да, то мы удаляем предпоследнюю точку из оболочки и повторяем проверку. На рис. 13.23 показано, как алгоритм Эндрю строит верхнюю выпуклую оболочку для нашего множества точек. Шаг 1 Шаг 2 Шаг 3 Шаг 4 Шаг 5 Шаг 6 Шаг 7 Шаг 8 Шаг 8 Шаг 10 Шаг 11 Шаг 12 Шаг 13 Шаг 14 Шаг 15 Шаг 16 Шаг 17 Шаг 18 Шаг 19 Шаг 20 Рис. 13.23. Построение верхней части выпуклой оболочки с помощью алгоритма Эндрю |