function TPABounds(TPA: TPointArray): TBox;
var
  h, i: Integer;
begin
  h := High(TPA);
  if (h > -1) then
  begin
    Result.X1 := TPA[0].X; Result.X2 := TPA[0].X;
    Result.Y2 := TPA[0].Y; Result.Y2 := TPA[0].Y;
    if (h > 0) then
    for i := 1 to h do
    begin
      if (TPA[i].X < Result.X1) then
        Result.X1 := TPA[i].X
      else if (TPA[i].X > Result.X2) then
        Result.X2 := TPA[i].X;
      if (TPA[i].Y < Result.Y1) then
        Result.Y1 := TPA[i].Y
      else if (TPA[i].Y > Result.Y2) then
        Result.Y2 := TPA[i].Y;
    end;
  end;
end;

function CrossTurn(p, q, r: TPoint): Boolean;
var
  sum1,sum2:Single; //Int?
begin
  //Do the vectors pq:qr form a right turn, or not?
  Result := False;
  sum1 := q.x*r.y + p.x*q.y + r.x*p.y;
  sum2 := q.x*p.y + r.x*q.y + p.x*r.y;
  if (sum1 - sum2) < 0 then
    Result := True;
end;

function CleanAndSortTPA(TPA:TPointArray): TPointArray;
var
  Matrix: Array of TBoolArray;
  i,c,H,j,idx,x,y: Integer;
  Bounds:TBox;
begin
  Bounds := TPABounds(TPA);
  H := High(TPA);
  SetLength(Matrix, (Bounds.Y2-Bounds.Y1)+1);
  for i:=0 to Bounds.y2 do
    SetLength(Matrix[i], (Bounds.X2-Bounds.X1)+1);
  C := 0;
  for i:=0 to H do
  begin
    x := TPA[i].x - Bounds.X1;
    y := TPA[i].y - Bounds.Y1;
    if Matrix[y][x] = True then
      Continue;
    Matrix[y][x] := True;
    Inc(C);
  end;
  SetLength(Result, C);

  idx := 0;
  for x:=Bounds.x1 to Bounds.x2 do
    for y:=Bounds.y1 to Bounds.y2 do
      if Matrix[y-Bounds.y1][x-Bounds.x1] = True then
      begin
        Result[idx] := Point(x,y);
        Inc(idx);
        if (idx >= C) then Exit;
      end;
  SetLength(Matrix, 0);
end;

function ConvexHull(TPA:TPointArray): TPointArray;
var
  Points, Lower: TPointArray;
  LH,H,I,UH:Integer;
begin
  // Get a local list copy of the points, and remove dupes.
  points := CleanAndSortTPA(TPA);
  H := High(points);
  if H <= 0 then Exit;

  // Upper half..
  UH := 2;
  SetLength(Result, H+1);
  Result[0] := Points[0];
  Result[1] := Points[1];
  for i:=2 to H do
  begin
    Result[UH] := points[i];
    Inc(UH);
    while (UH > 2) and not(CrossTurn(Result[UH-3], Result[UH-2], Result[UH-1])) do
    begin
      Dec(UH);
      Result[UH-1] := Result[UH];
    end;
  end;

  // Lower half..
  LH := 2;
  SetLength(Lower, H+1);
  Lower[0] := points[H];
  Lower[1] := points[H-1];
  for i:=2 to H do
  begin
    Lower[LH] := points[H-i];
    Inc(LH);
    while (LH > 2) and not(CrossTurn(Lower[LH-3], Lower[LH-2], Lower[LH-1])) do
    begin
      Dec(LH);
      Lower[LH-1] := Lower[LH];
    end;
  end;

  Dec(LH);
  SetLength(Result, UH+LH);
  for i:=UH to (UH+LH)-1 do
    Result[i] := Lower[i-UH];

  SetLength(Lower, 0);
  SetLength(Points, 0);
end;

function SamePoints(P1, P2:TPoint):Boolean;
begin
  Result := False;
  if ((P1.x = P2.x) and (P1.y = P2.y)) then
    Result := True;
end;

{ Given a TPA - This function will connect each point, from first to last }
function ConnectPts(Pts:TPointArray):TPointArray;
var
  i,j,h,l,rl,a: Integer;
  f,t:TPoint;
  AdivL: Extended;
begin
  h := high(pts);
  for i:=0 to h do
  begin
    j := i+1;
    if i=h then
      j:=0;
    f := pts[i];
    t := pts[j];
    rl := length(Result);
    if not(SamePoints(f, t)) then
    begin
      l := Max(Round(Abs(f.X - t.X)), Round(Abs(f.Y - t.Y)));
      SetLength(Result, rl+l+1);
      for a := 0 to l do begin
        AdivL := a / Extended(l);
        Result[rl+a] := Point(f.X + Round((t.X - f.X) * AdivL), f.Y + Round((t.Y - f.Y) * AdivL));
      end;
    end
    else
    begin
      SetLength(Result,rl + 1);
      Result[rl] := f
    end;
  end;
end;

function RandomTPA(Amount:Integer; MinX,MinY,MaxX,MaxY:Integer): TPointArray;
var i:Integer;
begin
  SetLength(Result, Amount+1);
  for i:=0 to Amount do
  begin
    Result[i] := Point(RandomRange(MinX, MaxX), RandomRange(MinY, MaxY));
  end;
end;

//******* Plot a few shapes using this algorithm *******//
var
  TPA,CTPA: TPointArray;
  bmp: Integer;
begin
  bmp := CreateBitmap(700, 700);

  TPA := RandomTPA(10000, 100,100,595,595);
  CTPA := CopyTPA(TPA);
  CTPA := ConvexHull(CTPA);
  //pp_TPAConvexHull(CTPA);
  CTPA := ConnectPts(CTPA);

  DrawTPABitmap(bmp, TPA, 357435);
  DrawTPABitmap(bmp, CTPA, 255);

  DisplayDebugImgWindow(700,700);
  DrawBitmapDebugImg(bmp);
  FreeBitmap(bmp);
end.