Mirror

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


Problem/Question/Abstract:

How to determine if a polygon is concave or not

Answer:

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[0];
    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