Алгоритмы для краевой маршрутизации заданных местоположений пикселей узлов?

Question

Каковы некоторые алгоритмы для генерации ребер для различных узлов в графе, которые минимизируют перекрытие краев с узлами и другими ребрами?

В принципе, скажем, у меня есть куча ящиков (с шириной, высотой, xs, ys) на холсте, и я хочу нарисовать края между несколькими из них. Кроме того, края должны соединяться с точками на ящиках в определенных точках (т. Е. Ровно на 5 пикселей от верхней части левого края).

Я чувствую, что это проблема оптимизации, о которой раньше думали другие.

Answer 1

Похоже, вы заинтересованы в вычислении и минимизации числа пересечений графиков. Это проблема NP-Hard, here's - это не очень-то старое исследование этой проблемы, а Helena's Master's thesis - это всестороннее начало анализа алгоритмов проблемы числа пересечений графа.