Плоский прямолинейный график
В вычислительной геометрии и геометрической теории графов планарный прямолинейный граф (или прямолинейный плоский граф , или плоский прямолинейный граф ), короче PSLG , представляет собой вложение плоского графа в плоскость так, что его ребра отображаются на карту. на прямолинейные отрезки. [1] Теорема Фари (1948) утверждает, что каждый плоский граф имеет такое вложение.
В вычислительной геометрии PSLG часто называют плоскими подразделениями , при этом предполагается или утверждается, что подразделения являются многоугольными, а не имеют изогнутые границы.
PSLG могут служить представлениями различных карт , например географических карт в географических информационных системах . [2]
Особыми случаями PSLG являются триангуляции ( триангуляция полигонов , триангуляция множества точек ). Триангуляции множества точек являются максимальными PSLG в том смысле, что к ним невозможно добавить прямые ребра, сохраняя при этом планарность графа. Триангуляции имеют множество применений в различных областях.
PSLG можно рассматривать как особый вид евклидовых графов . Однако при обсуждении евклидовых графов основной интерес представляют их метрические свойства, т. е. расстояния между вершинами, тогда как для PSLG основной интерес представляют топологические свойства. Для некоторых графов, таких как триангуляции Делоне , важны как метрические, так и топологические свойства.
Представительства
[ редактировать ]Существуют три хорошо известные структуры данных для представления PSLG: структура данных Winged-edge , Halfedge и Quadedge . Структура данных с «крылатым краем» — самая старая из трех, но манипулирование ею часто требует сложного различения регистров. Это связано с тем, что ссылки на ребра не сохраняют направление ребер, а направления ребер вокруг грани не обязательно должны быть согласованными. Структура данных полуребра хранит обе ориентации ребра и правильно связывает их, упрощая операции и схему хранения. Структура данных Quadedge одновременно хранит как плоское подразделение, так и его двойное подразделение. Его записи состоят явно только из записей ребер, по четыре на каждое ребро, и в упрощенном виде он пригоден для хранения PSLG. [3]
Проблемы с точки зрения PSLG
[ редактировать ]- Расположение точки . Для точки запроса найдите, к какой стороне PSLG она принадлежит.
- Наложение карты . Найдите наложение двух PSLG (карт), которое представляет собой подразделение плоскости двумя одновременно внедренными PSLG. В ГИС эта проблема известна как « наложение тематических карт ».
См. также
[ редактировать ]- Двусвязный список ребер , структура данных для представления PSLG.
- Размер локального объекта
Ссылки
[ редактировать ]- ^ Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия. Введение . Спрингер-Верлаг . ISBN 0-387-96131-3 . 1-е издание; 2-е издание, исправленное и дополненное, 1988 г.: ISBN 3-540-96131-3 ; Русский перевод, 1989: ISBN 5-03-001041-6 .
- ^ Надь, Джордж; Уэйгл, Шарад (июнь 1979 г.), «Обработка географических данных», ACM Computing Surveys , 11 (2): 139–181, doi : 10.1145/356770.356777 , S2CID 638860
- ^ Справочник по структурам данных и приложениям, Д.П. Мехта и С. Сахни, 2005 г., ISBN 1-58488-435-5 , глава 17