В вычислительной геометрии , A плоской прямой линейный график , в коротком PSLG , (или прямой линии плоского графа , или плоскости прямой линии графика ) это термин , используемый для вложения в виде плоского графа в плоскости таким образом, что ее края отображаются на отрезки прямых. [1] Теорема Фари (1948) утверждает, что каждый планарный граф имеет такое вложение.
В вычислительной геометрии PSLG часто называют планарными подразделениями с предположением или утверждением, что подразделения являются многоугольными, а не имеют изогнутые границы.
PSLG могут служить представлениями различных карт , например географических карт в географических информационных системах . [2]
Особые случаи PSLGs являются триангуляции ( многоугольник триангуляции , точка-множество триангуляции ). Триангуляции точек являются максимальными PSLG в том смысле, что к ним невозможно добавить прямые ребра, сохраняя при этом планарность графа. Триангуляции имеют множество приложений в различных областях.
PSLG можно рассматривать как особый вид евклидовых графов . Однако при обсуждении евклидовых графов основной интерес представляют их метрические свойства, т. Е. Расстояния между вершинами, в то время как для PSLG основной интерес представляют топологические свойства. Для некоторых графов, таких как триангуляции Делоне , важны как метрические, так и топологические свойства.
Представления
Существует три хорошо известных структуры данных для представления групп PSLG: структура данных с крылатым краем , Halfedge и Quadedge . Структура данных с крылатым краем является самой старой из трех, но для манипулирования ею часто требуется сложное различение регистров. Это связано с тем, что ссылки на кромки не сохраняют направление кромки, и направления кромок вокруг грани необязательно должны быть согласованными. Структура данных с половинным краем хранит обе ориентации ребра и должным образом связывает их, упрощая операции и схему хранения. В структуре данных Quadedge одновременно хранятся и планарные подразделения, и двойники. Его записи явно состоят только из записей ребер, по четыре для каждого ребра, и в упрощенном виде он подходит для хранения PSLG. [3]
Проблемы с точки зрения PSLG
- Расположение точки . Для точки запроса найдите, к какому лицу PSLG она принадлежит.
- Наложение карты . Найдите наложение двух PSLG (карт), которое представляет собой подразделение плоскости двумя одновременно встроенными PSLG. В ГИС эта проблема известна как « наложение тематической карты ».
Смотрите также
- Список двусвязных ребер , структура данных для представления PSLG
- Размер локального объекта
Рекомендации
- ^ Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение . Springer-Verlag . 1-е издание: ISBN 0-387-96131-3 ; 2-е издание, исправленное и расширенное, 1988 г .: ISBN 3-540-96131-3 ; Русский перевод, 1989 г .: ISBN 5-03-001041-6 .
- ^ Надь, Джордж; Wagle, Шарада (июнь 1979), "Географическая обработка данных", ACM Computing Surveys , 11 (2): 139-181, DOI : 10,1145 / 356770,356777
- ^ Справочник структур данных и приложений, DP Mehta и S. Sahni, 2005, ISBN 1-58488-435-5 , глава 17