Вычислительная геометрия. Алгоритмы и приложения
Покупка
Тематика:
Геометрия и топология
Издательство:
ДМК Пресс
Перевод:
Слинкин Алексей Александрович
Год издания: 2017
Кол-во страниц: 439
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-97060-406-9
Артикул: 854440.01.99
Перед вами хорошо известное введение в вычислительную геометрию. Основной упор в книге сделан на алгоритмах в виде, доступном широкой аудитории.
Все методы и решения, разрабатываемые в рамках вычислительной геометрии, связаны с конкретными применениями в робототехнике, компьютерной графике, САПР/АСУП и геоинформационных системах. Для большинства рассмотренных геометрических задач приводится одно, наиболее оптимальное решение. Рассмотрены все основные, а также ряд специальных тем вычислительной геометрии.
Издание предназначено студентам, аспирантам, а также разработчикам программного обеспечения, имеющих лишь базовую подготовку в области алгоритмов.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 01.03.01: Математика
- 01.03.02: Прикладная математика и информатика
- 01.03.04: Прикладная математика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Марк де Берг, Отфрид Чеонг, Марк ван Кревельд, Марк Овермарс
ВЫЧИСЛИТЕЛЬНАЯ
ГЕОМЕТРИЯ
Алгоритмы и приложения
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
Вычислительная геометрия.............................................. 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
Оглавление
Планирование движения робота......................................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 большое» и простыми алгоритмами, в том числе с сортировкой, двоичным поиском и сбалансированными деревьями поиска. Не предполагается никаких знаний о предметной области и почти никаких по геометрии. При анализе рандомизированных алгоритмов используется элементарная теория вероятностей. Реализации. Алгоритмы в этой книге представлены на псевдокоде высокого уровня, но описаны достаточно детально, для того чтобы их можно было без труда реализовать. В частности, мы старались всюду обращать внимание на обработку вырожденных случаев, которые зачастую вызывают трудности, когда дело доходит до реализации. Мы полагаем весьма полезным самостоятельно реализовать несколько алгоритмов, т. к. это позволит составить представление об их практической сложности. Каждую главу можно рассматривать как программный проект. В зависимости от