Wege optimieren

[L.a.r.s.]

Hallo ich habe folgendes Problem:

_0 1 2 3 4 5 6
0*
1...*
2......*
3........*
4...........*
5...........*
6...........*

Ich habe einen Vektor nennen wir ihn mal weg in dem lauter Punkte in Form von Tupeln stehen. Die Methode Tupel stellt die Funktion getX und getY zur Verfügung. So nun hat der Vektor z.b. wie ich in dem Bild versucht habe zu zeigen einen diagonalen Weg der aus den Punkten (0,0), (1,1), (2,2), (3,3), (4,4) besteht. Um diese Strecke zu fahren würde aber der Punkt (0,0) und der Punkt(4,4) reichen. Ich will also überflüßige Punkte aus dem Vektor streichen.
So meine Idee war nun:

ich nehme den ersten Punkt und schaue ob die X und die Y Koordinate des nächsten Punktes beide eins größer geworden sind und wenn ja schau ich den nächsten an. Ist dies beim nächstren wieder der Fall kann ich den mittleren löschen.
etwa so:

if(weg.elementAt(0).getX()+1==weg.elementAt(1).getX() && weg.elementAt(0).getY()+1==weg.elementAt(1).getY())
wenn ja gehe zum nächsten 
if(weg.elementAt(0).getX()+1==weg.elementAt(2).getX() && weg.elementAt(0).getY()+1==weg.elementAt(2).getY())
wenn ja lösche Tupel(1,1)
uns so weiter..

Ok nun meine Frage. Wie kann ich das am besten realisieren? Wie könnte ich z.B. den ersten Punkt speichern um ihn dann mit den nächsten zu vergleichen.

Schon mal im voraus vielen Dank!

 

[bambi]

Mal eine Idee:

Ist es nicht einfacher, wenn du statt +1 vergleichst - lieber mit der Steigung rechnest? Dann kannst Du Deine Methode auch noch fuer andere Moeglichkeiten einsetzen...

Also jetzt zu Deiner Frage: warum erzeugst du dir nicht einfach einen ergebnis-vektor? da kannst du dann ja alle punkte einfuegen, die nicht auf einer linie liegen - also immer den ersten und den letzten punkt auf jeden fall - und dann noch alle punkte, an denen sich deine linie kruemmt... war das so gemeint?

 

[L.a.r.s.]

Hey das mit der Steigung hört sich gut an. Ich brauch die Funtion eh noch für horizontale und vertikale Bewegungen. Außerdem hätte ich dann eine Funktion für fallende oder steigende Diagonalen.

Hmm an einem Ergebnis Vektor hab ich schon auch gedacht. Ich hab eben nur noch gar keine Idee wie ich das dann speicher. Mir fällt ja immer erst auf, dass sich die Steigung änert wenn ich schon beim nächsten Tupel bin. Dann müsste ich ja wieder zurück. Und da weiß ich nicht genau wie ich das am schlausten mach.

 

[bambi]

leg dir doch einfach ein paar variablen vom typ tupel an. und dann sowas wie

1. schreibe t1 in ergVektor
2. vergleiche t1 mit t2
3. schreibe t2 in tzwischen
4. vergleiche t2 mit t3
4a steigung gleich:
mach nix
4b steigung geaendert:
schreibe tzwischen in ergVektor
5. tzwischen = t3
etc

so ungefaehr vielleicht?

 

[L.a.r.s.]

Ok ich glaub jetzt hab ichs. Den tzwischen Vektor lösch ich dann einfach jedesmal bevor ich wieder einen Punkt einfüge oder besser gesagt tzwischen muss kein Vektor sein sondern nur ein Punkt der eben den letzten speichert. Und sobald sich die Steigung ändert hab ich meinen letzten Punkt.

Danke!!

 

[Bleiglanz]

warum nicht nicht den ganzen pfad auf einmal bereinigen

gegeben (p0,.....,pn)

for i=1...n-1 // geht nicht weil n sich ändert....
while(pi auf der geraden p(i-1)-p(i+1))
{   
    entferne p(i) // aufpassen wegen des entfernens aus Collections
    // und der index ändert sich usw.
}