Элегантный и эффективный способ прохода по краям и устранения пересечений

Question

У меня есть массив, который представляет собой матрицу смежности графа, как это.

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

Каждому узлу графика назначена двухмерная точка, которая представляет его положение на плоскости. Я пытаюсь написать функцию, которая проходит через все ребра и возвращает 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).