performance frage

cooky451

kantaki schrieb:

hat jemand vielleicht optimierungsvorschläge?

Du musst dich immer noch auf Straßen fortbewegen! (Jede Kreuzung ist dann ein Punkt.)

kantaki

cooky451 schrieb:

kantaki schrieb:

hat jemand vielleicht optimierungsvorschläge?

Du musst dich immer noch auf Straßen fortbewegen! (Jede Kreuzung ist dann ein Punkt.)

nein, jede koordinate liegt auf einem weg.
das einzige problem ist das es nicht den kürzesten weg nimmt, sondern immer nur den zielwegpunkt mit der luftdistanz zum ziel berechnet.
Naja zumindest kommt man zum Ziel.
aber die berechnung dauert schon sehr sehr lange

gibt es vielleicht eine alternative zum vector?

SeppJ

kantaki schrieb:

gibt es vielleicht eine alternative zum vector?

vector ist die mit Abstand schnellste Datenstruktur überhaupt. Wie wäre es stattdessen mal damit, auf die vielen guten Tipps zu hören die dir hier gegeben wurden, anstatt auf deiner Vorgehensweise zu beharren?

brotbernd

Du zeigst immer nur irgendwelche uusammenhangslosen Codefetzen und erklärst überhautp nicht was Du da überhaupt machst.
Auch wenn es mit Sicherheit ziemlich Quatsch ist, erklär doch bitte mal nach welchen Regeln Du den nächsten WP suchst.
http://img17.imageshack.us/img17/5426/appwb.jpg

Wieso nimmst Du da WP1 und nicht direkt WP5 (oder noch besser direkt WP6). Das ist doch dann ein viel kürzerer Weg. Das ist in Realität natürlich totaler Blödsinn, weil es mit Sicherheit keine direkte Straße von WP0 nach WP5 gibt. Aber die gibt es wahrscheilich genauso wenig von WP0 nach WP1. Aber das scheinst Du ja einfach ignorieren zu wollen.
Frage: Wieso gibt es eine Straße von WP0 nach WP1, aber keine Straße von WP0 nach WP3 (Auf dieser wärst du dann nämlich wohl scheinbar schneller).

Erklär mal in deutschen Sätzen, wie Du versucht den nächsten WP zu finden.

cooky451

kantaki schrieb:

nein, jede koordinate liegt auf einem weg.

Ja, das ist einfach ein Designfehler. Was versuchst du zu erreichen?

kantaki schrieb:

ich möchte das als app fürs handy benutzen, da ich gerne fahrrad fahre habe ich die koordianten natürlich nur auf befahrbaren wegen aufgenommen. und falls ein baum kommt muss ich nicht unbedingt dagegen fahren

Aha. Du bewegst dich also auf Straßen/Wegen/Whatever, aber nicht (wie in deinem Programm) auf einem freien Feld, denn da ist der Kürzeste weg von A nach B die Gerade AB!
Speichere bei jeder Krezung bzw. überall dort, wo die Möglicheit besteht abzubiegen, eine Koordinate und dazu zu welchen anderen Kreuzungen du von dort aus gelangen kannst.
Wenn du das für eine Stadt machst, kannst du effizient ausrechnen, welcher der schnellste Weg von A nach B ist.

krümelkacker

kantaki schrieb:

cooky451 schrieb:

kantaki schrieb:

hat jemand vielleicht optimierungsvorschläge?

Du musst dich immer noch auf Straßen fortbewegen! (Jede Kreuzung ist dann ein Punkt.)

nein, jede koordinate liegt auf einem weg.

Und woher weißt Du, welche Koordinaten direkt von einer bestimmten Koordinate aus erreicht werden können? Wo steht diese Information?

Dein Ziel ist doch, eine "Route" zu berechnen, die an einem bestimmten Punkt S (wie Start) anfängt und an einem bestimmten Punkt E (wie Ende) aufhört. Die Route wäre eine Folge von Punkten [S ? ? ... ? ? E], richtig? Es fehlt jetzt irgendwie die Information, welche Punkte hintereinander in dieser Folge auftauchen dürfen. Gegeben zwei Punkte, P und Q: Woher weiß ich, dass eine Route [... P Q ...] gültig ist? Mit anderen Worten: Gibt es einen direkten Weg von P nach Q? Wo steht diese Information?

Du hast bisher Dein Problem "unterspezifiziert". Da fehlt was. Denk da nochmal drüber nach. Und schau Dir nochmal diese Wikipediaseite an.

kantaki

okay tut mir leid, ich habe noch nie wirklich programmiert und ich finde es sehr schwer ein programm zu designen. ich habe mir einfach überlegt wie ich es anstellen könnte und es umgesetzt.

und vielleicht war mein bild ein wenig unpassend. ich versuche nochmal zu erklären was ich eigentlich erreichen wollte =(.

http://imageshack.us/f/607/nav1.jpg/

ich will:
-mich auf den Wegpunkten bewegen und diese nicht verlassen.
-keine Wegpunkte überspringen.
-möglichst kurzen Weg (start A- Ziel
-nich durch Berge laufen.

Meine Überlegung war, dass ich den Wegpunkt nehme der:
1. ...die kürzeste Entfernung zu meiner momentanen Position hat.
2. ...die geringste Entfernung zum Ziel hat.

War meine Überlegung so verkehrt?
Entweder meine Überlegung ist total falsch oder meine Programmumsetzung ist einfach nur schlecht.

SeppJ

Vielleicht solltest du erst einmal klären, wie du als Mensch das Problem mittels Zettel, Stift, Zollstock und Taschenrechner lösen würdest. Und vor allem, denk mal darüber nach, was deine Aussagen wirklich bedeuten:

-mich auf den Wegpunkten bewegen und diese nicht verlassen.

Häh? Nonsensaussage, du kannst keine Strecke aus endlich vielen Punkten zusammenbauen. Was meinst du wirklich?

-keine Wegpunkte überspringen.

Häh? Nonsensaussage. Wie ordnest du Punkte auf einer Fläche? Wie definierst du überspringen? Was meinst du wirklich?

-möglichst kurzen Weg (start A- Ziel

Ok, das ist eine konkrete Aussage.

-nich durch Berge laufen.

Ist auch ok.

Meine Überlegung war, dass ich den Wegpunkt nehme der:
1. ...die kürzeste Entfernung zu meiner momentanen Position hat.
2. ...die geringste Entfernung zum Ziel hat.

Häh? Diese beiden Bedingungen sind im Allgemeinen vollkommen inkompatibel. Was meinst du wirklich?

life

Ich verstehe das so, dass er eine Punktwolke hat, dessen Punkte quasi Abtastpunkte von realen Wegen darstellen. (Z.B. Auto fährt durch Stadt; Jede 5 Sekunden wird mittels GPS Position gemessen und in Punktwolke gespeichert.)

Ausgehend von dieser Wolke will er
1. die Wege rekonstruieren und
2. einen kürzesten Pfad (über die rekonstruierten Wege) von einem Startpunkt zu einem Zielpunkt finden.

Für 1. könnte man z.B. sagen, dass eine Kante zwischen zwei Knoten (Punkten) besteht, wenn der Abstand <= threshold ist. Anschließend lässt man für 2. z.B. A* auf den so konstruierten Graphen los.

krümelkacker

kantaki schrieb:

...
http://imageshack.us/f/607/nav1.jpg/
...
ich will:
-mich auf den Wegpunkten bewegen und diese nicht verlassen.
-keine Wegpunkte überspringen.
...

Das, was Du damit meinst, ist nicht klar.

Wenn ich mir zwei Punkte, P und Q, aus Deinem Bild raussuchte und Dich frägte, ob es einen direkten Weg von P nach Q gibt, der über keine weiteren Punkte ginge und wo man auch keine Punkte "überspringen" müsste, was würdest Du dann tun, um diese Frage zu beantworten?

life schrieb:

[...] könnte man z.B. sagen, dass eine Kante zwischen zwei Knoten (Punkten) besteht, wenn der Abstand <= threshold ist.

Ja, das könnte man so machen. Das ist eine mögliche Antwort auf meine Frage von oben. Aus dem, was kantaki bisher geschrieben hat, geht das nicht hervor.

Dein menschliches Gehirn kann die Punkte natürlich zu Wegen zusammenfügen - strikte Logik nicht!
Mein Hirn sagt mir z.B., dass Ziel B von zwei Wegen angesteuert wird, deshalb weiß ich, dass die Punkte, die nach links oben weglaufen, ein Weg sind, genau so die, die nach links unten weglaufen. Deine Programmlogik sieht das nicht! Würde sie vom oberen Weg Ziel B ansteuern wollen, würde sie vllt. bei ungünstiger Platzierung der Punkte vom zweiten von oben auf den zweiten von unter lenken statt auf den ersten von oben.

Bei einer Wegsuche von Kreuzung links nach Kreuzung rechts würde vllt. der untere Weg gewählt werden, da die Logik Ziel B auslässt und direkt überspringt. Das ist ja ein Berg, evtl hat der Weg, der Zeil B von unten ansteuert, ein Gefälle? Dann liegen die Punkte weit auseinander. Danach fährst du von Ziel B zur rechten Kreuzung auf einem Steilanstieg (die Kurve spricht dafür) Dann liegen a) die Punkte unten weit auseinander b) die Punkte oben eng zusammen und c) die beiden Wege die nach Ziel B führen eng beieinander - deine Logik wird dich hier den Steilhang irgendwo vor Ziel B nach oben schicken! Jippie!

kantaki

Häh? Nonsensaussage, du kannst keine Strecke aus endlich vielen Punkten zusammenbauen. Was meinst du wirklich?

Warum nicht ? ich gehe aus dem Haus und fahre zu einer Hütte, während der fahrt nehme ich alle 10m einen Wegpunkt auf.
Wenn ich wieder zu dieser Hütte möchte geben ich einfach die Koordinaten zu dieser Hütte ein ( Ziel A).

Häh? Nonsensaussage. Wie ordnest du Punkte auf einer Fläche? Wie definierst du überspringen? Was meinst du wirklich?

Die Wegpunkte liegen natürlich auf einem Weg und auf diesem Weg möchte ich mich bewegen. Also macht es doch sinn das ich mich von wegpunkt zu wegpunkt bewege oder?

Häh? Diese beiden Bedingungen sind im Allgemeinen vollkommen inkompatibel. Was meinst du wirklich?

ZB

1. ...die kürzeste Entfernung zu meiner momentanen Position hat.

ich habe die Koordinate von meiner momentanen position zb 1,1,1 jetzt vergleiche ich diese koodinate mit allen von mir aufgezeichneten Koordinaten.
Beispiel WP_POSITION = 1,1,1 wp_X=2,2,2 ( differenz ist 1,1,1)
mit der formel sqrt(1²⁺¹2+1^2) bekomme ich die entfernung heraus.

Jetzt weiß ich das die kleinste Entfernung der nächstliegende Wegpunkt ist.
Die 10 nächstliegenden Wegpunkte speichere ich in einem Vector zu.

2. ...die geringste Entfernung zum Ziel hat.

Nun greife ich auf den Vector mit den 10 nächstliegenden Wegpunkten.

jetzt mache ich das selbe wie bei 1. nur vergleiche ich die gespeicherten Wegpunkte mit der endkoordinate
Beispiel:
WP_X = 2,2,2 wp_END=10,10,10

Nun kann ich entscheiden welchen der 10 Wegpunkte ich benutzen möchte.
Nämlich den Wegpunkt der:
am nächsten liegt und die kürzeste entfernung zum Ziel besitzt.

Das mache ich solange bis WP_POSITION == WP_END

SeppJ

Sabrina S. schrieb:

Dein menschliches Gehirn kann die Punkte natürlich zu Wegen zusammenfügen - strikte Logik nicht!

Was du kannst, kann ein Computer auch. In vielen Fällen, wie diesem auch, ist das sogar erschreckend einfach zu programmieren. Man darf halt nicht den Fehler machen, die Regeln zu einfach zu formulieren.

kantaki schrieb:

Häh? Nonsensaussage, du kannst keine Strecke aus endlich vielen Punkten zusammenbauen. Was meinst du wirklich?

Warum nicht ? ich gehe aus dem Haus und fahre zu einer Hütte, während der fahrt nehme ich alle 10m einen Wegpunkt auf.

Und wo warst du zwischen den beiden Punkten? Teleportiert?

Häh? Nonsensaussage. Wie ordnest du Punkte auf einer Fläche? Wie definierst du überspringen? Was meinst du wirklich?
Die Wegpunkte liegen natürlich auf einem Weg und auf diesem Weg möchte ich mich bewegen. Also macht es doch sinn das ich mich von wegpunkt zu wegpunkt bewege oder?

Und dieser Weg wäre? Wenn du den Weg hast, dann überspringst du von ganz alleine keine Punkte auf diesem Weg, weil sie auf einem Weg liegen. Wenn du keinen Weg hast, bringt dir die Bedingung, dass du keine Punkte überspringen möchtest, überhaupt nichts was den Weg einschränkt. Daher: Nonsens.

Häh? Diese beiden Bedingungen sind im Allgemeinen vollkommen inkompatibel. Was meinst du wirklich?

ZB

1. ...die kürzeste Entfernung zu meiner momentanen Position hat.

ich habe die Koordinate von meiner momentanen position zb 1,1,1 jetzt vergleiche ich diese koodinate mit allen von mir aufgezeichneten Koordinaten.
Beispiel WP_POSITION = 1,1,1 wp_X=2,2,2 ( differenz ist 1,1,1)
mit der formel sqrt(1²⁺¹2+1^2) bekomme ich die entfernung heraus.

Jetzt weiß ich das die kleinste Entfernung der nächstliegende Wegpunkt ist.
Die 10 nächstliegenden Wegpunkte speichere ich in einem Vector zu.

Ach, nun sind es auf einmal nicht mehr nur einer, sondern 10. Das beantwortet schon einmal vieles von der Frage "Was meinst du wirklich?". Es wirft aber neue Fragen auf: Warum 10? Und was ist, wenn 11 Punkte auf einem Kreis liegen?

2. ...die geringste Entfernung zum Ziel hat.

Nun greife ich auf den Vector mit den 10 nächstliegenden Wegpunkten.

jetzt mache ich das selbe wie bei 1. nur vergleiche ich die gespeicherten Wegpunkte mit der endkoordinate
Beispiel:
WP_X = 2,2,2 wp_END=10,10,10

Nun kann ich entscheiden welchen der 10 Wegpunkte ich benutzen möchte.
Nämlich den Wegpunkt der:
am nächsten liegt und die kürzeste entfernung zum Ziel besitzt.

Ach, nun ist es nicht mehr der Punkt am nächsten beim Ziel, sondern der Punkt aus deiner vorher gewählten Menge, der am nächsten beim Ziel ist. Siehst du, wie viel klarer man sich ausdrücken kann?
Und es wirft nun die Frage auf: Was, wenn du in einen Berg oder in eine Sackgasse rennst?

kantaki

Was, wenn du in einen Berg oder in eine Sackgasse rennst?

kann ja garnicht passieren.
da ich
1. nicht mit dem fahrrad über den berg fahren kann, also sind auf dem berg keine wegpunkte.
2. und eine sackgasse wird es auch nicht geben, wie gesagt ich nehme wege auf auf denen ich mich bewege, da wird keine sackgasse sein.

ann liegen a) die Punkte unten weit auseinander b) die Punkte oben eng zusammen und c) die beiden Wege die nach Ziel B führen eng beieinander - deine Logik wird dich hier den Steilhang irgendwo vor Ziel B nach oben schicken! Jippie!

Das kann garnicht passieren. völlig unmöglich. warum ? ich nehme wegpunkte zb alle 10 m auf warum sollte sich der abstand vergrößern wenn ich berg auf oder ab gehe?
meine formel beinhaltet x y und Z.

kantaki schrieb:

Das kann garnicht passieren. völlig unmöglich. warum ? ich nehme wegpunkte zb alle 10 m auf warum sollte sich der abstand vergrößern wenn ich berg auf oder ab gehe?
meine formel beinhaltet x y und Z.

Die 10m kamen erst nach meinem Post, vorher hieß es nur "ich fahre Rad, dabei werden Punkte aufgezeichnet". Ich ging von einer Timergesteuerten Aufzeichnung aus (ist mMn. leichter), dabei liegen die Punkte bei schnellerer Fahrt weiter auseinander als Punkte bei langsamerer Fahrt.
Und wenn du weißt, dass du exakt alle 10m einen Messpunkt hast, warum vergleichst du mit allen Punkten?
Und was ist, wenn du 10m vor einer exakten 60°-Kehre bist? Dann ist von dir aus die Kurve und der nächste Messpunkt nach der Kurve exakt 10m weit weg. Die Logik weiß ja nicht, ob der übersprungene Kurvenpunkt jetzt zum Weg gehört - es ist ja ein anderer Punkt ebenfalls 10m weit weg, und der Weg zum Ziel wird dadurch kürzer.

Langer Rede kurzer Sinn: Bevor du deine Wege ausgeben kannst, musst du festlegen, welche Punkte man tatsächlich zu einem Weg verbinden kann. In einer Punktwolke können alle möglichen Punkte einen möglichen Weg bilden. Das wollen wir dir seit >3 Seiten sagen.

brotbernd

So langsam wird es ja etwas klarer was Du da machst (verstehe nicht wieso Du nicht von Anfang an sagst was Du machst. Wie soll man das mit diesem Bild http://img638.imageshack.us/img638/5426/appwb.jpg erraten. Hellsehen kann hier keiner).
Ich denke Hauptaufgabe ist für Dich aus deinen Punkten Straßen zu bilden. Das ist an vielen Stellen einfach, etwas kniffeliger wird es an Knicken und Kreuzungen. Wenn Du das hast, hast Du Kreuzungen=Knoten und Straßen=Kanten und bewegst dich dann auf bekanntem Gebiet der Graphen. Den Graphen kannst du dann abspeichern und musst nicht jedes mal von vorne deine Straßen suchen.

kantaki

Sabrina S. schrieb:

kantaki schrieb:

Das kann garnicht passieren. völlig unmöglich. warum ? ich nehme wegpunkte zb alle 10 m auf warum sollte sich der abstand vergrößern wenn ich berg auf oder ab gehe?
meine formel beinhaltet x y und Z.

Die 10m kamen erst nach meinem Post, vorher hieß es nur "ich fahre Rad, dabei werden Punkte aufgezeichnet". Ich ging von einer Timergesteuerten Aufzeichnung aus (ist mMn. leichter), dabei liegen die Punkte bei schnellerer Fahrt weiter auseinander als Punkte bei langsamerer Fahrt.
Und wenn du weißt, dass du exakt alle 10m einen Messpunkt hast, warum vergleichst du mit allen Punkten?
Und was ist, wenn du 10m vor einer exakten 60°-Kehre bist? Dann ist von dir aus die Kurve und der nächste Messpunkt nach der Kurve exakt 10m weit weg. Die Logik weiß ja nicht, ob der übersprungene Kurvenpunkt jetzt zum Weg gehört - es ist ja ein anderer Punkt ebenfalls 10m weit weg, und der Weg zum Ziel wird dadurch kürzer.

Langer Rede kurzer Sinn: Bevor du deine Wege ausgeben kannst, musst du festlegen, welche Punkte man tatsächlich zu einem Weg verbinden kann. In einer Punktwolke können alle möglichen Punkte einen möglichen Weg bilden. Das wollen wir dir seit >3 Seiten sagen.

das mache ich weil wenn ich auf einer kreuzung stehe muss ich zb zwichen 4-5 wegpunkten entscheiden. dabei kann natürlich der abstand varieren.

in einer Punktwolke können alle möglichen Punkte einen möglichen Weg bilden. Das wollen wir dir seit >3 Seiten sagen.

deswegen habe ich auch gefragt ob es eine alternative zum vector gibt, da ich beim vector jeden einzelnen wert erstmal ausgeben muss, und da ich ziemlich viele vergleiche anstellen muss, dauert es natürlich auch länger.
eine distanz von ca 50km dauert 4-5sec mit meiner berechnung.
es wäre natürlich ein vorteil wenn ich im vorhinein wüsste welche wegpunkte überhaupt in frage kommen, aber daran hänge ich noch

So langsam wird es ja etwas klarer was Du da machst (verstehe nicht wieso Du nicht von Anfang an sagst was Du machst. Wie soll man das mit diesem Bild http://img638.imageshack.us/img638/5426/appwb.jpg erraten. Hellsehen kann hier keiner).
Ich denke Hauptaufgabe ist für Dich aus deinen Punkten Straßen zu bilden. Das ist an vielen Stellen einfach, etwas kniffeliger wird es an Knicken und Kreuzungen. Wenn Du das hast, hast Du Kreuzungen=Knoten und Straßen=Kanten und bewegst dich dann auf bekanntem Gebiet der Graphen. Den Graphen kannst du dann abspeichern und musst nicht jedes mal von vorne deine Straßen suchen.

genau so mache ich das ich lasse die wegpunkte die ich nehmen soll im vorhinein berechnen, speichere die in eine .ini datei und kann diese dann einfach auf eine karte einzeichnen.

brotbernd

kantaki schrieb:

genau so mache ich das ich lasse die wegpunkte die ich nehmen soll im vorhinein berechnen, speichere die in eine .ini datei und kann diese dann einfach auf eine karte einzeichnen.

Nein, Du machst mit Sicherheit nicht das was da steht. Hast Du überhaupt gelesen was da steht? Der Vorschlag war deine Wegpunkte in einen Graphen mit Knoten und Kanten zu überführen, diesen zu speichern und deine blöden Wegpunkte wegzuschmeißen. Dein Programm arbeitet dann mit dem Graphen und nicht mehr mit Punkten. Der Graph wird dann nur aktualisiert, wenn Du neue Punkte aufgenommen hast.

kantaki

brotbernd schrieb:

kantaki schrieb:

genau so mache ich das ich lasse die wegpunkte die ich nehmen soll im vorhinein berechnen, speichere die in eine .ini datei und kann diese dann einfach auf eine karte einzeichnen.

Nein, Du machst mit Sicherheit nicht das was da steht. Hast Du überhaupt gelesen was da steht? Der Vorschlag war deine Wegpunkte in einen Graphen mit Knoten und Kanten zu überführen, diesen zu speichern und deine blöden Wegpunkte wegzuschmeißen. Dein Programm arbeitet dann mit dem Graphen und nicht mehr mit Punkten. Der Graph wird dann nur aktualisiert, wenn Du neue Punkte aufgenommen hast.

okay tut mir leid, hab ich wohl falsch interpretiert.

kannst du mir erklären was ein "Graph mit Knoten und Kanten" ist?

SeppJ

kantaki schrieb:

kannst du mir erklären was ein "Graph mit Knoten und Kanten" ist?

Das versucht dir hier ein jeder im Thread seit 4 Seiten zu erklären! Wie möchtest du noch jemanden motivieren, das noch einmal zu tun, wenn du bisher nur den Eindruck erweckst, dass man gegen eine Wand anschreibt.

Das Stichwort lässt sich aber auch hervorragend googlen.