Jump to content

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

(Перенаправлено из подразделения Planar )
Пример плоского линейного графа

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

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

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

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

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

Представительства

[ редактировать ]

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

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

[ редактировать ]

См. также

[ редактировать ]
  1. ^ Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия. Введение . Спрингер-Верлаг . ISBN  0-387-96131-3 . 1-е издание; 2-е издание, исправленное и дополненное, 1988 г.: ISBN   3-540-96131-3 ; Русский перевод, 1989: ISBN   5-03-001041-6 .
  2. ^ Надь, Джордж; Уэйгл, Шарад (июнь 1979 г.), «Обработка географических данных», ACM Computing Surveys , 11 (2): 139–181, doi : 10.1145/356770.356777 , S2CID   638860
  3. ^ Справочник по структурам данных и приложениям, Д.П. Мехта и С. Сахни, 2005 г., ISBN   1-58488-435-5 , глава 17
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 3aecac00bfd84b2e37a0be00a0503ff8__1706745240
URL1:https://arc.ask3.ru/arc/aa/3a/f8/3aecac00bfd84b2e37a0be00a0503ff8.html
Заголовок, (Title) документа по адресу, URL1:
Planar straight-line graph - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)