Suchergebnisse
Suchergebnisse 1-8 von insgesamt 8.
@nox: Ja, diese Überlegung hab ich auch gemacht, dazu kommt noch, dass ich nicht mit Sicherheit garantieren kann, dass alle Polygone konvex sind, was die Berechnung eines Schwerpunkts meinen Recherchen nach ziemlich verkompliziert. @Black-Panther: Ich weiß jetzt nicht so genau, auf was Du hinaus willst, Hill-Climbing Algorithmus ist m.W. doch eine Methode, um Optimierungsprobleme zu lösen, oder ? Hab da bis jetzt noch nicht soviel Ahnung von, inwiefern das auf geometrische Probleme angwendet wer...
Hallo, danke für eure Tipps, ok einen Brute-Force-Vergleich zu schreiben, dürfte nicht allzu schwierig sein, nur hatte ich gedacht, man könnte den Aufwand etwas reduzieren mit spz. Algorithmen etc. Auch eine Art Unschärfe bei der Abstandsberechnung einzubauen dürfte nicht das Problem sein. @WarMuuh!!: Danke für den Tipp, ich hatte schon vor einiger Zeit mal nach Nachbarn-Algorithmen gesucht, und auch diesen Nearest Neighor Algo angeschaut, ihn dann aber wieder verworfen, da er meiner Erinnerung ...
Hallo nox, es ist klar, dass sich die Nachbar-Polygone in der Nähe des betreffenden Polygons befinden müssen; ich habe schon mal eine Implementierung gesehen, bei der eine Art "unscharfe Grenze" definiert wurde (also etwa, alles was bis zu +/- 5 Einheiten von der Kante des Polygons weg ist, wird noch als Nachbar definiert), aber klar - das kompliziert die Sache noch. Das Problem ist, dass die Karte aus einem anderen Format konvertiert wird (AutoCAD) und es aufgrund von Bugs in der Export-Funktio...
Hallo, ich habe in meinem Projekt das Problem, eine automatische Nachbarschaftsrelation von allen Polygonen in einer Karte berechnen zu müssen. Die Karte besteht aus bis zu tausenden Polygonen, die normalerweise alle aneinandergrenzen. Leider ist das Kartenformat eine spezifische Art von XML, die zwar größtenteils hierarchisch (kleiner Elemente sind in größeren enthalten) sind, aber keine wirkliche geometrische Ordnung besitzen (man kann nicht sagen, welche Polygone sich in der Nachbarschaft ein...
Hm, ja an sowas in der Art hab ich auch schon mal gedacht; eine Art "Map Matching" mittels Ort / mittlerer Richtungsvektor, das geht dann aber schon in Richtung Ähnlichkeits-Algorithmus... aber sowas ähnliches wurde m.W. vom Ansatz her auch schon in anderen Routenplanern versucht...
Hallo zera, die Idee mit dem Abstand hatte ich auch schon mal, leider versagt diese einfache Berechnung, wenn der Graph nicht aus nur linear hintereinander angeordneten Wegpunkten besteht, sondern auch Abzweigungen, Kreuzungen usw. beinhaltet. Dann kann es passieren, dass sich Benutzer in der Nähe eines solchen Kreuzungspunkts befindet und der kleinste Abstand gerade zur falschen Kante führt; ganz nutzlos wird der Ansatz, wenn ich einen Graphen habe der ein Quadrat an Wegpunkten beinhaltet und s...
Hallo, @knivil: Es handelt sich nicht um ein Spiel, sondern um einen GPS-Tracker. Ich update die aktuelle Position jede Sekunde, sobald eben das GPS eine neue Message liefert. Im Programm lassen sich Routen auf einem vorher definierten Graphen festlegen; die Routen berechne ich durch den A*-Algorithmus (euklidischer Abstand zum Ziel als Heuristik-Funktion). Damit man nicht genau den einzelnen Wegpunkt "treffen" muss, definiere ich ein Proximity-Rechteck um die einzelnen Wegpunkte, in dem man sic...
Hallo, ich bin neu hier und habe ein Problem mit der Routenplanung in meinem Projekt: Ich habe eine Spielfigur, von der ich die Position in (x,y)-Koordinaten kenne, und einen vorgeschriebene Route in einem Graphen, die ich per A*-Algorithmus berechne. Mein Problem: Wie erkenne ich nun, welche Punkte der Zielroute von der Figur schon "abgelaufen" wurden? Ich kann zwar immer die Abstände Spielfigur -> Knoten berechnen, aber das zeigt mir nicht an, ob der Bereich um den Knoten schon passiert wurde....