Стратегия соединения 2 точек без пересечения ранее нарисованных отрезков кривых

9

Я должен соединить пары точек без пересечения. Допустим, у меня есть две заданные точки, которые я соединяю с сегментом кривой. Затем снова выбираются две новые конечные точки, и эти новые точки также должны быть соединены, однако без пересечения ранее нарисованных кривых и т. Д. Для любого числа заданных пар точек.

Какой самый простой способ найти и нарисовать эти сегменты кривых?

user36552
источник
Линии или отрезки?
Мокоша
Важно только то, что две новые точки связаны, поэтому отрезки кривых тоже в порядке. Вопрос отредактирован.
user36552
2
Вы можете посмотреть на алгоритмы поиска пути для этого. Используйте существующие сегменты в качестве препятствий и найдите путь между двумя новыми конечными точками. Возможно, примените некоторое сглаживание к полученному пути, чтобы сделать его более привлекательным.
Натан Рид

Ответы:

6

Общая проблема называется рисованием графиков и не является легкой задачей.

Графы, которые можно нарисовать на плоскости без пересечений, называются плоскими , но не все графы являются плоскими: типичные графы, которые не являются плоскими, представляют собой полный граф на вершинах и полный двудольный граф на 6 вершинах , известный из-за проблемы с тремя утилитами .5K5K3,3

Вы можете попробовать Graphviz - Программное обеспечение для визуализации графиков для создания хороших рисунков.

Смотрите также

Szirmay-Kalos, László, Алгоритм динамической компоновки для отображения общих графиков , в Graphics Gems IV , 1994. code

Розати, Клаудио, Простой алгоритм соединения для двумерного рисования, Graphics Gems III , 1992, код .

LHF
источник
Другие инструменты включают YEd (бесплатно для использования, но не бесплатно), Gephi ... это трудная проблема NP.
Джуджаа