Электрически заряженные ребра в алгоритме рисования графа на основе силы?

Question

Электрически заряженные ребра в алгоритме рисования графа на основе силы?

Я пытаюсь написать короткую мини-программу на Python, которая использует алгоритмы, основанные на использовании силы, для рисования графиков.

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

Может ли кто-нибудь дать мне подсказку о том, как я могу это сделать? (Или, в качестве альтернативы, другой способ настройки алгоритма рисования графиков на основе силы, чтобы минимизировать количество пересечений линий?) Я просто ищу подсказку; нет исходного кода, пожалуйста.

На случай, если кому-то интересно, я сделал мой исходный код и видео с YouTube.

1

language-agnostic physics graph-algorithm graph-drawing

Источник

user646543 19 фев '12 в 06:15

1 ответ

Решение

Другие вопросы по тегам language-agnostic physics graph-algorithm graph-drawing

user160074 20 фев '12 в 14:09 2012-02-20 14:09 · Accepted Answer · 2012-02-20 14:09

Вам необходимо явно включить термин в вашу функцию стоимости, которая минимизирует количество пересечений ребер. Например, за каждую пару ребер, которые пересекаются, вы получаете фиксированный штраф или, если ребра взвешены, вы получаете штраф, который является произведением двух весов.