Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Berechnen ob Punkt sich in Vieleck befindet

Berechnen ob Punkt sich in Vieleck befindet

Schüler

Tags: Polygon, Punkt, Vieleck

Make-Grafik aktiv_icon

16:20 Uhr, 13.04.2013

Hallo OnlineMathe Community!
Ich möchte berechnen ob sich ein Punkt in einem Vieleck befindet.

Hier sind die Koordinaten des Vielecks:

A = (\binom{3}{0})

B = (\binom{4}{0})

C = (\binom{7}{7})

D = (\binom{6}{7})

E = (\binom{0}{2})

Folgende Strecken sind demnach vorhanden:

\vec{A B} \vec{B C} \vec{C D} \vec{D E} \vec{E A}

Die Koordinate des Punktes:

P = (\binom{3}{3})

Mein Grundgedanke ist Folgender:
2 Punkte welche mit einer Strecke verbunden sind und der Punkt

P

bilden zusammen ein Dreieck. Jeder Winkel in einem Dreieck muss über

0 °

und unter

180 °

liegen. Also muss der Winkel, welcher bei dem Punkt

P

liegt über

0 °

und unter

180 °

sein. Wenn ich also jedes mögliche Dreieck nach diesen Verfahren überprüfe und der Winkel bei jedem Dreieck über

0 °

und unter

180 °

liegt, dann muss sich also der Punkt

P

im Vieleck befinden. Wenn jedoch ein Winkel

180 °

beträgt, dann muss der Punkt

P

auf einer der oben genannten Strecken liegen. Und wenn ein Winkel die

180 °

überstreigen, dann muss sich der Punkt

P

außerhalb des Vielecks befinden.

Soweit zu meinen Grundgedanken! Wenn jemand eine bessere Idee hat, würde ich mich freuen wenn ihr mir das mitteilt.

Ich schließe an meinen Grundgedanken an:
Ziel ist es nun, den Winkel der Dreiecke die bei

P

liegen zu berechnen. Allerdings habe ich keine Idee wie. Ich würde mich über jede Hilfe freuen! Ich brauche einen Ansatz der mich zu meinen Ziel führt. Ich bitte darum mir einen Denkanstoß zu geben aber auf keinen Fall die Lösung! Die Lösung möchte ich nämlich selber erarbeiten um das Verfahren zu verstehen. Später muss ich diesen Algorithmus nämlich programmieren.

LG. Make :-D)

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Ebene Geometrie - Einführung
Grundbegriffe der ebenen Geometrie

Zu diesem Thema passende Musteraufgaben einblenden

Femat aktiv_icon

16:54 Uhr, 13.04.2013

Ich empfehle dir sehr, folgenden Beitrag zu studieren.

http//www.onlinemathe.de/forum/Punkt-in-Dreieck

Deine Figur ist eher seltsam

Make-Grafik aktiv_icon

17:05 Uhr, 13.04.2013

Okey...
Kann sein dass ich die

x

und

y

Koordinaten vertauscht habe :-P)
Ich lerne mir das alles selber also bitte verzeihe mir für diesen schwerwiegenden Fehler!

Dreh einfach die Koordinaten um...

Ich dachte immer das oben die x-Koodrinate steht und unten die y-Koordinate?

Werner-Salomon aktiv_icon

17:12 Uhr, 13.04.2013

Hallo Make,

um es gleich vorweg zu nehmen. Deine Überlegungen passen nicht für den allgemeinen Fall eines Polygons. Die Prüfung auf >180° läuft im Prinzip darauf hinaus zu ermitteln, ob ein Punkt P links (oder rechts - je nachdem, was die Definition für 'außen' ist) von einer Strecke liegt. In einem Polygon was nicht konvex ist kann ein Punkt P innerhalb des Polygons aber durchaus rechts von einer Strecke liegen und wird daher fälschlich als außen liegend deklariert.

Im konkreten Fall des von Dir angegebenen Polygons fällt auf, dass A auf der Verbindung von E nach B liegt, also auch entfernt werden kann, ohne das Polygon zu verändern.

Weiter schneidet die Strecke BC die Strecke DE in

(\begin{array}{rcl} \frac{84}{17} \\ \frac{104}{17} \end{array})

Es ist also nicht klar, wo bei Deinem Polygon überhaupt innen und außen ist.

Mal angenommen, Du hast ein 'kreuzungsfreies' Polygon, und Du möchtest bestimmen, ob ein Punkt innen liegt, so ziehe einen beliebigen Strahl durch P (Halbgerade). Das kann z.B einfach ein horizontaler Strahl wie

y = P_{y}

sein. Dann bestimme alle vorhandenen Schnittpunkte dieses Strahls mit den Strecken des Polygons und betrachte den P am nächsten liegenden Schnittpunkt.

Liegt der Punkt P links von der dem Schnittpunkt zugehörigen Strecke, so liegt P im Polygon. (links, wenn das Polygon mathematisch positiv 'dreht')
Ist kein Schnittpunkt vorhanden ist P außen.
Aufpassen musst Du, wenn der Schnittpunkt gleichzeitig Stützpunkt des Polygons ist. Dann kommen zwei Strecken in Frage - dieses Detail überlasse ich Dir.

Gruß
Werner

Werner-Salomon aktiv_icon

17:15 Uhr, 13.04.2013

X ist oben, das ist richtig.
Die Koordinaten welchen Punktes sollen wir umdrehen? Wenn alle umgedreht werden, ändert sich im Prinzip nichts.

Und was ist mit A? liegt er auf EB?

Femat aktiv_icon

17:17 Uhr, 13.04.2013

Ich habe mal gedreht
sieht nicht toller aus.

Make-Grafik aktiv_icon

17:32 Uhr, 13.04.2013

Ich hab euch mal mein Koordinatensystem eingescannt!
Ich habe Punkt

P

dort bei

x = 3,5

und

y = 3

eingezeichnet!
Ignoriert das... LaTex wollte das nicht mit

3,5

anzeigen, daher habe ich daraus eine 3 gemacht :-P)

http//www7.pic-upload.de/13.04.13/t53tjc36n6kf.png

Sorry, Koordinate A und

B

sind komischerweise verdreht... Habe aber eigentlich richtig eingegeben oO

Ich berichtige dass im ersten Post eben...

Femat aktiv_icon

17:53 Uhr, 13.04.2013

Ist es nicht so?
Wenn der

P

südlich des nördlichsten, östlich des westlichsten, und nördlich des südlichsten und westlich des östlichsten Punktes des Polygons liegt, ist er drin.

Werner-Salomon aktiv_icon

18:01 Uhr, 13.04.2013

Hallo Femat,

Gegenbeispiel: ein auf der Spitze stehendes Quadrat - z.B. mit den Koordinaten (2;0), (4;2), (2;4), (0;2) und der Punkt P(3;0,5). Nach Deiner Bedingung liegt er drin, er liegt aber außerhalb.

Gruß
Werner

Make-Grafik aktiv_icon

18:03 Uhr, 13.04.2013

Leider nicht! ^^
Diese Überlegung hatte ich auch schon...

Aber wie sieht es bei dieser Situation aus?
Trifft dass dann auch noch zu?

A = (\binom{0}{0})

B = (\binom{5}{2})

C = (\binom{3}{4})

D = (\binom{5}{6})

E = (\binom{1}{6})

P = (\binom{4}{4})

Werner-Salomon aktiv_icon

18:04 Uhr, 13.04.2013

.. irgendwie habe ich das Gefühl, dass meine Postings keiner liest!? ;-)

Femat aktiv_icon

18:10 Uhr, 13.04.2013

Lieber Werner
Du hast recht mit dem Quadrat.
Natürlich werden deine Beiträge gelesen. Aber machmal überschlägt sich alles zeitlich und es gibt auch noch alltägliche Annehmlichkeiten und Verpflichtungen neben der hochinteressanten Mathematik.

Ich lande gedanklich wieder bei der Streifenmethode, die ich in dem Link, den ich hier auch schon empfohlen habe, auch vorschlug.:-)

Make-Grafik aktiv_icon

18:11 Uhr, 13.04.2013

@Werner-Salomon:
Die ignoriere ich mit absicht! :-D)
Okey, Spaß bei Seite...

Stell dir mal vor du hast ein Polygon wo eine Strecke genau Parallel zu der x-Achse ist. Und der Punkt

P

liegt auf dieser Strecke und der Strahl geht auch rein zufällig parallel zur x-Achse...

Tja, dann würde das nicht mehr funktionieren...
Daher bleibe ich lieber bei meiner Dreieckslösung weil ich weiß, dass sich keine Strecke des Polygons schneidet! Wenn noch Ideen vorhanden sind, ich bin für alles offen. :-)

Nun ja, ich lenke mal wieder zur meiner eigentlichen Frage:
Wie berechne ich nun den Winkel nur mit Hilfe der Koordinaten?
Bzw >> Ich hätte gerne einen Denkansatz bitte! :-D)

LG. Make

Femat aktiv_icon

18:21 Uhr, 13.04.2013

Da man Polygone in Dreiecke zerlegen kann, würd ich doch mal den von mir schon empfohlenen Beitrag studieren.
Liegt ein Punkt im Dreieck, war dort das Thema. und unter Google findest zu eben diesem Thema auch viele Beiträge.

Werner-Salomon aktiv_icon

18:26 Uhr, 13.04.2013

.. ok, ok; man beachte das Augenzwinkern hinter meiner Provokation.

@Femat: an die 'Streifenmethode' kann ich mich noch gut erinnern. Beachte auch meinen Beitrag zu dem Thema. Es ist aber gar nicht trivial ein konkaves Polygon in Dreiecke zu zerlegen - und zwar derart, dass alle Dreiecke wieder 'innen' liegen. Anschließend wäre es natürlich vergleichsweise einfach zu prüfen, ob P in einem der Dreiecke liegt.

@make: doch - der von mir vorgeschlagene Algorithmus funktioniert auch dann. Dann liegt nämlich der nächste Schnittpunkt auf einem der Stützstellen. Ich hatte ja erwähnt, dass dieser Fall extra zu behandeln ist.

Wenn das Polygon sicher konvex ist, reicht es aus zu prüfen, ob P immer 'links' liegt. Das wiederum geht einfach mit dem Kreuzprodukt. Es muss für alle benachbarten Stützstellenpaare

S_{i}

und

S_{i + 1}

gelten, dass

S_{i} S_{i + 1} \times S_{i} P \geq 0

im Falle von

= 0

liegt der Punkt auf der Geraden der Strecke.

Weißt Du wie man das berechnet?

Gruß
Werner

Femat aktiv_icon

18:29 Uhr, 13.04.2013

Wenn du solche Dinge zu programmieren gedenkst, ist wohl eine Einarbeitung in die analytische Geometrie unumgänglich.

Berechnung Winkel zwischen Vektoren

z . B

unter:

http//de.wikipedia.org/wiki/Skalarprodukt

Femat aktiv_icon

18:29 Uhr, 13.04.2013

Wenn du solche Dinge zu programmieren gedenkst, ist wohl eine Einarbeitung in die analytische Geometrie unumgänglich.

Berechnung Winkel zwischen Vektoren

z . B

unter:

http//de.wikipedia.org/wiki/Skalarprodukt

Werner-Salomon aktiv_icon

18:36 Uhr, 13.04.2013

... ich werde das Gefühl nicht los, dass meine Beiträge nicht verstanden werden.

@Femat: das Skalarprodukt liefert Dir den

c o s

des Winkels, hier wird aber der

s i n

des Winkels für die links-rechts (bzw. inenn/außen) Entscheidung benötigt - daher das Kreuzprodukt.
Ansonsten gebe ich Dir Recht: Grundkenntnisse in analytische Geometrie sind hier absolut hilfreich.

@Make: das Prinzip mit dem Winkel ist durchaus richtig. Es reicht aber die Information ob >180° oder nicht und dafür reicht der

s i n

, daher das Kreuzprodukt (s.o.).

Übrigens programmiere ich solche Sachen.

Liebe Grüße und nichts für ungut
Werner

Make-Grafik aktiv_icon

18:46 Uhr, 13.04.2013

Scheint wirklich so dass ich anscheinend deinen Beitrag nicht verstanden habe...
Um erhlich zu sein, hatte ich zuvor noch nichts mit der Trigonomie bzw. Schnittpunkten etc. Zu tun.

Mein Wissen darüber ist nur sehr begrenzt. Brauch ein wenig Zeit um mir das in ruhe durchzulesen und zu verstehen. ^^

Ich bin in der 8ten Klasse... Das sollte ich denke ich als Erklärung reichen weshalbt ich da Probleme bei habe. Mir Fehlt das Wissen dazu ^^

Melde mich nochmal wenn ich das ganze gelesen und auch wirklich verstanden habe.

LG. Make

Werner-Salomon aktiv_icon

19:08 Uhr, 13.04.2013

Hallo Make,

ich hatte Dich oben ja gefragt, ob Du weißt wie man das Kreuzprodukt hier berechnet. Du hattest nicht darauf reagiert.
in der 8.Klasse kannst Du das noch nicht wissen.

Es geht darum heraus zu bekommen, ob P links(innen) oder rechts(außen) von einer Strecke liegt. Dazu bestimmt man zunächst die 'Richtung' der Strecke indem man einfach die Koordinaten der auf einander folgenden Punkte von einander abzieht.

Beispiel: B und C;

B = (\begin{array}{rcl} 4 \\ 0 \end{array})

und

C = (\begin{array}{rcl} 7 \\ 7 \end{array})

dann rechnest Du

\vec{s} = C - B = (\begin{array}{rcl} 7 \\ 7 \end{array}) - (\begin{array}{rcl} 4 \\ 0 \end{array}) = (\begin{array}{rcl} 7 - 4 \\ 7 - 0 \end{array}) = (\begin{array}{rcl} 3 \\ 7 \end{array})

das ist der Vektor von B nach C.
Nun bestimmst Du den Vektor von B nach P auf die gleiche Art & Weise.

\vec{t} = P - B = (\begin{array}{rcl} 3 \\ 3 \end{array}) - (\begin{array}{rcl} 4 \\ 0 \end{array}) = (\begin{array}{rcl} 3 - 4 \\ 3 - 0 \end{array}) = (\begin{array}{rcl} - 1 \\ 3 \end{array})

und jetzt kommt das Kreuzprodukt. Hierzu multiplizierst Du kreuzweise die x- und y-Werte der beiden Vektoren und berechnest die Differenz der beiden Produkte. Achtung es kommt hier auf die Reihenfolge an.
Es gilt

\vec{s} \times \vec{t} = (\begin{array}{rcl} 3 \\ 7 \end{array}) \times (\begin{array}{rcl} - 1 \\ 3 \end{array}) = 3 * 3 - 7 * (- 1) = 9 + 7 = 16

der Wert ist positiv, also liegt P links von der Strecke.

das musst Du für alle Strecken machen, wenn P immer links liegt, so ist er drin.

(siehe auch de.wikipedia.org/wiki/Kreuzprodukt; ist hier aber nur für 3D erklärt)
Gruß
Werner

Make-Grafik aktiv_icon

19:30 Uhr, 13.04.2013

Okey :-)
Ich denke ich habe das verstanden...

Nur noch eine Frage, wenn ich die Strecke

\vec{A B}

habe, muss ich dann

\vec{B} - \vec{A}

rechnen oder

\vec{A} - \vec{B}

?

Oder kommt das auf den Inhalt der Vektoren an?

3D wäre der nächste Schritt... Ich bin gerade dabei mir die Grundlagen für die Programmierung in der dritten Dimension zu schaffen. :-D)

Danke für die Unterstützung! :-)

Werner-Salomon aktiv_icon

22:30 Uhr, 13.04.2013

Hallo Make,

wenn Du den Vektor der Strecke