Strecke die am nächsten zu einem Punkt liegt

[Gast]

Ich habe in einem Java-Programm mehrere Strecken und einen Punkt. Nun möchte ich rausfinden, welche Strecke den geringsten Abstand zum Punkt hat (exakter Abstand ist mir eigtl. egal). Was ist dafür denn die effizienteste Methode? Hab beim googlen hier http://www.hinterseher.de/Diplomarbeit/relativeLage.html gefunden, dass man das für eine Strecke mit
d = | x * cosa + y * sina - p |
berechnen könnte aber da kommts mir irgendwie so vor als ob die Formel nicht korrekt wäre oder (was soll denn auch p sein?)?

[RattuS]

Sofern du die Steigung nicht benötigst, geht das ganz simpel über Delta.

[Gast]

Delta? Hast du einen Link dazu wo das erklärt wird?

[RattuS]

Du hast 2 Punkte, X und Y. Um die Differenz zwischen diesen beiden Punkten zu ermitteln, bildest du einfach ein Pseudodreieck, das du mit dem Satz des Pythagoras berechnest.

d = Wurzel {(x1 - x2)² + (y1 + y2)²}

Edit: Sorry, ich hab dich falsch verstanden. Ich dachte, dass du die Strecke zwischen 2 Punkten suchst. :ulol:

[DocEW]

Um den Abstand von Punkt P zur Strecke AB zu bestimmen, könntest du P auf die zur Strecke gehörenden Gerade projizieren. Wenn die Projektion P' zwischen A und B liegt, bist du fertig, der Abstand |PP'| ist dann die Lösung. Wenn P' nicht zwischen A und B liegt ist die Lösung min(|PA|, |PB|).
Das Ganze machst du mit allen Strecken und suchst einfach den kleinsten Abstand.
Es gibt sicher auch noch schlauere Wege... mit irgendwelchen Methoden aus der algorithmischen Geometrie (Sweep-Verfahren etc.), aber vielleicht reicht das ja so.

[Trap]

Es kommt drauf an was genau dein Problem ist.

Wenn der Strecken meist fest sind und für verschiedene Punkte die nächste Strecke gesucht wird helfen Octrees oder KD-Trees.

Wenn der Punkt fest ist und die Strecken einzeln dazukommen oder alles sich jedesmal ändert, muss man sich nur die jeweils nächste Strecke merken, Rechnungen dürfte man sich aber kaum sparen können.

Wenn alles fest ist braucht man nicht rechnen.

[Tesseract]

ich würde es so machen:

1) punkt auf die geraden projizieren.
2a) wenn dieser punkt zwischen anfangs- und endpunkt der strecke liegt, ist er die kürzeste entfernung der strecke zum punkt.
2b) wenn er außerhalb der strecke liegt ist der anfangs oder endpunkt (welcher halt näher ist) die kürzeste entfernung zum punkt.

wenn du das mit allen strecken gemacht hast nimmst du den nahsten der projektions/end/anfangs-punkte und bist fertig.

aber keine garantie, dass das die optimallösung ist.

[rotalever]

wenn du das mit allen strecken gemacht hast nimmst du den nahsten deiner schnittpunkte und bist fertig.

aber keine garantie, dass das die optimallösung ist.
Kommt halt darauf an. Die Idee mit einem Suchbaum könnte hier weiterhelfen, falls das verschiedenen Punkten immer wieder gemacht werden muss, aber die Strecken fest bleiben. Ansonsten natürlich nicht, da das Aufbauen des Suchbaumes ja auch Zeit kostet. Wenn das jeweils eine einmalige Angelegenheit ist, dann muss man sowieso jede Strecke mindestens ein Mal "anschauen". Hier könnte man dann noch optimieren, dass nur bei manchen Strecken teure Operationen verwendet werden, aber das hängt ja davon ab, wofür man es benutzen möchte.

[Tesseract]

wie willst du das mit einem suchbaum machen? mit bounding volumes?

[rotalever]

wie willst du das mit einem suchbaum machen? mit bounding volumes?
ja hätte an sowas gedacht, irgendwie mit einem Quadtree (es ist doch 2d?).

[DocEW]

ich würde es so machen:
...
Habe ich doch genau so beschrieben, oder? :|

[Tesseract]

Habe ich doch genau so beschrieben, oder? :|

hm... jo denke schon. wieso? :D