Планарный прямолинейный график - Planar straight-line graph

Пример планарный прямолинейный график

В вычислительная геометрия, а планарный прямолинейный график, короче PSLG, (или же прямолинейный плоский график, или же плоский прямолинейный график) - термин, используемый для встраивание из планарный граф в самолет таким образом, чтобы его края отображались в отрезки прямых линий.[1] Теорема Фари (1948) утверждает, что каждый планарный граф имеет такое вложение.

В вычислительной геометрии PSLG часто называют планарные подразделения, с предположением или утверждением, что подразделения являются многоугольными, а не имеют изогнутые границы.

PSLG могут служить представлением различных карты, например, географические карты в географические информационные системы.[2]

Частными случаями PSLG являются триангуляции (триангуляция многоугольника, триангуляция набора точек ). Триангуляции по множеству точек являются максимальными PSLG в том смысле, что к ним невозможно добавить прямые ребра, сохраняя при этом планарность графа. Триангуляции имеют множество приложений в различных областях.

PSLG можно рассматривать как особый вид Евклидовы графы. Однако при обсуждении евклидовых графов основной интерес представляют их метрические свойства, то есть расстояния между вершинами, тогда как для PSLG основной интерес представляют топологические свойства. Для некоторых графиков, например Триангуляции Делоне, важны как метрические, так и топологические свойства.

Представления

Существуют три хорошо известные структуры данных для представления групп PSLG: Крылатый край структура данных, Halfedge, и Quadedge. Структура данных с крылатым краем является самой старой из трех, но для манипулирования ею часто требуется сложное различение регистра. Это связано с тем, что ссылки на кромки не сохраняют направление кромки, и направления кромок вокруг грани необязательно должны быть согласованными. Структура данных с половинным краем хранит обе ориентации ребра и должным образом связывает их, упрощая операции и схему хранения. В структуре данных Quadedge одновременно хранятся и планарные подразделения, и двойники. Его записи явно состоят только из записей ребер, по четыре для каждого ребра, и в упрощенном виде он подходит для хранения PSLG.[3]

Проблемы с точки зрения PSLG

  • Расположение точки. Для точки запроса найдите, к какому лицу PSLG она принадлежит.
  • Наложение карты. Найдите наложение двух PSLG (карт), которое представляет собой подразделение плоскости двумя одновременно встроенными PSLG. В ГИС эта проблема известна как "тематическая карта оверлей ".

Смотрите также

Рекомендации

  1. ^ Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение. Springer-Verlag. 1-е издание: ISBN  0-387-96131-3; 2-е издание, исправленное и расширенное, 1988 г .: ISBN  3-540-96131-3; Русский перевод, 1989 г .: ISBN  5-03-001041-6.
  2. ^ Надь, Джордж; Вагл, Шарад (июнь 1979 г.), «Обработка географических данных», Опросы ACM Computing, 11 (2): 139–181, Дои:10.1145/356770.356777
  3. ^ Справочник по структурам данных и приложениям, Д. П. Мехта и С. Сахни, 2005 г., ISBN  1-58488-435-5, глава 17