Elektrisch ladekanten in einem Kraft-basierten Diagrammzeichnungsalgorithmus?

Question

Ich versuche, ein kurzes Miniprogramm in Python zu schreiben, das mit dem herumspielt Kraftbasierte Algorithmen Für die Grafikzeichnung.

Ich versuche, die Häufigkeit zu minimieren, die Linien überschneiden. Wikipedia schlägt vor, den Linien eine elektrische Ladung zu verleihen, damit sie sich gegenseitig abwehren. Ich fragte meine Physiklehrerin, wie ich das simulieren könnte, und sie erwähnte mit Calculus mit Coulombs Gesetz, aber ich bin mir nicht sicher, wie ich anfangen soll.

Könnte mir jemand einen Hinweis darauf geben, wie ich das machen könnte? (Oder alternativ eine andere Möglichkeit, einen Kraft-Basis-Graph-Zeichnungsalgorithmus zu optimieren, um die Häufigkeit der Linien zu minimieren?) Ich suche nur nach einem Hinweis. Bitte kein Quellcode.

Falls jemand interessiert ist, mein Quellcode und ein YouTube Vid Ich habe darüber gemacht.

Answer 1

Sie müssen explizit einen Begriff in Ihre Kostenfunktion aufnehmen, der die Anzahl der Kantenübergänge minimiert. Zum Beispiel für jedes Paar von Kanten, die überqueren, entstehen eine feste Strafe oder, wenn die Kanten gewichtet werden, eine Strafe, die das Produkt der beiden Gewichte entspricht.