Doppelt zeichnen vermeiden?

[23]

Hallo,

ich zeichne rekursiv einen Objektgraph und nun hab ich das Problem, dass ich öfter mal Linie doppelt zeichne. Kann mir jemand erklären wie man dieses Problem minimieren kann?

Der Objektgraph besteht aus Objekten die untereinander in Beziehung stehn. Jedes Objekt ist bereits auf einem Panel positioniert d.h. es gibt X und Y Koordinaten. Jedes Objekt hat mehrere Kinder. Es wird bei einem Objekt angefangen und dann wird vom 1. Kind eine Verbindung (Nicht direkt, sondern mit 2 Kanten) zum Parent gezeichnet. Alle nachfolge Kindobjekte werden dann als Pfad mit dem 1. verbunden.

Danach wird das selbe für die Kinder gemacht.

Viele Grüße

 

[Beni]

Nur eine Idee: Knoten ordnen (z.b. auch nach x/y) und Verbindung nur zeichnen, falls Start < Ende.

 

[Marco13]

Etwas zu schwamminge Beschreibung, als dass man "DIE" Antwort geben könnte. Notfalls beim Traversieren sowas wie

class Connection
{
    Object a, b;
    
    public int hashCode() { return a.hashCode() ^ b.hashCode(); }
    public boolean equals(Object object)
    {
        ...
        return 
            (a.equals(other.a) && b.equals(other.b)) || 
            (a.equals(other.b) && b.equals(other.a));
    }
}

und diese Connections in ein HashSet packen und dann alles zeichnen, was in den HashSet liegt.

 

[23]

ok werde ich mal versuchen.

Mal ein Pfad

x y
50,50
80,60
40,40

Das sind nun 3 Punkte d.h. 3 Objekte und der Pfad geht von 50,50 zu 80,60 dann von 80,60 zu 40,40

Wenn ich mir in einer HashMap die Punkte merke, gäbe es dann die Möglichkeit irgendwie bei jedem weiteren Punkt zu schauen ob der bereits Teil eines Pfades ist?

 

[Marco13]

Und dann...? Ein Knoten kann doch vermutlich z.B. auch 3 Kanten haben. Einfach aufzuhören, wenn man einen Punkt schon hatte, könnte evtl. nicht reichen...

 

[23]

class Node {
 int x;
 int y;
 List<Node> nodes = new ArrayList<Node>(); //Zyklus frei
}

Die Nodes sind bereits in einer MxN Matrix (Anderer Algo) angeordnet... in einer Zelle der Matrix können beliebig viele Nodes enthalten sein, Die Matrix kann je nach Auflösung die Nodes umbrechen...

 

[Beni]

Wenn ich mir in einer HashMap die Punkte merke, gäbe es dann die Möglichkeit irgendwie bei jedem weiteren Punkt zu schauen ob der bereits Teil eines Pfades ist?

Wenn die Verbindungen in beide Richtungen gehen, sollte sowas funktionieren. Dann würde der Code ungefähr so aussehen.

Für alle Knoten x
  Falls x nicht in Set  // eigentlich immer true, wenn es keine Zyklen gibt
    Für alle y verbunden mit x
      Falls y nicht in Set
        x-y zeichnen
    x in Set speichern

Das funktioniert natürlich nicht, wenn es Verbindungen gibt, die nur einem Knoten bekannt sind.

[Edit, das war wohl zu spät]

 

[23]

Also,

ich habe bereits eine Optimierung drin und zwar:

Wenn die Node A z.B. in [1,1] liegt und sagen wir 3 Kindernodes in [0,0] und 4 in [2,2] dann gibt es erstmal kein Problem. Dann wird von Kante Oben eine Verbinding zum 1. Kind in [1,1] gezeichnet. Die Kinder sind dann als Pfad direkt verbunden. Von Kante Rechts wird eine Verbindung zum 1. Kind in [2,2] gezeichnet.

So das Problem ensteht wenn die Rekursion eins tiefer geht und zwar: Beispiel hätte das 4. Kind in [0,0] wieder Kinder würde quasi die gleiche Zeichenlogik nochmal durchgespielt und dabei wird dann in komplexen Beziehung leider mal was doppelt gezeichnet.

 

[23]

Würde es was bringen wenn ich eine Adjazenzmatrix erstellen würde?
Es wäre kein Problem die Parents einer Node zu finden (Eine Node kann N Kinder und N Parents haben)

 

[23]

Etwas zu schwamminge Beschreibung, als dass man "DIE" Antwort geben könnte. Notfalls beim Traversieren sowas wie

class Connection
{
    Object a, b;
    
    public int hashCode() { return a.hashCode() ^ b.hashCode(); }
    public boolean equals(Object object)
    {
        ...
        return 
            (a.equals(other.a) && b.equals(other.b)) || 
            (a.equals(other.b) && b.equals(other.a));
    }
}

und diese Connections in ein HashSet packen und dann alles zeichnen, was in den HashSet liegt.

Kannst du das noch genauer ausführen?

Also wie soll icj genau vorgehen? Danke

 

[Marco13]

WIe sind denn "Verbindungen" im Moment repräsentiert? Hat einfach jedes Objekt eine Liste von Children? Willst du (mal ganz direkt gefragt) einfach nur einen Graphen zeichnen?

 

[23]

Ja genau jede Node hat eine List mit Kindern und Parents.
Es sollen immer die Kinder gezeichnet werden und dann deren Kinder usw.

Es ist allerdings kein Baum, da die Nodes schon in einer Matrix angeordnet sind.

 

[Marco13]

Alles schrecklich unpräzise, und ich bin übermüdet, aber wenn die Knoten eh schon einer Matrix angeordnet sind, malt man einfach alle Verbinungen, die in dem Teil oben rechts oder unten links (bzgl. der Diagonalen der Matrix) stehen...? Wenn nicht muss ich morgen nochmal schauen...

 

[23]

Hi,

ja das mache ich auch schon jedoch ist die Matrix groß d.h. eine Node in einer Celle kann Verbindungen in mehr als nur die acht direkten Nachbarn haben

 

[Marco13]

Ich dachte du meinst eine Adjazenzmatrix Repräsentation von Graphen im Computer ? Wikipedia

Ein bißchen Code (am besten KSKB ) zu posten würde vermutlich helfen.

 

[23]

Hi,

sorry für die späte Antwort. Also stellt euch ein Schachbrett vor wie hier: http://www.schach-lernen.de/grafik/schach.gif

Das ist das Raster mit Zeilen und Spalten d.h. es gibt Zellen. In einer Zelle können mehere Nodes enthalten sein.

Die Breite der Spalten wird berechnet d.h. alle Spalten sind z.B. 400Pixel breit. Eine Node ist z.B. 150Pixel breit. Die Anordnung der Nodes in den Zellen ist von links nach rechts mit Umbruch.

Die Einsortierung der Nodes in das Raster wird von einem eigenen Algo vorgenommen.

Wie bereits erwähnt haben die Nodes Kinder und Eltern => Beziehungen. Wenn man nun eine Node auswählt sollen alle Kindbeziehungen "schön" eingezeichnet werden. Wenn ein Kind auch Kinder hat soll dies ebenfalls gezeichnet werden. Im Prinzip wie ein Baum jedoch das die Nodes halt nicht wie ein Baum gelayoutet sind da sie sich ja in dem Raster befinden.

Breite, Höhe des Raster, Höhe der Zeilen, Breite der Spalten, Breite, Höhe, Position der Nodes sind alle verfügbar.


Beim Zeichnen sollte es nach Möglichkeit keine Überschneidungen geben und wenn das die Beziehung zu lässt können auch Wege verbunden werden, d.h. wenn in Zelle [2,0] die Elternnode liegt und in [0,1] und [1,1] jeweils Kinder dann könnte man auch einen Weg zeichnen bis zu einem gewissen Punkt der dann verzweigt zu den Kindnodes...

Ich hoffe nun ist es verständlicher

 

[Marco13]

Es scheint sehr schwierig zu sein... Hat das Schachbrett (HEY, das Hat ja 8x8 Felder! Und alle Quadratisch!) irgendwas mit dem Problem der doppelt gezeichneten Linien zu tun? Poste am besten mal ein KSKB mit einer Zeile

// Hier das wird doppelt gemacht, soll aber nur einmal gemacht werden

 

[23]

Es gibt nur das Einsortieren und das ist wirklich nicht sehenswert...

Es geht ja drum eine Lösung zu finden...

Ein Ansatz ist:

Für jedes Kind eine Linie mit zwei Kanten zuzeichen (Also von Parent zu Kind)
und am Parent und auch Kind die Anzahl der Eingänge bzw. Ausgänge zu merken...
Weiterhin könnte man Kinder die in gleichen Zellen liegen direkt miteinandern verbinden d.h. Kind D,B,C sind untereinander verbunden und B ist mit der Parent Node verbunden.

 

[Marco13]

Sorry, aber ... das wäre schon fast eine Umfrage wert, "Weißt du was hier gemeint ist?", und ich tippe auf >90% "Nein". Jetzt kommen noch abstrakte Begiffe wie "Schönheit" dazu, und dicke Bretter wie "Überschneidungsfreiheit" - bisher ging es ja nur darum, dass du ausführlichst

private void drawStuff(Node node)
{
    for (Node child : node.getChildren())
    {
        drawLine(node, child);
        drawStuff(child);
    }
}

beschrieben hast, und nicht gesagt hast, warum das nicht das ist, was du suchst.

Ich glaube, ich bin raus... :bahnhof:

 

[23]

Hm was verstehst du nicht? Ich habs doch jetzt ausführlich erklärt.

 

[Marco13]

Auch wenn manche Menschen es als unhöflich empfinden, eine Frage mit einer Gegenfrage zu beantworten: Was verstehst du denn an den vorgeschlagenen Lösungen nicht?

 

[André Uhres]

Hallo 23,

ich glaube nicht, dass sich Überschneidungen vermeiden lassen, oder dass so was überhaupt schön aussehen kann. Ich würde wahrscheinlich einfach die Knoten mit passenden Farben einfärben und keine Linien zeichnen. Ich meine, nur den Vater und seine direkten Kinder einfärben, wobei erkennbar sein muss, ob eine Kind ein Blatt ist oder nicht. So kann man, wenn nötig, Unterknoten auf und zu klappen, um einen Pfad zu verfolgen.

Gruß,
André

 

[Marco13]

Bei einem Baum lassen sie sich natürlich vermeiden. Die sekundäre Frage wäre, wie aufwändig das im speziellen Fall ist. Die primäre Frage wäre: Geht es überhaupt um einen Baum? (Ja, nodes mit parents und children, aber dann noch die Linien und da Kindeskinder und überhaupt ist das ja in einem Schachbrett angeordnet ... sorry, ich kapier's einfach nicht - mal' vielleicht mal ein Bild.... )