# Wanted: a program that will give edge crossing count

**URL:** <https://forum.graphviz.org/t/wanted-a-program-that-will-give-edge-crossing-count/2201>\
**Category:** Help\
**Created:** [May 20, 2024, 2:31am UTC](https://forum.graphviz.org/t/wanted-a-program-that-will-give-edge-crossing-count/2201 "2024-05-20T02:31:01Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![steveroush](https://avatars.discourse-cdn.com/v4/letter/s/a9adbd/32.png) [@steveroush](https://forum.graphviz.org/u/steveroush)\
**Post date:** [May 20, 2024, 2:31am UTC](https://forum.graphviz.org/t/wanted-a-program-that-will-give-edge-crossing-count/2201/1 "2024-05-20T02:31:01Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![tkim](https://avatars.discourse-cdn.com/v4/letter/t/858c86/32.png) [@tkim](https://forum.graphviz.org/u/tkim)\
**Post date:** [May 21, 2024, 11:00am UTC](https://forum.graphviz.org/t/wanted-a-program-that-will-give-edge-crossing-count/2201/2 "2024-05-21T11:00:18Z")

</div>

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](https://stackoverflow.com/questions/31346374/how-to-check-if-the-connections-between-points-are-crossing-each-other)

and here: [Line Segment Intersection&nbsp;Algorithm - Bryce Boe](https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/) 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.

---

<div class="post-metadata">

**Author:** ![scnorth](https://sea2.discourse-cdn.com/graphviz/user_avatar/forum.graphviz.org/scnorth/32/89_2.png) [@scnorth](https://forum.graphviz.org/u/scnorth)\
**Post date:** [May 21, 2024, 11:18am UTC](https://forum.graphviz.org/t/wanted-a-program-that-will-give-edge-crossing-count/2201/3 "2024-05-21T11:18:41Z")

</div>

> 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](https://stackoverflow.com/questions/35058362/reliable-test-for-intersection-of-two-bezier-curves)  
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.