convex_hull.exs

defmodule ConvexHull do
  @type coordinate :: {number, number}
  @type point_list :: [coordinate]

  @spec find(point_list) :: point_list
  def find(points) do
    sorted = points |> Enum.sort
    left = sorted |> do_half_calc
    right = sorted |> Enum.reverse |> do_half_calc
    [left, right] |> Enum.concat
  end

  @spec do_half_calc(point_list) :: point_list
  defp do_half_calc(points) do
    points
    |> Enum.reduce([], &add_to_convex_list/2)
    |> tl
    |> Enum.reverse
  end

  @spec perp_prod(coordinate, coordinate, coordinate) :: number
  defp perp_prod({x0, y0}, {x1, y1}, {x2, y2}) do
    (x1 - x0) * (y2 - y0) - (y1 - y0) * (x2 - x0) 
  end

  @spec add_to_convex_list(coordinate, point_list) :: point_list
  defp add_to_convex_list(p2, list) do
    {:ok, new_tail} =
      list
      |> stream_tails
      |> Stream.drop_while(fn tail -> oa_left_of_ob(p2, tail) end)
      |> Enum.fetch(0)
    [p2 | new_tail]
  end

  @spec oa_left_of_ob(coordinate, point_list) :: number
  defp oa_left_of_ob(b, [a, o | _]), do: perp_prod(o, a, b) <= 0
  defp oa_left_of_ob(_, _), do: false

  @spec stream_tails(point_list) :: Enum.t(point_list) 
  defp stream_tails(list) do
    tails = Stream.unfold(list, fn [_ | t] -> {t, t} end)
    Stream.concat([list], tails)
  end

end


ExUnit.start

defmodule ConvexHullStart do
  use ExUnit.Case, async: true

  @points for x <- 0..9, y <- 0..9, do: {x, y}

  test "finding the convex hull for all points (0,0) .. (9,9)" do
    assert ConvexHull.find(@points) == [{0, 0}, {9, 0}, {9, 9}, {0, 9}]
  end
end