6
$\begingroup$

I have some Graphs for which I have explicitly specified both the VertexCoordinates and the EdgeShapeFunction. I'd like to determine (just a boolean True/False is fine) whether the resulting Graph as drawn on screen contains any intersecting edges. E.g.,

Image of graph with no intersecting edges, labeled False, and graph with intersecting edges, labeled True

How might I go about detecting this?

If it is useful for testing, I produced the above graphs thusly:

symbols = Table[Unique[], 8];
v = Flatten[MapAt[Reverse, Table[{a, s}, {s, symbols}, {a, {-3, 3}}], {;; ;; 2}], 1];
e = BlockMap[Apply@UndirectedEdge, v, 2, 1] ~Drop~ {Length@symbols};
curv = GraphElementData[{"CurvedArc", "Curvature" -> (#〚1〛〚2〛 - #〚2〛〚2〛) / #〚2〛〚1〛}]&;
g[order_] := With[{rules = Thread[symbols -> order]}, Graph[e, 
  VertexCoordinates -> Thread[v -> (v /. rules)], EdgeShapeFunction -> Thread[e -> (curv /@ e /. rules)]]]

g1 = g[{8, 3, 2, 1, 5, 4, 6, 7}]
g2 = g[{8, 6, 5, 1, 7, 3, 2, 4}]
$\endgroup$
7
$\begingroup$
Graphics`Mesh`MeshInit[]

ClearAll[edgeIntersections]
edgeIntersections =  Complement[Graphics`Mesh`FindIntersections[Show @ #], 
    N @ GraphEmbedding[#]] &;

edgeIntersections[g1]
 {}
edgeIntersections[g2]
 {{-3.99852, 4.}, {-3.31218, 3.25027}, {-3.31218, 6.74973}}
Show[g2, Graphics[{Red, PointSize[Large], Point @ edgeIntersections[g2]}]]

enter image description here

ClearAll[edgesIntersectQ]
edgesIntersectQ = edgeIntersections[#] =!= {} &;

edgesIntersectQ /@ {g1, g2}
{False, True}
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.