 |
|||
| HSG |
|
Eine Inside-Funktion für konvexe Polygone
 |
Wir gehen davon aus, dass die Ecken des Polygons im Gegenuhrzeigersinn, also linksherum
umlaufen werden. Dann liegt ein Punkt z.B. B, genau dann im Inneren des Polygons, wenn der
Punkt links von jeder Kante (dh. ccw = +1) liegt.
Im Beispiel liegt A außerhalb, weil ccw(P0,P1,A) = -1 gilt. Für den Punkt C gilt sogar ccw(P2,P3,C) = -1 und ccw(P3,P4,C) = -1. Dass die Überlegung für nicht-konvexe Polygone nicht mehr gilt, zeigt der zweite Teil der Skizze: D liegt innerhalb des Polygons, aber ccw(P2,P3,D) = -1. |
Eine mögliche Realisierung der Funktion zeigt folgender Quelltext-Auszug:
function inside(Punkt : TPunkt; P : array of TPunkt) : boolean;
var
i,n : integer;
innen : boolean;
begin
n := Length(P);
innen := true;
i := 0;
while (i
|
inside.zip