 Mirror

Determine if a polygon is concave or not (Views: 100)

 Problem/Question/Abstract:How to determine if a polygon is concave or notAnswer:I would check the area of 3 triangle points of the polygon. It should always be positive. Here is the code:function TriXYArea(PBegin, PMiddle, PEnd: TXYPoint): TDouble;begin  TriXYArea := (PBegin.y + PMiddle.y) / 2 * (PMiddle.x - PBegin.X) + (PMiddle.y +    PEnd.y) / 2 * (PEnd.x - PMiddle.X) + (PBegin.y + PEnd.y) / 2 * (PBegin.x -      PEnd.X);end;If the polygon is clockwise oriented (the Gauss integral is positive), it should work like this:function IsConvex(Poly: array of TXYPoint);var  i: Integer;  First, Mid, Last: TXYPoint;begin  Result := False;  for i := 1 to High(Poly) do  begin    if i < High(Poly) then    begin      First := Poly[i - 1];      Mid := Poly[i];      Last := Poly[i + 1];    end    else    begin      First := Poly[i - 1];      Mid := Poly[i];      Last := Poly;    end;    if TriXYArea(First, Mid, Last) < 0 then      exit;  end;  Result := True;end;If you only want to use the angle, here is the function:function TriXYAngle(PBegin, PMiddle, PEnd: TXYPoint): TDouble;var  AC, ACX, ACG, TR: TDouble;begin  TriXYAngle := 1E38;  TR := TriXYArea(PBegin, PMiddle, PEnd);  AC := TriXYCos(PBegin, PMiddle, PEnd);  ACX := ArcCos(AC);  ACG := ACX / Pi * 180;  if Tr >= 0 then    TriXYAngle := +ACG;  if Tr < 0 then    TriXYAngle := 360 - ACG;  if AC = 1E38 then    TriXYAngle := 1E38;end;

<< Back to main page