Вычислительная геометрия. Алгоритмы и приложения

Марк де Берг, Отфрид Чеонг, Марк ван Кревельд, Марк Овермарс




ВЫЧИСЛИТЕЛЬНАЯ
   ГЕОМЕТРИЯ



         Алгоритмы и приложения

Mark de Berg · Otfried Cheong
Marc van Kreveld · Mark Overmars


Computational
Geometry

Algorithms and Applications



Third Edition

Марк де Берг · Отфрид Чеонг
Марк ван Кревельд · Марк Овермарс


Вычислительная
геометрия

Алгоритмы и приложения



Третье издание





                       Москва, 2017

УДК   514.7
ББК   22.151.5
     Б48

Б48  Марк де Берг, Отфрид Чеонг, Марк ван Кревельд, Марк Овермарс
     Вычислительная геометрия. Алгоритмы и приложения. 3-е изд. / Пер. с
      англ. Слинкин А. А. – М.: ДМК Пресс, 2017. – 438 с.: ил.


     ISBN 978-5-97060-406-9

       Перед вами хорошо известное введение в вычислительную геометрию.
    Основной упор в книге сделан на алгоритмах в виде, доступном широкой
     аудитории.
       Все методы и решения, разрабатываемые в рамках вычислительной гео     метрии, связаны с конкретными применениями в робототехнике, компью     терной графике, САПР/АСУП и геоинформационных системах. Для боль     шинства рассмотренных геометрических задач приводится одно, наиболее
     оптимальное решение. Рассмотрены все основные, а также ряд специальных
     тем вычислительной геометрии.
       Издание предназначено студентам, аспирантам, а также разработчикам
     программного обеспечения, имеющих лишь базовую подготовку в области
     алгоритмов.





        Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы
      то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев
      авторских прав.
         Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность
      технических ошибок все равно существует, издательство не может гарантировать абсолютную
      точность и правильность приводимых сведений. В связи с этим издательство не несет ответ      ственности за возможные ошибки, связанные с использованием книги.



ISBN 978-3-540-77973-5 (англ.)        © 2008, 2000, 1997 Springer-Verlag Berlin
                                               Heidelberg
ISBN 978-5-97060-406-9 (рус.)         © Оформление, издание, ДМК Пресс, 2017

              ОГЛАВЛЕНИЕ




Предисловие................................................................... 9

ГЛАВА 1.
Вычислительная геометрия.............................................. 13
   Введение...................................................................................................... 13
       1.1. Пример: выпуклые оболочки................................................................... 14
       1.2. Вырожденность и устойчивость.............................................................. 22
       1.3. Области применения.............................................................................. 23
       1.4. Замечания.............................................................................................. 27
       1.5. Упражнения............................................................................................ 29

ГЛАВА 2.
Пересечение отрезков.................................................... 32
 Наложение тематических карт....................................................................... 32
       2.1. Пересечение отрезков прямых............................................................... 33
       2.2. Двусвязный список ребер....................................................................... 44
       2.3. Вычисления наложения двух разбиений................................................. 49
       2.4. Булевы операции.................................................................................... 56
       2.5. Замечания.............................................................................................. 57
       2.6. Упражнения............................................................................................ 58

ГЛАВА 3.
Триангуляция многоугольника.......................................... 61
  Охрана картинной галереи............................................................................ 61
       3.1. Охрана и триангуляции........................................................................... 62
       3.2. Разбиение многоугольника на монотонные части................................... 66
       3.3. Триангуляция монотонного многоугольника........................................... 73
       3.4. Замечания.............................................................................................. 78
       3.5. Упражнения............................................................................................ 79

ГЛАВА 4.
Линейное программирование........................................... 81
 Литейные формы.......................................................................................... 81
       4.1. Геометрия отливки.................................................................................. 82

Оглавление

       4.2. Пересечение полуплоскостей................................................................. 85
       4.3. Инкрементное линейное программирование.......................................... 90
       4.4. Рандомизированное линейное программирование................................ 97
       4.5. Неограниченные линейные программы................................................ 100
       4.6*. Линейное программирование в многомерных пространствах............. 103
       4.7*. Минимальная описанная окружность.................................................. 107
       4.8. Замечания............................................................................................ 111
       4.9. Упражнения.......................................................................................... 113

ГЛАВА 5.
Поиск в ортогональных диапазонах..................................116
  Запрос к базе данных.................................................................................. 116
       5.1. Одномерный поиск по диапазону......................................................... 117
       5.2. Kd-деревья........................................................................................... 120
       5.3. Деревья диапазонов............................................................................. 128
       5.4. Многомерные деревья диапазонов....................................................... 132
       5.5. Множества точек общего вида.............................................................. 134
       5.6*. Частичное каскадирование................................................................. 135
       5.7. Замечания............................................................................................ 139
       5.8. Упражнения.......................................................................................... 141

ГЛАВА 6.
Локализация точки........................................................145
  Где я нахожусь............................................................................................. 145
       6.1. Локализация точки и трапецоидные карты............................................ 146
       6.2. Рандомизированный инкрементный алгоритм...................................... 153
       6.3. Обработка вырожденных случаев......................................................... 163
       6.4*. Оценка хвоста..................................................................................... 166
       6.5. Замечания............................................................................................ 169
       6.6. Упражнения.......................................................................................... 171

ГЛАВА 7.
Диаграммы Вороного.....................................................174
  Задача о почтовом отделении..................................................................... 174
       7.1. Определение и основные свойства....................................................... 175
       7.2. Вычисление диаграммы Вороного........................................................ 179
       7.3. Диаграмма Вороного отрезков прямых................................................ 189
       7.4. Дальняя диаграмма Вороного.............................................................. 193
       7.5. Замечания............................................................................................ 198
       7.6. Упражнения.......................................................................................... 201

ГЛАВА 8.
Конфигурации и двойственность......................................204
  Избыточная выборка в трассировке лучей................................................... 204
       8.1. Вычисление отклонения....................................................................... 206
       8.2. Двойственность.................................................................................... 209

Оглавление                                                      7

       8.3. Конфигурации прямых.......................................................................... 212
       8.4. Уровни и отклонение............................................................................ 218
       8.5. Замечания............................................................................................ 219
       8.6. Упражнения.......................................................................................... 222

ГЛАВА 9.
Триангуляции Делоне.....................................................224
  Интерполяция высоты................................................................................. 224
       9.1. Триангуляции множеств точек на плоскости......................................... 226
       9.2. Триангуляция Делоне........................................................................... 229
       9.3. Вычисление триангуляции Делоне........................................................ 233
       9.4. Анализ.................................................................................................. 240
       9.5.* Общая схема рандомизированных алгоритмов................................... 244
       9.6. Замечания............................................................................................ 250
       9.7. Упражнения.......................................................................................... 251

ГЛАВА 10.
Другие геометрические структуры данных........................255
  Оконные запросы........................................................................................ 255
       10.1. Деревья интервалов........................................................................... 256
       10.2. Приоритетные деревья поиска........................................................... 263
       10.3. Деревья отрезков............................................................................... 268
       10.4. Замечания.......................................................................................... 275
       10.5. Упражнения........................................................................................ 277

ГЛАВА 11.
Выпуклые оболочки.......................................................282
  Приготовление смесей................................................................................ 282
       11.1. Сложность выпуклых оболочек в трехмерном пространстве............... 284
       11.2. Вычисление выпуклых оболочек в трехмерном пространстве............. 285
       11.3.* Анализ............................................................................................... 290
       11.4.* Выпуклые оболочки и пересечение полупространств........................ 293
       11.5.* И снова о диаграммах Вороного........................................................ 295
       11.6. Замечания.......................................................................................... 297
       11.7. Упражнения........................................................................................ 298

ГЛАВА 12.
Двоичные разбиения пространства..................................301
  Алгоритм художника.................................................................................... 301
       12.1. Определение BSP-дерева.................................................................. 303
       12.2. BSP-деревья и алгоритм художника.................................................... 305
       12.3. Построение BSP-дерева..................................................................... 306
       12.4.* Размер BSP-дерева в трехмерном пространстве.............................. 311
       12.5. BSP-деревья для сцен низкой плотности............................................ 315
       12.6. Замечания.......................................................................................... 323
       12.7. Упражнения........................................................................................ 324

Оглавление

ГЛАВА 13.
Планирование движения робота......................................327
  Попасть туда, куда хочешь........................................................................... 327
       13.1. Рабочее пространство и конфигурационное пространство................. 328
       13.2. Точечный робот................................................................................... 331
       13.3. Суммы Минковского........................................................................... 336
       13.4. Планирование движения поступательно перемещающегося робота... 344
       13.5.* Планирование движения с вращением.............................................. 346
       13.6. Замечания.......................................................................................... 350
       13.7. Упражнения........................................................................................ 352

ГЛАВА 14.
Квадродеревья.............................................................354
  Генерация неравномерных сеток................................................................. 354
       14.1. Равномерные и неравномерные сетки................................................ 355
       14.2. Квадродеревья для множеств точек.................................................... 357
       14.3. От квадродеревьев к сеткам............................................................... 364
       14.4. Замечания.......................................................................................... 367
       14.5. Упражнения........................................................................................ 369

ГЛАВА 15.
Графы видимости..........................................................372
  Нахождение кратчайшего маршрута............................................................ 372
       15.1. Кратчайшие пути для точечного робота.............................................. 373
       15.2. Вычисление графа видимости............................................................ 376
       15.3. Кратчайшие пути для поступательно перемещающегося
           многоугольного робота...................................................................... 380
       15.4. Замечания.......................................................................................... 381
       15.5. Упражнения........................................................................................ 383

ГЛАВА 16.
Поиск в симплициальных диапазонах...............................385
 Еще об оконных запросах............................................................................ 385
       16.1. Деревья разбиения............................................................................. 385
       16.2. Многоуровневые деревья разбиения.................................................. 394
       16.3. Деревья сечений................................................................................ 397
       16.4. Замечания.......................................................................................... 404
       16.5. Упражнения........................................................................................ 406

Список литературы .......................................................409

Предметный указатель...................................................430

             ПРЕДИСЛОВИЕ



Вычислительная геометрия зародилась в области проектирования и анализа алгоритмов в конце 1970-х годов. Впоследствии она превратилась в самостоятельную дисциплину со своими журналами, конференциями и большим сообществом
активно работающих исследователей. Ее успех как отдельной отрасли научных
исследований можно, с одной стороны, объяснить красотой изучаемых задач и их
решений, а, с другой, многочисленностью областей применения – компьютерная
графика, геоинформационные системы (ГИС), робототехника и другие – в которых геометрические алгоритмы играют важнейшую роль.
  Есть много геометрических задач, первые алгоритмы решения которых либо
работали очень медленно, либо были трудны для понимания и реализации. В последние годы разработан ряд новых алгоритмических подходов, которые позволили улучшить или упростить прежние решения. В этой книге мы попытались
представить современные алгоритмы в виде, доступном широкой аудитории. Книга задумана как учебник по курсу вычислительной геометрии, но может использоваться и для самообразования.

   Организация книги. Каждая из шестнадцати глав (кроме введения) начинается с некоторой прикладной задачи. Эта задача переформулируется как чисто
геометрическая, а затем решается методами вычислительной геометрии. Сама
геометрическая задача, а также идеи и приемы ее решения и составляют тему главы. Выбор приложений продиктован темами, которые мы хотели охватить, и не
может считаться исчерпывающим обзором всех применений вычислительной геометрии. Мы ставили перед собой задачу пробудить любопытство у читателя, а не
продемонстрировать готовые решения. Вместе с тем, мы полагаем, что знание вычислительной геометрии важно для эффективного решения геометрических задач
в самых разных областях. Мы надеемся, что наша книга вызовет интерес не только
у алгоритмистов, но и у специалистов-прикладников.
  Для большинства рассмотренных геометрических задач мы приводим только
одно решение, даже если их существует несколько. В общем случае мы выбирали
то решение, которое проще всего понять и реализовать, пусть даже оно не самое
эффективное. Мы также постарались включить достаточное число различных технических приемов, например: метод «разделяй и властвуй», заметание плоскости
и рандомизированные алгоритмы. Мы решили не рассматривать всевозможные
варианты каждой задачи, нам казалось важнее познакомить читателя со всеми ос

Предисловие

новными вопросами вычислительной геометрии, чем увязнуть в деталях немногих избранных тем.
  Некоторые разделы отдельных глав помечены звездочками. В них описываются
улучшенные решения, обобщения или взаимосвязи между разными задачами. Для
понимания остального материала они необязательны.
  Каждая глава завершается разделом «Замечания». Здесь приводятся ссылки на
источники приведенных в данной главе результатов, упоминаются другие решения, обобщения и усовершенствования и дается обзор литературы. Эти разделы
можно пропустить, но они содержат полезную информацию для тех, кто хочет узнать больше о теме главы.
  В конце каждой главы имеются упражнения. Они варьируются от простых проверочных вопросов на усвоение до более сложных задач, расширяющих пройденный материал. Трудные упражнения, как и те, что относятся к материалу из разделов со звездочкой, помечены звездочкой.

  План курса. Хотя главы книги в значительной мере независимы, мы не рекомендуем читать их в произвольном порядке. Например, глава 2 знакомит с алгоритмами заметания плоскости, поэтому читать ее лучше до глав, в которых этот
метод используется. Точно так же главу 4 лучше прочитать раньше глав, в которых
применяются рандомизированные алгоритмы.
  В начальный курс вычислительной геометрии мы советуем включить материал
глав 1–10 в указанном порядке. В них рассматриваются понятия и методы, которые, на наш взгляд, должны быть освещены в любом курсе вычислительной геометрии. Если есть желание включить дополнительный материал, то можно взять
любые из оставшихся глав.

   Предварительные требования. Книгу можно использовать как учебник для
курса, читаемого при подготовке бакалавров или магистров, – в зависимости от
общей структуры учебного плана в данном учебном заведении. Предполагается,
что у читателя имеются базовые знания по проектированию и анализу алгоритмов и структурам данных. Читатель должен быть знаком с нотацией «O большое»
и простыми алгоритмами, в том числе с сортировкой, двоичным поиском и сбалансированными деревьями поиска. Не предполагается никаких знаний о предметной области и почти никаких по геометрии. При анализе рандомизированных
алгоритмов используется элементарная теория вероятностей.

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