Я работаю над этим проектом, где мы генерируем изображения из ориентированного графа.Вершины в графе размечаются с помощью алгоритма позиционирования, а ребра (или коннекторы) размечаются после.
Оптимальный путь коннекторов уже рассчитан с помощью алгоритма A *, и это прекрасно работает.Примечание: «оптимальный» зависит от имеющейся у нас блок-схемы и является «оптимальным» в визуальном аспекте, а не в необработанном расстоянии.
Также важно отметить, что у нас нет никакого представления о реальных пикселях раньшерендеринг.Каждая вершина расположена в целочисленной (x, y) позиции, а соединители - это просто списки, содержащие дроби для позиций.Фракции, потому что наши соединители перемещаются «между» ячейками сетки, и мы ограничиваем перемещения до 1/2.Каждый угол является прямым углом.
Таким образом, переход от (1,1) к (3, 2) соединителю будет выглядеть просто: [(1,1), (3 / 2,1), (2,1), (5 / 2,1), (3,1), (3,3 / 2), (3,2)].
Это прекрасно работает.
Для линий, которые запускают parellel в некоторых разделах, я сделал простой алгоритм, который присваивает каждому разделу соединителя (раздел, являющийся прямой частью между двумя углами) индекс.Таким образом, 4 параллельных сегмента будут иметь индексы 0..3.
На этапе рендеринга эти простые целые числа и дроби отображаются в пикселях, определяя смещение для параллельных индексов.
Теперь проблема: в случае множества параллельных линий (> 10) смещениеначинает разрушаться, так как общая ширина параллельных линий начинает превышать ширину визуализированной вершины.Кроме того, необходимо несколько оптических улучшений:
- Прямые линии без углов должны быть в середине набора линий.Или как можно ближе.
- Набор параллельных разъемов, идущих за углом, должен сохранять свое соответствующее положение внутри нашей внешней стороны кривой.Таким образом, если 10 разъемов идут вверх, а затем направо, самый левый разъем должен находиться сверху после изгиба, а самый правый разъем должен быть снизу после изгиба.
IПри рассмотрении программного обеспечения для блок-схем и особенно программного обеспечения для электрических диаграмм осознайте, что эта проблема решается многими людьми.
Итак, мой вопрос к вам: Существует ли известный алгоритм для упорядочения сегментов?в таком случае использования? Я искал в Интернете, но я нахожу только инструменты, связанные с принципиальными схемами и простыми блок-схемами.
Конечно, большинство алгоритмов не являются раскрытыми, что я совсем не против.Мне нужно адаптировать его к моим потребностям.
РЕДАКТИРОВАТЬ : я нашел эту ссылку сейчас: http://cs.brown.edu/people/rtamassi/papers/gd-tutorial/gd-constraints.pdf, которая содержит много литературных данных.Посмотрим на это: -)