Algorytm QuickHull, działanie krokowe..

Odpowiedz Nowy wątek
2012-03-14 22:30

Rejestracja: 11 lat temu

Ostatnio: 5 lat temu

0

Witam, potrzebuje pomocy w przerobieniu algorytmu quickhull tak, aby każdy krok był wykonywany krok po kroku, ponieważ chcę to zademonstrować w postaci graficznej.

Klasa algorytmu dziedziczy po klasie

public abstract class Algorithm {
    public abstract void start(Vector v);

    /*
     * Wykonuje jeden krok algorytmu
     */
    public abstract void nextStep();

    /*
     * Zwraca true <=> algorytm zakonczony
     */
    public abstract boolean isDone();
}

jeden krok miałby się wykonywać w metodzie nextStep(), natomiast metoda start służy do inicjalizacji zmiennych i pobraniu wartości punktów.

To co do tej pory zrobiłem http://pastebin.com/efC0E56U

algorytm natomiast wygląda następująco: http://pastebin.com/5s4B46Sx

Pozostało 580 znaków

2012-03-14 22:57

Rejestracja: 11 lat temu

Ostatnio: 5 lat temu

0

oto pseudokod algorytmu

procedure otoczka(punkty)
        begin
                A := skrajny lewy punkt
                B := skrajny prawy punkt
                s1 := zbiór punktów po prawej stronie AB
                s2 := zbiór punktów po lewej stronie AB

                return [A] + QuickHull(A, B, s1) + [B] + QuickHull(B, A, s2);
        end;

procedure QuickHull(A, B, punkty)
        begin
                C := najbardziej odległy punkt od prostej AB
                s1 := zbiór punktów znajdujących się na prawo od prostej AC
                s2 := zbiór punktów znajdujących się na prawo od prostej CB

                return QuickHull(A, C, s1) + [C] + QuickHull(C, B, s2);
        end;

zastanawiam się jak rozłożyć ten algorytm skoro korzysta z rekurencji.

Pozostało 580 znaków

2012-03-15 05:30

Rejestracja: 11 lat temu

Ostatnio: 5 miesięcy temu

0

pseudokod do takich spraw

class Step {
     costam arg1, arg2;
     costam arg3, arg4;

    public Step(costam arg1, costam arg2, costam arg3, costam arg4)
    {
      this.arg1 = arg1;
      this.arg2 = arg2;
      this.arg3 = arg3;
      this.arg4 = arg4;
    }
}

Queue<Step> queue = new ArrayList<Step>();

next()
{
     Step s = queue.poll();
     hullSet(s.arg1, s.arg2, s.arg3, s.arg4);
}

hasNext()
{
   return !queue.isEmpty();
}

hullSet(costam A, costam B, costam set, costam hull)
{
   // bla bla bla
   // ...

   queue.offer(new Step(A,P,leftSetAP,hull))
   queue.offer(new Step(P,B,leftSetPB,hull))

}

mniej więcej chyba łapiesz koncept...

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0