Denkanstoß: Wie Verbindungen besser darstellen?

[Perlsau]

@silver-moon-2000
Da fallen mir spontan die Mitov-Komponenten ein, insbesondere OpenWire. Allerdings kann ich nicht viel dazu sagen, denn ich hab da nur mal vor längerer Zeit reingeschnuppert und noch nicht ernsthaft damit gearbeitet. Für nichtkommerzielle Anwendungen sind diese Komponenten kostenlos verwendbar.

[Dejan Vu]

Ich würde mir persönlich mal überlegen, was Du da machst: Die Verbindungen sind ja nicht der zentrale Punkt, sondern der Graph an sich. Ergo würde ich mir auch keine Gedanken über irgendwelche Verbindungsbibliotheken machen, damit das irgendwie hübsch aussieht. Beim Leiterplattendesign geht es ja gerade um die Verbindungen, und da ergibt das Sinn, aber bei dir eben nicht.

Ich kann mich dunkel daran erinnern, das die Entflechtungsalgorithmen, die die Teile umplazieren um überkreuzungen zu minimieren, nicht sonderlich schwer sind (Brute Force, soweit ich weiss), aber ich finde auf die Schnelle keinen Link (und ich kann mich auch irren).

Ich würde also eher so einen Algorithmus suchen und den einbauen. Beim Erstellen der Verbindungen mit der Maus würde ich jedoch keine direkte Linie verwenden, sondern eine, die nur aus senkrechten und waagerechten Linien besteht und möglichst wenig Ecken hat.

Vielleicht bringt es was, sich deine Leinwand als z.B. 100x100 Matrix vorzustellen und jede Zelle ist entweder eine Linie (senkrecht, waagerecht, Ecke) oder Teil eines Bausteins (Anschlusspunkt, sonstiges). Und schon kannst Du sehr sauber 'zeichnen'. Mit einem Algorithmus, der den 'optimalen' Weg von A nach B findet, solltest Du beim Layouten schon weit kommen. Die Regeln sind klar: Jede Ecke kostet und das überkreuzen auch.

[hstreicher]

Ich würde mir mal ansehen wie das Leiterplatten Entflechtungsprogramme machen ,
da darf sich ja auch nichts kreuzen

[himitsu]

Zitat von hstreicher:

Ich würde mir mal ansehen wie das Leiterplatten Entflechtungsprogramme machen ,
da darf sich ja auch nichts kreuzen

Doch, darf es, bei mehreren Ebenen.

Es darf auch mal ein verworrener Umweg sein, bzw. bestimmte Dinge müssen eine ganz bestimmte Länge haben (1), egal wo es lang geht und andere Leiter dürfen nicht nebeneinander liegen, oder sie dürfen schräg verlaufen und unter den Bausteinen hindurch ...
Und grade von denen verrät doch keiner wie er es macht, denn die wollen ja ihr Programm vekaufen.

PS: Selbst bei einer einseitigen Leiterplatte gibt es schon seit jahrzehnten möglichkeiten es dennoch zu kreuzen.
- 0 Ohm-Widerstände
- oder eine dünne Sperrschicht dazwischen (wird oft bei Tastaturlayouts angewendet, wo für die Gummyknöpfe eh eine weitere (Kontakt)Leiterschicht aufgetragen wird)


1: hohe Frequenzen, hohe Ströme oder gaaaanz kleine störanfällige Spannungen

[Dejan Vu]

Ich hab mir mal die Links von Perlsau angesehen. Das ist wirklich super! Da kreuzen sich die Bahnen, aber es ist trotzdem nicht unübersichtlich. Ich finde es auch wichtig (nervt mich bei ER-Tools), das *meine* visuelle Gruppierung der Elemente durch den Autorouter nicht durcheinander gewirbelt wird. Denn das nervt mehr, als eine Leitungen, die sich kreuzen.

Eigentlich muss der TE doch nur drauf achten, das
* Leitungen nicht 'hinter' anderen Klötzen verlaufen
* Kreuzungen irgendwie ordentlich gezeichnet werden, damit man sieht, was wohin verläuft.

[Namenloser]

Zitat von Dejan Vu:

Vielleicht bringt es was, sich deine Leinwand als z.B. 100x100 Matrix vorzustellen und jede Zelle ist entweder eine Linie (senkrecht, waagerecht, Ecke) oder Teil eines Bausteins (Anschlusspunkt, sonstiges). Und schon kannst Du sehr sauber 'zeichnen'. Mit einem Algorithmus, der den 'optimalen' Weg von A nach B findet, solltest Du beim Layouten schon weit kommen. Die Regeln sind klar: Jede Ecke kostet und das überkreuzen auch.

Genau so hatte ich das gemacht, hat sich nicht wirklich bewährt, wie oben beschrieben.

Edit: Im Anhang mal ein Screenshot. Das Ergebnis sieht schon ähnlich aus wie bei den Komponenten, die Perlsau verlinkt hat (nur weniger schön gezeichnet, z.B. keine abgerundeten Ecken). Das Hauptproblem ist halt, dass die Berechnung von Routen in dieser Qualität bei mir einfach viel zu lange gedauert hat.

[Dejan Vu]

Ah, ist also dein Wegfindealgorithmus suboptimal? Welchen verwendest Du denn? A* würde sich hier anbieten, wobei dem man das 'schräge' -also Zick-Zack- laufen einfach nur abgewöhnen müsste.

PS: Ist doch ordentlich... Bisserl mehr Mühe beim rendern, und schon ist das perfekt. Aber es ist auch so imho vollkommen ausreichend (die Verbindungen sollten halbdurchsichtig sein, das wäre noch besser)

[Namenloser]

Zitat von Dejan Vu:

Ah, ist also dein Wegfindealgorithmus suboptimal? Welchen verwendest Du denn? A* würde sich hier anbieten, wobei dem man das 'schräge' -also Zick-Zack- laufen einfach nur abgewöhnen müsste.

Das ist A*. Der Algorithmus braucht deshalb so lange, weil durch das komplizierte Qualitätsmaß einfach sehr viele mögliche Routen in Frage kommen und er deshalb sehr viele Möglichkeiten durchprobieren muss, bis die optimale Route gefunden ist. Beispiel: Setzt man die Bestrafung für eine Überkreuzung hoch, dann probiert natürlich er einen besseren Umweg zu finden. Je größer man die Bestrafung setzt, desto größer darf der Umweg sein, und das alles kostet eben Zeit. Im Endeffekt läuft A* hier fast auf Brute Force hinaus.

Dass er an den Ecken eine 45°-Kurve macht, ist gewollt. Das ist nicht der Zick-Zack-Fall, den ich meine. Der Zick-Zack-Fall tritt erst bei Platzmangel auf. Ich hab ihn im Anhang mal provoziert. Glaub mir, ich habe wirklich Tage damit verbracht, zu versuchen, ihm das abzugewöhnen, aber es kam immer zu noch schlimmeren Seiteneffekten.

Ich denke, man könnte den Algorithmus nur effizienter zu machen, indem man die Anzahl der in Betrachtung gezogenen Wegpunkte durch irgendeine Vorberechnung reduziert. Bisher wurde hier mit einem einfachen Raster gearbeitet. D.h. auch bei einer geraden Strecke gibt es dadurch sehr viele Abzweigungspunkte, die der Algorithmus ggf. durchprobiert. Wenn man die Anzahl der in Betrachtung gezogenen Punkte durch eine Vorberechnung einschränken würde, würde sich der Suchraum deutlich verkleinern, und dann wäre es vielleicht effizient machbar.