Wanted: a program that will give edge crossing count

Help
1

Given a graph that has node & edge positions (from any layout engine), how can I determine the count of edge crossings?

2

I’ve used this set of functions (python) in the past:

def ccw(A,B,C):
    Ax,Ay=A
    Bx,By=B
    Cx,Cy=C
    return (Cy-Ay) * (Bx-Ax) > (By-Ay) * (Cx-Ax)

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)

def edge_intersect(E,F):
    A,B = E
    C,D = F
    return intersect(A,B,C,D)

It’s not my work, but cribbed as an answer from here: graph - How to check if the connections between points are crossing each other? - Stack Overflow

and here: Line Segment Intersection Algorithm - Bryce Boe for a more authoritative source, which contains a downloadable script.

It assumes that edges E,F are each tuples containing the x,y positions of connected nodes.

So if A–B and A is at (0,1) and B is at (1,0) and C–D with C at (0,0) and D at (1,1)

edge_intersect(((0,1),(1,0)),((0,0),(1,1)))

Should return True.

You’d have to build a loop to compare all pairwise edge possibilities, then determine if/whether there are any crossings. It doesn’t consider splines or wiggly edges, just assumes straight lines.

3

It doesn’t consider splines

That’s the problem, at least if we want correct answers.

I don’t think there’s code for this in Graphviz, because the spline router’s main job is to find a path inside a constraint polygon. There must be code that tests whether a candidate spline intersects this polygon.

There must be code for this somewhere? It’s a nontrivial problem, or it used to be: computational geometry - Reliable test for intersection of two Bezier curves - Stack Overflow
Note that actually we are dealing with continuous sequences of piecewise cubic Bezier splines.

There are probably a lot of potential efficiency hacks, like comparing bounding boxes the splines as a cheap test before solving 9th degree polynomials. The stackoverflow article suggests if you just want to detect where splines appear to intersect, use a pixel-based algorithm.