[lnkForumImage]
TotalShareware - Download Free Software

Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

pl.comp.programming

Algorytm rysowania drzewa

Verne

5/17/2007 11:02:00 AM

Witam,

Zalózmy, ze mam w pamieci strukture drzewiasta (kazdy element ma
wskaznik na ojca i liste swoich synów).
Moim zadaniem jest jak najladniej i najbardziej przejrzyscie
zwizualizowac to drzewko.
Efektem koncowym powinny byc wspólrzedne dla kazdego wezla tak by
uzyskac po narysowaniu przejrzysty rysunek o strukturze ponizej :

w
|
_____
| |
w w
|
____
| |
w w

Ogólnie rzecz biorac wiem jak to zrobic. Wystarczy rozmiescic
odpowiednio wezly terminalne i pózniej propagowac wspólrzedne w góre
drzewa. Nawet mam dzialajacy kod. Niestety jest jeden problem ..
algorytm jest za wolny. Java nie jest w stanie poradzic sobie z okolo
2000 tysiacami takich wezlów gdy doda sie jakis nowy (jest widoczne
opóznienie, a ja potrzebuje czegos co by dzialalo w czasie
rzeczywistym).
Bede wdzieczny za informacje czy istnieja jakies algorytmy czy tez
problemy algorytmiczne podobne do mojego.
Najlepiej jakies z rozwiazaniami :)

Pozdrawiam,

Wojtek

6 Answers

Zbyszek Malec

5/17/2007 11:16:00 AM

0

Dnia 17 May 2007 04:02:07 -0700, Verne napisa3(a):

> Nawet mam dzia3aj?cy kod. Niestety jest jeden problem ..
> algorytm jest za wolny. Java nie jest w stanie poradzia sobie z oko3o
> 2000 tysi?cami takich wez3ów gdy doda sie jaki? nowy (jest widoczne
> opó?nienie, a ja potrzebuje czego? co by dzia3a3o w czasie
> rzeczywistym).

Poka? jak rysujesz.

--
Zbyszek Malec Ustronie 104
jid: zbyszanna@chrome.pl

Verne

5/18/2007 8:15:00 AM

0

Witam,

Udalo mi sie troche poprawic mój kod. W zasadzie jest juz
wystarczajaco wydajny by móc go uzywac
w czasie rzeczywistym. Ale nie jestem zadowolony z efektów jakie
generuje. Tzn powstaje za duzy
rozrzut pomiedzy obiektami jesli wystepuje duzo wezlów terminalnych.
Dlatego zapytalem o jakies standardowe rozwiazania tego problemu bo
nie mam pomyslu jak inaczej mozna
to zrobic by uzyskac jak najczytelniejsze (i latwe w nawigacji)
wizualne odwzorowanie struktury.


> Pokaz jak rysujesz.

Przed wywolaniem ponizszej metody ustawiam wszystkim obiektom
wlasciwosci formated na false.
getChildsMidddleX() - jak sama nazwa wskazuje pobiera srodek (a
dokladniej srednia ze wspolrzednych
pierwszego i ostatniego dziecka)

int termNumber = 0;
private void placeBlocks(DObject obj, int deep){
deep+=1;
Vector v = obj.getAllChildren();
DObject next = null;
for(ListIterator it = v.listIterator();it.hasNext();){
next = (DObject)it.next();
if(next.getAllChildren().size() == 0){

next.setx((SPACEX + next.getWidth()) * (termNumber) +
next.getWidth()/2);
next.sety((deep+1) * (next.getHeight() + SPACEY));
next.setFormated(true);
termNumber++;
continue;
}
placeBlocks(next,deep);
}
if(obj.areAllChildsFormated() && !obj.isFormated()){
obj.setx(obj.getChildsMidddleX());
obj.sety(obj.getChildsMidddleY() - obj.getHeight() - SPACEY);
obj.setFormated(true);
}
}



Zbyszek Malec

5/18/2007 12:11:00 PM

0

Dnia 18 May 2007 01:14:55 -0700, Verne napisa3(a):

> int termNumber = 0;
> private void placeBlocks(DObject obj, int deep){
> deep+=1;
> Vector v = obj.getAllChildren();

Musi bya Vector? Nie mo?e bya ArrayList? Zyska3by? pare milisekund. Je?li
to jest 1.5 to dodatkowo lista generyczna, czyli:
List<DObject> children = obj.getAllChildren();

> DObject next = null;
> for(ListIterator it = v.listIterator();it.hasNext();){
> next = (DObject)it.next();

Je?eli to jest java 1.5 to proponuje:
for(DObject child : children) {

> if(next.getAllChildren().size() == 0){
>
> next.setx((SPACEX + next.getWidth()) * (termNumber) +
> next.getWidth()/2);
> next.sety((deep+1) * (next.getHeight() + SPACEY));
> next.setFormated(true);
> termNumber++;
> continue;
> }
> placeBlocks(next,deep);
> }
> if(obj.areAllChildsFormated() && !obj.isFormated()){
> obj.setx(obj.getChildsMidddleX());
> obj.sety(obj.getChildsMidddleY() - obj.getHeight() - SPACEY);
> obj.setFormated(true);
> }
> }

Dalej nie pokaza3e? jak malujesz. W ka?dym razie kiedy wywo3ujesz t?
metode? Za ka?dym odmalowaniem? Ja bym sobie zrobi3 jaki? wewnetrzny bufor
do malowania (BufferedImage) i przy zmianie struktury drzewa odmalowywa3bym
ten bufor, a w metodzie odmalowywania komponentu wrzuca3bym ten bufor na
ekran. W ten sposób nie powiene? miea wiekszych problemów z wydajno?ci?.

--
Zbyszek Malec Ustronie 104
jid: zbyszanna@chrome.pl

Verne

5/18/2007 12:30:00 PM

0


> Musi byc Vector? Nie moze byc ArrayList? Zyskalbys pare milisekund. Jesli
> to jest 1.5 to dodatkowo lista generyczna, czyli:
> List<DObject> children = obj.getAllChildren();

Niestety ze wzgledów technicznych to musi byc Java 1.3.1.

> Jezeli to jest java 1.5 to proponuje:
> for(DObject child : children) {

Ciekawa konstrukcja, pierwszy raz ja widze...
Jak sie nazywa ?
Zgaduje ze zostalo wprowadzone od wersji 1.5 dopiero :)

> Dalej nie pokazales jak malujesz. W kazdym razie kiedy wywolujesz ta
> metode? Za kazdym odmalowaniem? Ja bym sobie zrobil jakis wewnetrzny bufor
> do malowania (BufferedImage) i przy zmianie struktury drzewa odmalowywalbym
> ten bufor, a w metodzie odmalowywania komponentu wrzucalbym ten bufor na
> ekran. W ten sposób nie powienes miec wiekszych problemów z wydajnoscia.

Dokladnie tak robie. Odmalowywuje bufor (nawet nie musze go robic ...
swing zalatwia za mnie spraw)
Przed optymalizacja (powyzsza metoda wygladala duzo gorzej :)) edycja
drzewka byla bardzo uciazliwa.
Aha zapomnialem wspomniec ze tworze edytor wiec operacja zmiany drzewa
bedzie sie zdarzac dosc
czesto :). Teraz juz nie jest tak zle, ale zawsze podobno mozna
lepiej :)

Poza tym tak jak wspominalem w nastepnym poscie nie do konca jestem
zadowolony z efektów tego
algorytmu. Daje za duzy rozrzut i nawigacja po tym drzewku z 2000
elementów jest niewygodna.
(duzo scrollowania po pustych przestrzeniach gdzie nic nie ma :) )

Zbyszek Malec

5/18/2007 1:08:00 PM

0

Dnia 18 May 2007 05:30:27 -0700, Verne napisa3(a):

> Dok3adnie tak robie. Odmalowywuje bufor (nawet nie musze go robia ...
> swing za3atwia za mnie spraw)
> Przed optymalizacj? (powy?sza metoda wygl?da3a du?o gorzej :)) edycja
> drzewka by3a bardzo uci??liwa.
> Aha zapomnia3em wspomniea ?e tworze edytor wiec operacja zmiany drzewa
> bedzie sie zdarzaa do?a
> czesto :). Teraz ju? nie jest tak ?le, ale zawsze podobno mo?na
> lepiej :)

Tak z ciekawo?ci, poka? swoj? metode paint.

--
Zbyszek Malec Ustronie 104
jid: zbyszanna@chrome.pl

Maciej Pilichowski

5/20/2007 6:46:00 AM

0

On 17 May 2007 04:02:07 -0700, Verne <wojciech.klicki@gmail.com>
wrote:

>Bede wdzieczny za informacje czy istniej? jakie? algorytmy czy te?
>problemy algorytmiczne podobne do mojego.
>Najlepiej jakie? z rozwi?zaniami :)

Graphiz.

milego dnia zycze, hej
--
Maciej "MACiAS" Pilichowski http://bantu.fm.i...