数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究数据结构中的平面直线图 (PSLG)
在计算几何中，平面直线图 (简称 PSLG)（或直线平面图，或平面直线图）定义为平面图在平面上的嵌入，其边映射为直线段。Fáry 定理 (1948) 的陈述是，每个平面图都有这种嵌入。
在计算几何中，PSLG 通常被称为平面细分，并假设或断言细分是多边形的。
如果没有度为 1 的顶点，PSLG 定义了平面到多边形区域的细分，反之亦然。度为 1 的顶点的缺失简化了各种算法的描述，但这并非必需的。
PSLG 可以用于表示各种地图，例如地理信息系统中的地理地图。
PSLG 有一些特殊情况。特殊情况是三角剖分（多边形三角剖分，点集三角剖分）。点集三角剖分是最大 PSLG，因为在保持图平面性的同时，不可能向其中添加直线边。三角剖分在许多领域都有各种应用。
PSLG 可以看作是欧几里德图的一种特殊类型。此外，在涉及欧几里德图的讨论中，主要关注的是它们的度量属性，即顶点之间的距离，而对于 PSLG，主要关注的是拓扑属性。对于某些图，例如 Delaunay 三角剖分，度量属性和拓扑属性都很重要。
表示
PSLG 由三种众所周知的数据结构表示。这些数据结构是带翼边数据结构、半边数据结构和四边数据结构。带翼边数据结构是最古老的三种之一，但是操作它通常需要复杂的案例区分。其原因在于边引用不存储边方向，并且面周围边的方向不必一致。半边数据结构用于存储边的两种方向并正确地链接它们，从而简化操作和存储方案。四边数据结构用于同时存储平面细分及其对偶。它的记录只明确包含边记录，每条边四个，简化形式可用于存储 PSLG。
更新于：2020年1月7日
315 次浏览
广告