# kürzester weg  zwischen zwei Punkten, Koordinaten finden



## chief. wiggam (19. Apr 2007)

Servus

ich habe folgendes Problem und weiss nicht, wie ich es angehen soll, bzw. nicht so, das es alle fälle abdeckt:

Es seien zwei java.awt.Point Objekte gegeben. Ich möchte jetzt den kürzesten Weg zwischen diesen beiden Punkten berechnen, das ist ja auch ganz einfach -> satz des pytagoras. Diesen kürzesten Weg möchte ich nun weiterverarbeiten und brauche die Point-Objekte aus von dieser Geraden, wie komm ich an diese ran?

Beispiel: 
p1.x = 100, p1.y= 100;
p2.x = 200, p2.y = 200;

```
p2
                -
            -
        -
    -
p1
```

Ich brauche nun die Point-Elemente, die auch Graphics.drawLine benötigt um die Linie zu zeichnen.

Kann mir jemand einen Ansatz geben?


----------



## Wildcard (19. Apr 2007)

Zurückdenken an die 7. Klasse.
Geradengleichung, 2 Punkte Form,....


----------



## Deady (20. Apr 2007)

Das geht ziemlich einfach:

Zunächst brauchst du die anzahl der zwischenschritte.

Dann berechnest du den abstand zwischen point1.x und point2.x, genauso dann für y.

Abstandx = point1.x – point2.x;
abstandy = point1.y – poin2.y;

Die ergebnisse kannst du mit hilfe einer for-schleife in einem oder zwei arrays ablegen.

For (int i = 1; i < zwischenschritte; i++) {
arrayx_ += arrayx[i-1] + (abstand/zwischenschritte);
arrayy += arrayy[i-1] + (abstand/zwischenschritte);
}

mfg
Deady_


----------



## AlArenal (20. Apr 2007)

Wildcard hat gesagt.:
			
		

> Zurückdenken an die 7. Klasse.
> Geradengleichung, 2 Punkte Form,....



:lol:

Manchmal lernt man eben doch fürs Leben


----------



## Deady (20. Apr 2007)

sorry, so isses richtiger:

For (int i = 0; i < zwischenschritte; i++) {
arrayx_ = arrayx[i-1] + (abstandx/zwischenschritte);
arrayy = arrayy[i-1] + (abstandy/zwischenschritte);
}

Den startpunkt fügst du im array an position [0] ein, den endpunkt entsprechend am ende.

mfg
Deady_


----------



## Unregistriert (23. Okt 2009)

Deady hat gesagt.:


> Das geht ziemlich einfach:
> 
> Zunächst brauchst du die anzahl der zwischenschritte.



Wie rechne ich die Zwischenschritte aus?
Sorry, aber bin ned so ein Mathe-"Genie"...
Wahrscheinlich muss man kein Genie sein, aber egal^^

Bitte um Antwort =)


----------



## JohannisderKaeufer (24. Okt 2009)

Wie wäre es mit einer Umrechnung in Polarkoordinaten und wieder zurück zu den Kartesischen.

In den Polarkoordinaten hast du den Winkel und mußt nur die Länge variieren.


----------



## Ark (24. Okt 2009)

1. Man beachte, was Wildcard und JohannisderKaeufer gesagt haben.
2. (Und nur, falls derart große Rundungsfehler erlaubt sind!!) Bresenham-Algorithmus ? Wikipedia

Ark


----------



## darkeye2 (25. Okt 2009)

Hallo, also wie man die gerade zeichnet ist mir zwar bekannt, aber ich hab ein anderes problem ... wie kriege ich den kürzesten weg raus, wenn nichtalle pixel genutzer werden dürfen... bsp.:
* = unpassierbare punkte; # = anfangs und endpunkte; :

```
*********                     
   #      ****
            *******
                         ***      #
```


----------



## Ark (25. Okt 2009)

Hm, ich bin mir nicht sicher, aber möglicherweise hilft der hier weiter:

Dijkstra-Algorithmus ? Wikipedia

Ark


----------



## faetzminator (25. Okt 2009)

Japs, ein Dijkstra oder A* funktioniert, hab ich in C mal geschrieben. Du kannst da einfach die Entfernung weglassen.


----------



## ice-breaker (25. Okt 2009)

A* wäre die bessere Wahl 
Da er hier geschickt die Luftlinie als Heuristik nutzen kann, hat er ein besseres Laufzeitverhalten mit dem A* im Gegensatz zum Dijkstra


----------



## darkeye2 (25. Okt 2009)

hmm, hab mich etwas umgesehen, aber komme net wirklich weiter, also nehmen wir mal an, ich habe folgende situaltion:
Punkt A (10, 50)
Punkt B (70, 15)
Unpassierbares rechteck definiert durch die Punkte:
R1 (25, 20)
R2 (55, 20)
R3 (25, 60)
R4 (55, 60)

So, und jetzt brauche ich ja den weg von A nach B, wobei ich wissen buss, wo sich alle zwischenpunkte befinden, also wo jetzt punkte liegen, an dennen sich die richtung ändert. damit ich das graphisch darstellen kann.

Schon mal Danke für die bisscherigen Tipps!


----------



## faetzminator (25. Okt 2009)

A*-Algorithmus ? Wikipedia schon gelesen?


----------



## darkeye2 (25. Okt 2009)

jop, so wie ich das verstehe, braucht der algo irgendwleche punkte, und er rechnet nur aus, welche punkte ich verbindung muss, um den kürzesten weg zu ermitteln, aber hier habe ich ja sozusagen nur 2 punkte, und dazwischen eine fläche, die net durchquert werden kann, es könnte jetzt z.b. so ausschauen:

```
+-----------------------+
|                                |
|            +--+         B    |
|            |**|               |
|         +-+**|              | 
| A      |****|              |
|         +-----+             |
+-----------------------+
```

(auf der rechten seite sollte es den rand  auc hgeben, ist irgendwie komisch ...)

Auf jeden fall, wie soll ich den das nicht passierbare feld im algorithmus angeben?


----------



## faetzminator (25. Okt 2009)

Ich schrieb damals eine KI für ein interaktives Game, in welches unsere KI's gegeneinander kämpften (schweizer Informatikolympiade). Da bekam ich vom Server gleich ne Map und konnte diese 1:1 verwenden. (. = freie Fläche, # = Mauer, $ = Futter etc.). Du musst einfach irgendwie intern speichern, was ein Feld ist. Falls du da nur Mauer und "nicht Mauer" hast, kannst du einen boolean dafür verwenden.


----------

