遍历边缘和解决交叉点的优雅而有效的方法

Question

我有一个数组，它表示这样一个图的邻接矩阵。

connections:Array = [0,0,1,1,
                     0,0,1,1,
                     0,0,0,1,
                     0,0,0,0];

图中的每个节点都有一个分配给它的二维点，代表它在平面上的位置。我正在尝试编写一个遍历所有边的函数，如果两条边中的任何一条相交，则 returns false。这是我的代码

function test():boolean
{
    for (i = 0; i < nodes.length ; i++)
    {
        for (j = i ; j < nodes.length ; j ++)
        {
            if (connections[i * nodes.length + j] == 1)
            {
                //we found an edge
                //This is the place where i am stuck I, can't figure out how
                //to take pairs of edges to test them for intersections
            }
        }
    }
}

您可以用任何语言甚至伪代码给出答案。

注意：我不需要交集算法的任何代码。

Answer 1

在遍历邻接矩阵的同时，构建以边为中心的数据结构。最简单的选择是简单的边列表。然后你可以迭代所有以前访问过的边，这会给你 O(V^2 + E^2) 的复杂性，其中 V 是顶点数，E 是边数。

如果您的图可能很大，您可能希望使用更高效的数据结构，例如动态构建的 BSP 树。这将使您的复杂性降低到 O(V^2 + E log E).

遍历边缘和解决交叉点的优雅而有效的方法

Elegant and efficient way to traverse through edges and resolve intersections

algorithm

traversal

graph

pseudocode

actionscript-3