railroadblues - Fr 06.12.02 22:25
Titel: Frage zur Programmierung

---

hallo,
muss einen algorithmus für folgendes prob aufstellen:

"Gegeben seien n Punkte durch ihre kartesischen koord. x[i] und y[i] (i=1(1)n).diese punkte werden durch strecken zu einem polygon verbunden(punkt 1 mit punkt 2,punkt 2 mit punkt 3...Punkt n mit Punkt 1).weiterhin sei ein Punkt mit den Koord. (xp,yp) gegeben.es ist zu klären ob der punkt innerhalb des polygons liegt oder nicht."

kann mir jemand helfen.
habe keine ahnung was ich da machen muss.

brauche dazu ein struktogramm.

bin für jede hilfe dankbar................

Christian S. - Fr 06.12.02 22:57

---

Ich habe noch keinen fertigen Algortihmus, aber ich kann Dir einen Ansatz sagen, der Dir vielleicht weiterhilft:

1. Die Punkte P[1] bis P[n] definieren Dir Funktionen f[1] bis f[n], wobei f[i] die Punkte P[i] und P[i+1] verbindet, wenn i=1,...n-1 ist und die Punkte f[n] und f[1] verbindet, wenn i=n ist. Diese Funktionen sind jeweils nur auf dem Intervall der x-Achse definiert, das den x-Koordination der zugehörigen Punkte entspricht.

2. Du musst jetzt die beiden Funktionen aus der Menge der f[i] suchen, die an der x-Koordinate des Punktes, den Du prüfen sollst, definiert sind. Hast Du die beiden Funktionen, ist die Hauptarbeit getan. Jetzt musst Du nur noch die x-Koordinate in die beiden Funktionen einsetzen und schauen, ob von den beiden Funktionswerten einer kleiner und einer größer als die y-Koordinate des zu prüfenden Punktes ist.

Hoffe, ich konnte Dir wenigstens ein wenig helfen,
Peter

Wolff68 - Sa 07.12.02 00:03

---

Du kannst auch für jede Teilstrecke nachschauen, ob der Punkt links oder rechts der Geraden liegt. Ist er für alle Geraden auf der gleichen Seite liegt der Punkt innerhalb des Poligons.

Mit folgender Formel bekommst Du ein positives Ergebnis, wenn der Punkt P links der geraden A-B liegt und ein negatives, wenn er rechts liegt.
(Genau genommen ist D der Abstand des Punktes zur Geraden)

Übrigends: Durch das Teilen solltest Du eventuell vorher Prüfen, ob nicht A und B gleich sind, da es sonst zu einem Div/0 kommt.

Ausserdem gibt diese Lösung ein hübsches Flussdiagramm. :lol:

Christian S. - Sa 07.12.02 13:23

---

Zitat:

Ist er für alle Geraden auf der gleichen Seite liegt der Punkt innerhalb des Poligons.

Das verstehe ich nicht. Wenn ein Punkt innerhalb eines (z.B.) Vierecks liegen soll, dann muss er doch auf jeweils unterschiedlichen Seiten der vier Geraden liegen, oder?

Ach ja, da fällt mir noch etwas ein: Geraden, die senkrecht nach oben zeigen, sind natürlich nicht definiert. Aber die brauchts Du auch nicht.

MfG,
Peter

Wolff68 - Sa 07.12.02 23:55

---

@Peter:
Angenommen, Du hast eine Laterne in der Mitte eines Parkplatzes.
Jetzt läufst Du von Ecke A nach B. von B nach C, von C nach D und von D nach A... Ist doch die Laterne immer links von Dir, oder nicht?

Aber meine Lösung hat echt ein Problem. Sie geht davon aus, daß das Vieleck einigermaßen regelmäßig ist. Bzw. daß alle Winkel in die gleiche Richtung gehen.
Bei dem hier haut das wegen der roten Strecke schon nimmer hin :(

Christian S. - So 08.12.02 14:14

---

:idea: Ah, jetzt verstehe ich, wie Du das meinst. Ich war von einem "absoluten" links und rechts ausgegangen, Du läufst sozusagen auf den Linien entlang. Meine Lösung funktioniert aber leider auch nicht immer:

Wenn Du dein Bild um 90° im Uhrzeigersinn kippst und den Punkt dann unter dem roten Strich plazierst, würde mein Algorithmus behaupten, er wäre innerhalb des Polygons. Man müsste Schritt 2 bei meiner Lösung noch einmal anwenden, lediglich mit vertauschten Rollen von x und y. Ich glaube, dann sollte es funktionieren.

MfG,
Peter