Find the points which form a convex hull from a set of arbitrary two dimensional points.

For example, given the points (16,3), (12,17), (0,6), (-4,-6), (16,6), (16,-7), (16,-3), (17,-4), (5,19), (19,-8), (3,16), (12,13), (3,-4), (17,5), (-3,15), (-3,-9), (0,11), (-9,-3), (-4,-2) and (12,10) the convex hull would be (-9,-3), (-3,-9), (19,-8), (17,5), (12,17), (5,19) and (-3,15).




See also
 Convex Hull (youtube)
 http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/


 
program ConvexHulls;
 
{$APPTYPE CONSOLE}
 
{$R *.res}
 
uses
  System.Types,
  System.SysUtils,
  System.Generics.Defaults,
  System.Generics.Collections;
 
  function Ccw(const a, b, c: TPoint): Boolean;
  begin
    Result := ((b.X - a.X) * (c.Y - a.Y)) > ((b.Y - a.Y) * (c.X - a.X));
  end;
 
  function ConvexHull(const p: TList<TPoint>): TList<TPoint>;
  var
    pt: TPoint;
    i, t: Integer;
  begin
    Result := TList<TPoint>.Create;
 
    if (p.Count = 0) then Exit;
 
    p.Sort(TComparer<TPoint>.Construct(
          function(const Left, Right: TPoint): Integer
          begin
            Result := Left.X - Right.X;
          end
    ));
 
    // lower hull
    for i := 0 to p.Count-1 do
    begin
      pt := p[i];
      while ((Result.Count >= 2) and (not Ccw(Result[Result.Count - 2], Result[Result.Count - 1], pt))) do
      begin
        Result.Delete(Result.Count - 1);
      end;
      Result.Add(pt);
    end;
 
    // upper hull
    t := Result.Count + 1;
    for i := p.Count-1 downto 0 do
    begin
      pt := p[i];
      while ((Result.Count >= t) and (not Ccw(Result[Result.Count - 2], Result[Result.Count - 1], pt))) do
      begin
        Result.Delete(Result.Count - 1);
      end;
      Result.Add(pt);
    end;
 
    Result.Delete(Result.Count - 1);
  end;
 
var
  points: TList<TPoint>;
  hull: TList<TPoint>;
  i: Integer;
begin
 
  hull := nil;
  points := TList<TPoint>.Create;
  try
 
    points.AddRange([
        Point(16, 3),
        Point(12, 17),
        Point(0, 6),
        Point(-4, -6),
        Point(16, 6),
        Point(16, -7),
        Point(16, -3),
        Point(17, -4),
        Point(5, 19),
        Point(19, -8),
        Point(3, 16),
        Point(12, 13),
        Point(3, -4),
        Point(17, 5),
        Point(-3, 15),
        Point(-3, -9),
        Point(0, 11),
        Point(-9, -3),
        Point(-4, -2),
        Point(12, 10)
        ]);
 
    hull := ConvexHull(points);
 
    // Output the result
    Write('Convex Hull: [');
    for i := 0 to hull.Count-1 do
    begin
      if (i > 0) then Write(', ');
      Write(Format('(%d, %d)', [hull[i].X, hull[i].Y]));
    end;
    WriteLn(']');
 
  finally
    hull.Free;
    points.Free;
  end;
 
end.
 