mercredi 23 décembre 2015

Elegant and efficient way to traverse through edges and resolve intersections

I have an array which represents adjacency matrix of a graph like this.

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

Every node of the graph has a 2D point assigned to it which represents its position on a plane. I am trying to write a function which traverses through all the edges and returns false if any of the two edges intersect. Here is my code

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
            }
        }
    }
}

You can give the answer in any language or even pseudo code.

Note: I don't need any code for intersection algorithm.

Aucun commentaire:

Enregistrer un commentaire