punkt in konkavem Polygon
-
Hi Leute,
ich versuche gerade einen Algorithmus, zur Bestimmung ob sich ein Punkt in einem konkavem Polygon befindet oder nicht, herzuleiten, oder selber auf die Beine zu stellen/verbessern. Als Grundlage habe ich mich an diese Anleitung gehalten. Den allgemeinen Ansatz mit der Straight-On-Variante finde ich interessant, habe allerdings nicht verstanden wie die Parameter d,a und m zu interpretieren sind und wie sie hergeleitet wurden. Vom Prinzip her habe ich alles soweit verstanden.
Ich werde mal posten was ich bis jetzt raus bekommen habe.
Zu untersuchender Punkt: Index a
\begin{equation}y\_a=s/c*x\_a+b_a\end{equation}Zu untersuchende Kante: Index i für erste Ecke und nachfolgender Ecke i+1, die Kante wird mit p gekennzeichnet
\setcounter{equation}{1}\begin{equation}y\_p=m\_p*x\_p+b\_p\end{equation}Der zu untersuchende Punkt soll als A bezeichnet werden. Von A geht ein Strahl Namens S aus, der irgendeine Kante des Polygons schneidet. Die Kante wird als P bezeichnet.
Nur welche Kante, das müssen wir raus kriegen. Wenn der Strahl S eine der Kanten schneidet so gilt.
\setcounter{equation}{4}\begin{equation}b_a=y*-s/c*x[i] \end{equation}*
\setcounter{equation}{2}\begin{equation}y\_a=y\_p\end{equation}
(1) und (2) in (3) ergibt,
\setcounter{equation}{3}\begin{equation}m\_p\*x\_p+b\_p=s/c\*x\_a+b_a\end{equation}
Nun könnte der Strahl S den Punkt P(xi;yi) schneiden, dann folgt aus (1) in diesem PunktP(xi;yi) ist eine Ecke des Polygons, die um ungünstigen Fall geschnitten wird vom Strahl S was wir nicht wollen, aber es kann ja sein und wir müssen dies überprüfen.
Nun setzen wir (5) wieder in (1) ein und erhahlten
\setcounter{equation}{6}\begin{equation}y\_a-s/c\*x\_a=y[i]-s/c\*x[i] \end{equation} \setcounter{equation}{7}\begin{equation}c\*y\_a-s\*x\_a=c\*y[i]-s\*x[i] \end{equation} \setcounter{equation}{8}\begin{equation}c*(y[i]-y\_a)=s(x[i]-x\_a) \end{equation}
\setcounter{equation}{5}\begin{equation}y\_a=s/c\*x\_a+y[i]-s/c\*x[i]\end{equation}
Dies ergibt dann,In [i]dieser Anleitung* hat der Autor 3 Gleichungen gepostet, auf die ich nicht komme bzw. mir der Ansatz zur Zeit fehlt. Hier die Gleichungen:
\setcounter{equation}{9}\begin{equation}d=c*(y[i]-y[i+1])-s(x[i]-x[i+1]) \end{equation} \setcounter{equation}{10}\begin{equation}a=(x[i]-x\_a)*(y[i]-y[i+1])-(y[i]-y\_a)*(x[i]-x[i+1]) \end{equation} \setcounter{equation}{11}\begin{equation}m=c*(y[i]-y\_a)-s*(x[i]-x\_a) \end{equation}Wie ist der Autor auf diese Gleichungen gekommen? Und wie sind die Parameter d,a und m zu interpretieren?
Grüße Markus
-
Und deine Frage?
-
Eure Latex Umgebung ist ziemlich hinüber. Die Gleichung (12) ist mir jetzt glaube ich auch klar geworden. Ich poste meinen Ansatz morgen.
Grüße Markus
-
Ich habe mir nochmal die verschiedenen Algorithmen angeschaut. Kann es sein, dass der Algorithmus mit der Umlaufzahl http://de.wikipedia.org/wiki/Windungszahl schneller und aussagekräftiger ist? Mit Ihm müsste man sogar eine Fläche in einer Fläche bestimmen können?
Welchen Algorithmus würdet Ihr mir empfehlen? Allerdings ist der Umlaufzahl-Algorithmus nicht ganz so simpel wie in manchen Dokus erläutert, immerhin muss man überprüfen das die Polygon-Kante den nach rechts waagerecht verlaufendene Strahl, von Punkt A, schneidet und nicht links am Punkt A vorbei geht.
Grüße Markus
-
Dieser Thread wurde von Moderator/in pumuckl aus dem Forum C++ in das Forum Mathematik und Physik verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
