问题标签 [planar-graph]

我在 2D 平面上有一个连接图，由一些顶点和它们之间定义的一些边组成。图的整体形状不一定是凸的，即凸包上的相邻顶点并不总是由边连接。现在是否有一种现有的算法可以找到该图的“轮廓”？最困扰我的问题是，这个轮廓多边形可能包含的顶点不是原始图中的顶点，而是两条边的交点，所以我不太确定如何处理它......

谢谢！

尼可

这里的具体问题。假设您有一个图，其中每个顶点指定它们必须与另一个顶点有多少连接，并且适用以下规则/属性：

1-图形可能不完整（不需要每个顶点都相互连接）

2-只有当两个顶点的方向相反时，它们之间才能有两个连接（例如：A 点做 B，B 点到 A）。

3-假设它们在2D 平面上，不能有交叉连接（甚至没有切线）。

4-对最短路径没有兴趣，只需尊重属性并知道解决方案是否唯一。

5-不可能有解决办法

编辑：好的，抱歉没有具体说明。我将尝试在这里澄清我的观点：我想要做的是给定多个顶点，知道一个图是否连接（如果所有点都至少与图有一个连接）。给定的顶点可能无法绘制它的图表，所以我想知道是否有解决方案，解决方案是否唯一，或者（最坏的情况）是否没有可能的解决方案。我认为这阐明了第 4 点和第 5 点。图形是无向的，连接不能弯曲，只有直线。节点（顶点）是固定的，我们有它们的位置或 W/E 输入。我想知道最好的方法，我一直在研究，这是一个连接问题，尽管也许一些特定的算法可能更有效地完成这项任务。就是这样，抱歉回复晚了

EDIT2：好吧，如果我们认为每个顶点都在平面矩阵的行和列上并且它们只能与同一列或行上的其他顶点连接，那么问题会有所不同吗？所以它只是 90/180/270/360 直接连接。这会大大缩短可能性，对吗？

我有一个具有固定节点位置的无向图。不能移动、合并、移除或以其他方式更改节点。边缘固定到它们的节点，但不必是直的。

我需要知道是否可以“弯曲”或“绘制”边缘以使图形是平面的（即没有边缘交叉）。

如果存在这样的算法或实现，或者您只是对如何做有想法，请告诉我！

我有两组 n 个节点。现在我想将一组中的每个节点与另一组中的另一个节点连接起来。结果图应该没有交集。

我知道几种扫描线算法（Bentley-Ottmann-Algorithm来检查交叉点发生的位置，但我找不到解决这些交叉点的​​算法，除了蛮力方法。

一组中的每个节点都可以连接到另一组中的任何其他节点。

任何指向解决此问题的（有效）算法的指针？无需实施。

编辑1：

这是解决问题的一种方法n=7：

黑点是一组节点，红点是一组。每个黑色节点都必须连接到一个红色节点，这样连接它们的线就不会交叉。

编辑2：

进一步澄清：所有节点的位置都是固定的，结果图将有 n 条边。我也没有任何证据证明存在解决方案，但我无法创建没有解决方案的示例。我敢肯定，某处有证据表明始终可以创建这样的平面图。此外，只需要一种解决方案，而不是所有可能的解决方案。

我正在处理一个编程挑战，因为我需要找到给定点所属的区域。这里有一些方法可以解决这个问题。

点位置

所以我决定使用slab分解，它足够快，更容易实现，而且空间对我来说不是什么大问题。但是，我不知道从哪里开始。以下是 UC Santa Barbara 制作的 pdf 文件中的板分解示例。

我将几何形状存储在节点字典中，例如无向图（使用坐标）。

像这样。（仍然不知道边缘列表是否会更好？）

现在我知道如何解决这个问题，但是很难决定采用哪种方式，因为输入将是一个非常复杂的几何形状，并且在 cpu 资源中找到该点将是昂贵的。

我决定将每个点（使用 x 坐标排序）存储在排序列表中（使用平分）。获取板坯。但是，我找不到一种方法来找到板如何与区域边缘相交，或者如何划分板，如图所示。实际上我确实找到了一种方法，但对我来说并不可行。我可以检查从平板左侧开始到右侧结束的边缘。这意味着边缘正在穿过平板。这很好，但是要实现这一点，每次给定一个新节点并且区域增加时，我都必须检查几乎一半的顶点。所以这个方法对我来说听起来很失败。还有一个问题是要知道平板中的区域属于哪个区域。鉴于我们这样做是为了避免一一检查所有区域以提高速度。

如果你能给我一些关于这个主题的想法，我不需要任何代码。我只需要这里有经验的用户的建议。我被卡住了，因为我不确定如何实现它，我不想以错误的方式开始它并重写它。（我可以向你保证，这不是功课。）

注意1：我不确定数据结构，我应该为区域创建结构吗？还是为点？还是边缘？还是我需要一个结构来创建搜索树？我必须在这个结构中存储什么？

注2：我知道如何找到该点所在的板块。我也知道如何在平板内使用二进制搜索找到点。我缺乏更多的概念知识，因此缺乏经验。就像首先如何表示区域一样。

提前致谢。

任务

从一组不重叠（但接触）的多边形计算对偶图。

例子

多边形A、B和C，它们的部分共享坐标 1-22（黄色）和对偶图（蓝色）。

数据

我有一组多边形。每个多边形P _i都表示为坐标的有序列表。多边形P _i的边a - b记为P _i,(a,b)

主意

多边形代表面，因此代表对偶图的节点。要识别多边形P _i的相邻面，只需将P _i的每条边与每个其他多边形P _j的每条边进行比较。如果边由另一个多边形共享，则P _i和P _j是相邻的。

这将创建大量的多个边缘，这些边缘可以在以后移除。

问题

该算法不是很有效，因为它在O(E ² )中运行，其中E表示多边形集合S的边数。

改进思路

在第一步中创建一个边缘索引。这会将运行时间减少到O(2×E) = O(E)

删除每个度数为 2 的节点。（我认为这不会影响对偶图？）

问题

• 我在正确的轨道上吗？
• 是否有任何批准的算法用于此任务？

有没有一种方法可以测试网络图在 R 中是否是平面的？我查看了 igraph 但无济于事。

我知道我可以使用 BGL 工具箱使用 MATLAB，但我想知道是否有人在 R 中尝试过。

我试图了解是否可以增强平面性检查算法（例如 LR Planarity、PC 树、PQ 树等），以便允许某些边缘根据其类型交叉。

我有一个带有 3 种不同类型边的图：A、B、C

类型 A 的边不能与任何其他边相交。

B 型边可以穿过 C 型边，反之亦然。

我已经看过一个简单的 LR 平面度测试，但无法成功实现此功能。

是否可以采用现有算法并使用这些规则对其进行调整，或者是否已经有一种算法支持这一点？

如何从平面图的边缘列表或邻接列表表示转到面列表？

例如，使用此图（奇怪的是，它不是 0 索引）：

我想要一个看起来像这样的列表：

它不必采用那种格式或顺序，但它应该是所有面孔的某种列表（或集合）。包括外面。

对于具有 V 个顶点的图（E=O(V)，因为是平面的），算法应该在 O(V) 中生成这个列表。

我用 Graphviz 画了一个小的平面图，但在一个地方有两条边的交点。我在 SO 上读到，并非所有平面图都可以在没有交点的情况下绘制，因为这是一个 NP 难题。我还读到 Graphviz 中甚至没有实现复杂的算法来做到这一点。但是那个交叉点很容易修复，所以可能有办法摆脱它。

以下是我使用的选项：

这是图表：

那么，有没有一种方法可以修复一个交叉点（25-38 和 7-18）而不像我在这里所做的那样改变边缘的顺序？至少没有O(n^2)算法可以交换两个顶点并检查交叉点是否消失？