Ist ein Punkt in einem Polygon

[Medium]

Vom Prinzip her müsste doch folgendes eigentlich völlig ausreichen. Ich hab es bei mir mehrfach im Einsatz, und es geht mit konvexen, konkaven, überschlagenen und sogar mit Polygonen mit Loch (so lange man sich an die Konvention hält, dass das Loch-Polygon dem äusseren Polygon entgegen orientiert ist).

Delphi-Quellcode:

function PtInPoly(const points: array of TPoint; p: TPoint): Boolean;
var
  i     : Integer;
  angle : Double;

  function Angle2D(x1, y1, x2, y2: Double): Double;
  var
    dtheta, theta1, theta2: Double;
  begin
    theta1 := ArcTan2(y1, x1);
    theta2 := ArcTan2(y2, x2);
    dtheta := theta2 - theta1;
    while (dtheta > PI) do
       dtheta := dtheta - 2*pi;
    while (dtheta < -PI) do
       dtheta := dtheta + 2*pi;
    result := dtheta;
  end;

begin
  angle := 0;
  for i := 0 to High(points) do
  begin
    p1.X := points[i].X - p.X;
    p1.Y := points[i].Y - p.Y;
    p2.X := points[(i+1) mod Length(points)].X - p.X;
    p2.Y := points[(i+1) mod Length(points)].Y - p.Y;
    angle := angle + Angle2D(p1.X, p1.Y, p2.X, p2.Y);
  end;
  result := Abs(angle) < pi;
end;

Bislang hatte ich mit keinen Exceptions oder Polygonen zu tun, die nicht richtig erkannt wurden.