Ist ein Punkt in einem Polygon

[LoCrux]

HI JasonDX,

war mir soweit alles klar..

Vielleicht gefällt Dir die Lösung besser..

Delphi-Quellcode:

PROCEDURE AddPolyPoint(VAR APoly:TPolyPoints;pnt:TPoint);
VAR
  pos : INTEGER;
BEGIN
  pos := HIGH(APoly)+1;
  SETLENGTH(APoly,pos+1);
  APoly[pos] := pnt;
  FPolyNew := YES;
END;

FUNCTION CopyPolyRange(APoly:TPolyPoints;startindex,endindex:INTEGER):TPolyPoints;
VAR
  cnt   : INTEGER;
  tPoly : TPolyPoints;
BEGIN
  IF (startindex>=0) AND (HIGH(APoly)>=endindex)
  THEN FOR cnt := startindex TO EndIndex DO AddPolyPoint(tPoly,APoly[cnt]);
  RESULT := tPoly;
END;

FUNCTION PointInTriangle(Tri:TPolyPoints;pnt:TPoint):BOOLEAN;
VAR
  a,b,c : DOUBLE;
BEGIN
 IF (HIGH(Tri)<3)
 THEN BEGIN
   // NOW THE POINT SHOULD BE INDEXED WITH 3 IN THE TRI ARRAY
   Self.AddPolyPoint(Tri,pnt);
   // FIRST PLACE A POINT TO ZERO NOW MOVE THE OTHERS RESPECTIVLY
   Tri[1] := SubPoints(Tri[1],Tri[0]);
   Tri[2] := SubPoints(Tri[2],Tri[0]);
   Tri[3] := SubPoints(Tri[3],Tri[0]);
   Tri[0] := SubPoints(Tri[0],Tri[0]);
   // COMPUTE
   a := (Tri[1].x*Tri[2].y)-(Tri[2].x*Tri[1].y);
   b := (Tri[1].x*Tri[3].y)-(Tri[3].x*Tri[1].y);
   c := (Tri[2].x*Tri[3].y)-(Tri[3].x*Tri[2].y);
   // RESULT
   RESULT := ((a*b)>0) AND ((a*c)<0) AND ((a*(a-b+c))>0);  // IF TRUE THEN POINT IN TRIANGLE
 END;
END;

FUNCTION ClosePoly(APoly:TPolyPoints):TPolyPoints;
BEGIN
  IF HIGH(APoly)>2
  THEN BEGIN
    RESULT := APoly;
    AddPolyPoint(RESULT,APoly[0]);
  END;
END;

FUNCTION PointInPoly_A1(APoly:TPolyPoints;Point:TPoint;Depth:INTEGER):BOOLEAN;
VAR
  cnt        : INTEGER;
  HighPoly   : TPolyPoints;
  LowPoly    : TPolyPoints;
  ePoly      : TPolyPoints;
  tPoly      : TPolyPoints;
BEGIN
  IF HIGH(APoly)>2
  THEN BEGIN
    ePoly    := ClosePoly(APoly);
    LowPoly  := CopyPolyRange(ePoly,LOW(ePoly)   ,HIGH(ePoly) DIV 2);
    HighPoly := CopyPolyRange(ePoly,HIGH(LowPoly),HIGH(ePoly));
    RESULT   := PointInPoly_A1(LowPoly,Point,Depth+1);
    IF NOT(RESULT) THEN RESULT := PointInPoly_A1(HighPoly,Point,Depth+1);
  END
  ELSE IF (HIGH(APoly)=2) THEN RESULT := PointInTriangle(APoly,Point);
END;

Hänge mal das komplette Testprojekt+Source mit an....

ABER IST QUICK'N'DIRTY... UND GILT AUCH NUR FÜR SICH NICHT ÜBERSCHNEIDENDE POLYGONE.. MUSS AN DER TRINAGULIERUNG NOCH ARBEITEN...