Алгоритмы ГИС (5000,00 руб.)

Стр.5

Стр.7

Стр.8

Стр.9

УДК 528.1:379.85 ББК 26.8:32.81 С99 С99 Алгоритмы ГИС / пер. с англ. А. А. Слинкина. – М.: ДМК Пресс, 2021. – 328 с.: ил. Сяо H. ISBN 978-5-97060-908-8 В этой книге обсуждаются концептуальные основы географических информационных систем (ГИС) – важнейшие алгоритмы, составляющие фундамент многих операций над пространственными данными. Проследив, как эти данные подаются на вход алгоритма и как алгоритм используется для получения конечного результата, читатель поймет два важных аспекта ГИС: что на самом деле представляют собой геопространственные данные и как они обрабатываются. В книгу включены алгоритмы, которые обеспечивают измерение важных пространственных свойств (например, расстояния), включение нескольких источников данных с помощью слоев, ускорение анализа за счет применения различных методов индексирования. Уделено внимание алгоритмам решения таких задач пространственного анализа и моделирования, как интерполяция, анализ паттернов и принятие решений с помощью моделей оптимизации. Издание будет полезно студентам и преподавателям географических и технических вузов, а также всем, кто хочет разобраться в принципах работы ГИС. УДК 528.1:379.85 ББК 26.8:32.81 Authorized Russian translation of the English edition of GIS Algorithms ISBN 9781491974292. This translation is published and sold by permission of SAGE Publishing, which owns or controls all rights to publish and sell the same. Russian language edition copyright © 2021 by DMK Press. All rights reserved. Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. ISBN 978-1-491-97429-2 (англ.) ISBN 978-5-97060-908-8 (рус.) © Ningchuan Xiao, 2016 © Оформление, издание, перевод, ДМК Пресс, 2021

Стр.5

Содержание Об авторе ...................................................................................................................9 Предисловие ..........................................................................................................10 От издательства ....................................................................................................12 Глава 1. Введение ................................................................................................13 1.1. Вычислительные аспекты алгоритмов ............................................................14 1.2. Кодирование .....................................................................................................19 1.3. Как использовать эту книгу .............................................................................19 Часть I. ГЕОМЕТРИЧЕСКИЕ АЛГОРИТМЫ .......................................22 Глава 2. Базовые геометрические операции ........................................23 2.1. Точка ..................................................................................................................23 2.2. Расстояние между двумя точками ...................................................................25 2.3. Расстояние от точки до прямой .......................................................................28 2.4. Центроид и площадь многоугольника ............................................................30 2.5. Определение положения точки относительно прямой .................................32 2.6. Пересечение отрезков прямых ........................................................................34 2.7. Операция «точка внутри многоугольника».....................................................38 2.7.1. Алгоритм чет-нечет ...................................................................................39 2.7.2. Алгоритм на основе числа оборотов ........................................................42 2.8. Картографические проекции ...........................................................................45 2.9. Примечания ......................................................................................................57 2.10. Упражнения .....................................................................................................58 Глава 3. Наложение многоугольников ......................................................60 3.1. Пересечение отрезков ......................................................................................60 3.2. Наложение .........................................................................................................68 3.3. Примечания ......................................................................................................77 3.4. Упражнения .......................................................................................................78 Часть II. ИНДЕКСИРОВАНИЕ ПРОСТРАНСТВЕННЫХ ДАННЫХ ................................................................................................................79 Глава 4. Индексирование .................................................................................80 4.1. Упражнения .......................................................................................................85 Глава 5. kD-деревья ............................................................................................86 5.1. Точечные kD-деревья ........................................................................................86

Стр.7

Содержание  7 5.1.1. Запрос к прямоугольному диапазону ......................................................91 5.1.2. Запрос к круговому диапазону .................................................................93 5.1.3. Поиск ближайших соседей ........................................................................94 5.2. Точечно-регионные kD-деревья ......................................................................97 5.3. Тестирование kD-деревьев .............................................................................103 5.4. Примечания ....................................................................................................107 5.5. Упражнения .....................................................................................................107 Глава 6. Квадродеревья .................................................................................109 6.1. Регионные квадродеревья ..............................................................................109 6.2. Точечные квадродеревья ................................................................................115 6.3. Примечания ....................................................................................................120 6.4. Упражнения .....................................................................................................121 Глава 7. Индексирование отрезков и многоугольников ................122 7.1. Квадродеревья полигональных карт .............................................................122 7.1.1. PM1-квадродеревья .................................................................................126 7.1.2. PM2-квадродеревья .................................................................................132 7.1.3. PM3-квадродеревья .................................................................................134 7.2. R-деревья .........................................................................................................136 7.3. Примечания .....................................................................................................145 7.4. Упражнения .....................................................................................................146 Часть III. ПРОСТРАНСТВЕННЫЙ АНАЛИЗ И МОДЕЛИРОВАНИЕ ..................................................................................147 Глава 8. Интерполяция ....................................................................................148 8.1. Метод обратных взвешенных расстояний ....................................................150 8.2. Кригинг ............................................................................................................156 8.2.1. Полудисперсия .........................................................................................156 8.2.2. Моделирование полудисперсии .............................................................159 8.2.3. Обыкновенный кригинг ..........................................................................166 8.2.4. Простой кригинг ......................................................................................171 8.3. Применение методов интерполяции ............................................................174 8.4. Смещение средней точки ...............................................................................180 8.5. Примечания ....................................................................................................184 8.6. Упражнения .....................................................................................................185 Глава 9. Пространственные паттерны и их анализ ..........................187 9.1. Анализ точечных паттернов ..........................................................................188 9.1.1. Анализ ближайшего соседа .....................................................................188 9.1.2. K-функция Рипли ....................................................................................195 9.2. Пространственная автокорреляция ..............................................................202 9.3. Кластеризация ................................................................................................209 9.4. Метрики ландшафтной экологии ..................................................................212 9.5. Примечания ....................................................................................................218 9.6. Упражнения .....................................................................................................219

Стр.8

8  Содержание Глава 10. Анализ сетей ....................................................................................221 10.1. Обход сети .....................................................................................................224 10.1.1. Обход в ширину .....................................................................................224 10.1.2. Обход в глубину .....................................................................................226 10.2. Кратчайший путь из одного узла .................................................................227 10.3. Кратчайшие пути между всеми парами узлов ............................................232 10.4. Примечания ...................................................................................................236 10.5. Упражнения ...................................................................................................236 Глава 11. Пространственная оптимизация ...........................................238 11.1. Задача о 1-центре .........................................................................................240 11.2. Задачи размещения ......................................................................................254 11.3. Примечания ...................................................................................................258 11.4. Упражнения ...................................................................................................259 Глава 12. Эвристические алгоритмы поиска .......................................261 12.1. Жадные алгоритмы ......................................................................................261 12.2. Алгоритм обмена вершин ............................................................................263 12.3. Имитация отжига ..........................................................................................271 12.4. Примечания ...................................................................................................283 12.5. Упражнения ...................................................................................................284 Послесловие.........................................................................................................286 Приложение А. Введение в Python...........................................................288 Приложение В. GDAL/OGR и PySAL ..........................................................303 Приложение С. Список программ ..............................................................315 Список литературы ...........................................................................................318 Предметный указатель ...................................................................................324

Стр.9