![[HaBo]](/styles/default/logoklein.png){kind=small}
Hiho.
zur Zeit stellt sich uns folgendes Problem:
(vorweg, das Programm dient zur Visualisierung von Graphenalgorithmen)
Stellt euch in einem Java Programm eine Zeichenflaeche vor, in dieser Flaeche liegen
sagen wir ca. 200 Knotenobjeke (Ableitungen von JComponent, optisch sind das einfach nur 40x40 grosse Kreise) beliebig angeordnet. Von diesen Knoten aus gehen zu beliebigen anderen Knoten gerichtete Kantenobjekte (auch Ableitungen von JComponent) .. also optisch kann man sich das so vorstellen, 200 Kreise beliebig angeordnet und im Extremfall fuehrt von jedem Kreis zu alle anderen jeweils eine Kante (einfach nur eine Linie mit Pfeilspitze) ... soweit erstmal klar hoffe ich.
Die Kanten sind von JComponent abgeleitet damit sie Mausereignisse empfangen koennen, Problem dabei ist natuerlich das ein JComponent a) im Prinzip ein riesiges Rechteck ist (aber nur die Linie diagonal durch das Rechteck interessiert) und b) sich diese Kantenobjekte sehr leicht ueberlagern, aber nur das oberste Objekt das Mausereignis erhaelt. Noch gesagt werden muss, dass alle Kanten um ihre "Linie" herum ein unsichtbares Polygon verwalten das fuer die Mausklickerkennung dient.
Weiterhin liegen diese Kanten in einem JLayeredPane, wodurch man eine Z-Ordnung auf allen Kanten erhaelt. Die bisherige Loesung sieht wie folgt aus: die Kante die das Mausereignis erhaelt prueft zunaechst ob ihr eigenes Polygon getroffen wurde, wenn nicht prueft sie die Polygone aller Kanten die sie selbst ueberlagert (eben wegen der Z Ordnung geht das recht effizient) und reicht ggfs das Mausereignis weiter. Dieser 'Mechanismus' wird a) dafuer benutzt das man Kanten direkt anklicken kann als User und weiterhin Kanten auch 'gehighlighted' werden... dh. wenn der User mit Maus ueber eines dieser Polygon faehrt blinkt die Linie auf.
Ok, das Ganze klappt soweit schon sehr gut... allerdings nur fuer kleinere Graphen (mit wenigen Kantenobjekten... so bis 1.000-3.000 stueck oder so) . Bei grossen Graphen mit sagen wir 10.000 Kanten wuerde das Ganze prinzipiell auch noch funktionieren, allerdings stoesst Java dabei an seine Grenzen... allein das Hinzufuegen (also JLayeredPane.add(blaa); ) dieser 10k Kanten dauert mehrere Minuten und Java wird im Prozessmonitor dann mit 200+ MB an Speichernutzung gelistet.
Das Problem bzw die Frage ist jetzt wie man das Ganze auch bei sehr vielen Kanten noch effizient loesen kann? Bedingung ist das man die Kanten nach wie vor zumindest direkt anklicken kann (auf Highlighting verzichten wir zur Not)
Bisherige Ideen von uns waren folgende, einmal koennte man die Kanten direkt durch die Zeichenflaechen zeichnen lassen (dadurch erspart man sich den riesen Overhead den die Ableitung von JComponent mit sich bringt)... das Problem dabei ist natuerlich das die Kanten a) dann keine Mausevents mehr bekommen und man mehr oder minder bei jedem Mausklick _alle_ Kanten auf "getroffen-worden-sein" testen muss. Bei 40k Kanten dauert das ca. 3 sekunden (2.6 Ghz Rechner)... also unakzeptabel langsam. Dadurch das man die Kanten direkt zeichnet verliert man ja zudem auch die Z-Ordnung so das man immer alle testen muss.
Eine andere Idee war, alle Kanten in einem einzigen Objekt welches von JComponent abgeleitet worden ist zu verwalten.. hat so ca. diesselben Schwaechen wie die Direkt-Zeichnen Loesung.. man hat nur direkt die MausEvents und ein paar nuetzliche Methoden die Jcomponent mitbringt.
Ein weiterer riesen Nachteil beider Ansaetze ist das das effiziente Zeichnen extrem schwierig wird (einfach immer _alle_ Kanten zu zeichnen ist indiskutabel)..
So... hoffe es ist klar geworden worum's sich dreht (ansonsten ruhig nachfragen)... vielleicht stand jemand schon mal vor einem aehnlichen Problem und/oder hat eine gute Loesung parat?
zur Zeit stellt sich uns folgendes Problem:
(vorweg, das Programm dient zur Visualisierung von Graphenalgorithmen)
Stellt euch in einem Java Programm eine Zeichenflaeche vor, in dieser Flaeche liegen
sagen wir ca. 200 Knotenobjeke (Ableitungen von JComponent, optisch sind das einfach nur 40x40 grosse Kreise) beliebig angeordnet. Von diesen Knoten aus gehen zu beliebigen anderen Knoten gerichtete Kantenobjekte (auch Ableitungen von JComponent) .. also optisch kann man sich das so vorstellen, 200 Kreise beliebig angeordnet und im Extremfall fuehrt von jedem Kreis zu alle anderen jeweils eine Kante (einfach nur eine Linie mit Pfeilspitze) ... soweit erstmal klar hoffe ich.
Die Kanten sind von JComponent abgeleitet damit sie Mausereignisse empfangen koennen, Problem dabei ist natuerlich das ein JComponent a) im Prinzip ein riesiges Rechteck ist (aber nur die Linie diagonal durch das Rechteck interessiert) und b) sich diese Kantenobjekte sehr leicht ueberlagern, aber nur das oberste Objekt das Mausereignis erhaelt. Noch gesagt werden muss, dass alle Kanten um ihre "Linie" herum ein unsichtbares Polygon verwalten das fuer die Mausklickerkennung dient.
Weiterhin liegen diese Kanten in einem JLayeredPane, wodurch man eine Z-Ordnung auf allen Kanten erhaelt. Die bisherige Loesung sieht wie folgt aus: die Kante die das Mausereignis erhaelt prueft zunaechst ob ihr eigenes Polygon getroffen wurde, wenn nicht prueft sie die Polygone aller Kanten die sie selbst ueberlagert (eben wegen der Z Ordnung geht das recht effizient) und reicht ggfs das Mausereignis weiter. Dieser 'Mechanismus' wird a) dafuer benutzt das man Kanten direkt anklicken kann als User und weiterhin Kanten auch 'gehighlighted' werden... dh. wenn der User mit Maus ueber eines dieser Polygon faehrt blinkt die Linie auf.
Ok, das Ganze klappt soweit schon sehr gut... allerdings nur fuer kleinere Graphen (mit wenigen Kantenobjekten... so bis 1.000-3.000 stueck oder so) . Bei grossen Graphen mit sagen wir 10.000 Kanten wuerde das Ganze prinzipiell auch noch funktionieren, allerdings stoesst Java dabei an seine Grenzen... allein das Hinzufuegen (also JLayeredPane.add(blaa); ) dieser 10k Kanten dauert mehrere Minuten und Java wird im Prozessmonitor dann mit 200+ MB an Speichernutzung gelistet.
Das Problem bzw die Frage ist jetzt wie man das Ganze auch bei sehr vielen Kanten noch effizient loesen kann? Bedingung ist das man die Kanten nach wie vor zumindest direkt anklicken kann (auf Highlighting verzichten wir zur Not)
Bisherige Ideen von uns waren folgende, einmal koennte man die Kanten direkt durch die Zeichenflaechen zeichnen lassen (dadurch erspart man sich den riesen Overhead den die Ableitung von JComponent mit sich bringt)... das Problem dabei ist natuerlich das die Kanten a) dann keine Mausevents mehr bekommen und man mehr oder minder bei jedem Mausklick _alle_ Kanten auf "getroffen-worden-sein" testen muss. Bei 40k Kanten dauert das ca. 3 sekunden (2.6 Ghz Rechner)... also unakzeptabel langsam. Dadurch das man die Kanten direkt zeichnet verliert man ja zudem auch die Z-Ordnung so das man immer alle testen muss.
Eine andere Idee war, alle Kanten in einem einzigen Objekt welches von JComponent abgeleitet worden ist zu verwalten.. hat so ca. diesselben Schwaechen wie die Direkt-Zeichnen Loesung.. man hat nur direkt die MausEvents und ein paar nuetzliche Methoden die Jcomponent mitbringt.
Ein weiterer riesen Nachteil beider Ansaetze ist das das effiziente Zeichnen extrem schwierig wird (einfach immer _alle_ Kanten zu zeichnen ist indiskutabel)..
So... hoffe es ist klar geworden worum's sich dreht (ansonsten ruhig nachfragen)... vielleicht stand jemand schon mal vor einem aehnlichen Problem und/oder hat eine gute Loesung parat?
