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,

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