Simple ConvexityDefects using concavehull

type
  EConvexityDefects = (cdNone, cdAll, cdMinimal);

(*
  Finds the defects in relation to a convex hull of the given concave hull.
  cdAll     -> Keeps all convex points as well.
  cdMinimal -> keeps the convex points that was linked to a defect
  cdNone    -> Only defects
*)
function ConvexityDefects(ConcavePoly: TPointArray; Epsilon: Single; Mode:EConvexityDefects=cdNone): TPointArray;
var
  x,y,i,j,k: Int32;
  dist, best: Single;
  pt: TPoint;
  convex: TPointArray;
begin
  convex  := ConcavePoly.ConvexHull();

  for x:=0 to High(ConcavePoly) do
  begin
    i := convex.IndexOf(ConcavePoly[x]);

    if i <> -1 then
    begin
      j := (i+1) mod Length(convex);
      y := ConcavePoly.IndexOf(convex[j]);

      best := 0;
      for k:=y to x do
      begin
        dist := DistToLine(ConcavePoly[k], convex[i], convex[j]);
        if (dist > best) then
        begin
          best := dist;
          pt := ConcavePoly[k];
        end;
      end;

      if best >= Epsilon then
      begin
        if (Mode = cdMinimal) and ((Length(Result) = 0) or (Result[High(Result)] <> convex[j])) then Result += convex[j];
        Result += pt;
        if Mode = cdMinimal then Result += convex[i];
      end;

      if Mode = cdAll then
        Result += convex[i];
    end;
  end;
end;


// original simpler function returns only defects
function ConvexityDefects(ConcavePoly: TPointArray; Epsilon: Single): TPointArray;
var
  x,y,i,j,k: Int32;
  dist, best: Single;
  pt: TPoint;
  convex: TPointArray;
begin
  convex  := ConcavePoly.ConvexHull();

  for x:=0 to High(ConcavePoly) do
  begin
    i := convex.IndexOf(ConcavePoly[x]);

    if i <> -1 then
    begin
      j := (i+1) mod Length(convex);
      y := ConcavePoly.IndexOf(convex[j]);

      best := 0;
      for k:=y to x do
      begin
        dist := DistToLine(ConcavePoly[k], convex[i], convex[j]);
        if (dist > best) then
        begin
          best := dist;
          pt := ConcavePoly[k];
        end;
      end;

      if best >= Epsilon then Result += pt;
    end;
  end;
end;