defmodule Scurry.Polygon do
  @moduledoc """
  Functions related to polygons and lines relevant for 2D map pathfinding.

  This provides functions for;

  * line of sight between two points
  * classify polygon vertices as concave or vertex
  * intersections of lines and polygons
  * checking if points are inside/outside polygons
  * finding nearest point on a polygon and distances

  Polygons are
  * A list of vertices, `[{x1, y1}, {x2,y2}, ...]` defined as a `list(vector)`.
  * They **must not** be closed, ie. last vertex should not be equal to the first.
  * They **must be** in clockwise order in screen coordinates, otherwise
    convex/concave classification will be inversed as it traverses the egdes.

  > ### Order of vertices {: .warning}
  >
  > Polygons **must** be defined in clockwise order in screen coordinates. This is necessary
  > for the convex/concave classification. It counter clock, it  will be inversed as it
  > traverses the egdes.
  >
  > Here's a crude drawing of an example of the M shaped polygon used for many tests/docs.
  >
  > `polygon = [{0, 0}, {10, 0}, {20, 0}, {20, 20}, {10, 10}, {0, 20}]`
  > ![Order of vertices](imgs/polygon.png)
  """

  alias Scurry.Geo
  alias Scurry.Vector
  use Scurry.Types

  @doc """
  Checks if a line intersects a polygon.

  This is a boolean version of `intersects/2`. For most cases using
  `intersections/3` will be a better choice to get intersections.

  ## Params

  * `polygon` (`t:polygon/0`), the polygon to check.
  * `line` (`t:line/0`), the line to check if it intersects `polygon`.

  ## Returns

  `true` or `false` wether the line intersects the polygon or not.

  ## Examples
      # A vaguely M shaped polygon
      iex> Polygon.intersects?([{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}], {{1, -0.5}, {1, 0.5}})
      true
      iex> Polygon.intersects?([{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}], {{1, -1}, {1, 0}})
      true
      iex> Polygon.intersects?([{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}], {{1, -2}, {1, -1}})
      false
  """
  @spec intersects?(polygon(), line()) :: boolean()
  def intersects?(polygon, line) do
    case intersects(polygon, line) do
      :nointersection -> false
      _ -> true
    end
  end

  @doc """
  Checks if a line intersects a polygon.

  Find an intersection (if any) between `polygon` and `line`. For most cases
  using `intersections/3` will be a better choice to get intersections.

  ## Params

  * `polygon` (`t:polygon/0`), the polygon to check.
  * `line` (`t:line/0`), the line to check if it intersects `polygon`.

  ## Returns

  This relates to `Scurry.Geo.line_segment_intersection/2`.

  - `:nointersection`, `line` does not intersect `polygon`
  - `{:point_intersection, vector}`
  - `{;intersection, line}`
  - `:on_segment`

  ## Examples
      # A vaguely M shaped polygon
      iex> Polygon.intersects([{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}], {{1, -0.5}, {1, 0.5}})
      {:point_intersection, {1.0, 0.0}}
      iex> Polygon.intersects([{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}], {{0.5, -0.5}, {0.5, 0.5}})
      {:intersection, {0.5, 0.0}}
      iex> Polygon.intersects([{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}], {{0.5, -1}, {0.5, 0}})
      {:point_intersection, {0.5, 0.0}}
      iex> Polygon.intersects([{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}], {{0.5, -2}, {0.5, -1}})
      :nointersection
      iex> Polygon.intersects([{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}], {{2, 0.1}, {2, 0.9}})
      :on_segment
  """
  @spec intersects(polygon(), line()) :: :nointersection | :on_segment | {:intersection, vector()} | {:poiont_intersection, vector() }
  def intersects(polygon, line) do
    prev_point = List.last(polygon)
    intersects_helper(polygon, line, prev_point)
  end

  @doc """
  Get all intersections of a line with a polygon including their type.

  This function basically calls `Geo.line_segment_intersection/2` for every segment
  of the `polygon` against the `line` and filters the results to only include
  the list of intersection points.

  ## Params

  * `polygon` (`t:polygon/0`), the polygon to check.
  * `line` (`t:line/0`), the line check for intersections against `polygon`.

  ## Options

  * `:allow_points` (default `false`) whether a `on_point` intersection
  should be considered an intersection or not. This varies from use
  cases. Eg. when building a polygon, points will be connected and thus
  intersect if `true`. This may not be the desired result, so `false` won't
  consider points intersections.

  ## Returns

  * a list of `t:vector/0` indicating where the line intersects
  * `[]` if there's no intersections.

  ## Examples
      iex> polygon = [{0, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}]
      [{0, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}]
      iex> line = {{1, -1}, {1, 3}}
      {{1, -1}, {1, 3}}
      iex> Polygon.intersections(polygon, line)
      [{1.0, 0.0}]
      iex> Polygon.intersections(polygon, line, allow_points: true)
      [{1.0, 0.0}, {1.0, 0.5}]
  """
  @spec intersections(polygon(), line(), [allow_points: boolean()]) :: list(vector())
  def intersections(polygon, line, opts \\ []) do
    allow_points = Keyword.get(opts, :allow_points, false)
    prev_point = List.last(polygon)

    intersects_helper(polygon, line, prev_point, [])
    |> Enum.filter(fn
      {:intersection, _} -> true
      {:point_intersection, _} -> allow_points
      _ -> false
    end)
    |> Enum.map(fn {_, point} -> point end)
    |> Enum.dedup()
  end

  @doc """
  Get first intersection of a line with a polygon.

  The "opposite" of `last_intersection/2`.

  ## Params

  * `polygon` (`t:polygon/0`) a polygon to check for an intersection with `line`.
  * `line` (`t:line/0`). The line to check for intersections with `polygon`.

  A `t:line/0` is a tuple of two `t:vector/0` and the first is considered the head
  of the line and "first" in this context means nearest to that point.

  ## Returns

  * A `t:vector/0` indicating where `line` first intersects `polygon`.
  * `nil` if there's no intersection.

  ## Examples

      # A square around 0,0
      iex> square = [{-1, -1}, {1, -1}, {1, 1}, {-1, 1}]
      [{-1, -1}, {1, -1}, {1, 1}, {-1, 1}]
      iex> Polygon.first_intersection(square, {{0, -2}, {0, 2}})
      {0.0, -1.0}
      iex> Polygon.first_intersection(square, {{0, 2}, {0, -2}})
      {0.0, 1.0}
      iex> Polygon.first_intersection(square, {{2, -2}, {2, 2}})
      nil
  """
  @spec first_intersection(polygon(), line()) :: nil | vector()
  def first_intersection(polygon, {a, _b} = line) do
    Enum.min_by(
      intersections(polygon, line),
      fn ip ->
        Vector.distance(a, ip)
      end,
      fn ->
        nil
      end
    )
  end

  @doc """
  Get last intersection of a line with a polygon.

  The "opposite" of `first_intersection/2`.

  ## Params

  * `polygon` (`t:polygon/0`) a polygon to check for an intersection with `line`.
  * `line` (`t:line/0`). The line to check for intersections with `polygon`.

  A `t:line/0` is a tuple of two `t:vector/0` and the last is considered the tail
  of the line and "last" in this context means nearest to that point.

  ## Returns

  * A `t:vector/0` indicating where `line` last intersects `polygon`
  * `nil` if there's no intersection.

  ## Examples

      # A square around 0,0
      iex> square = [{-1, -1}, {1, -1}, {1, 1}, {-1, 1}]
      [{-1, -1}, {1, -1}, {1, 1}, {-1, 1}]
      iex> Polygon.last_intersection(square, {{0, -2}, {0, 2}})
      {0.0, 1.0}
      iex> Polygon.last_intersection(square, {{0, 2}, {0, -2}})
      {0.0, -1.0}
      iex> Polygon.last_intersection(square, {{2, -2}, {2, 2}})
      nil
  """
  @spec last_intersection(polygon(), line()) :: nil | vector()
  def last_intersection(polygon, {a, _b} = line) do
    Enum.max_by(
      intersections(polygon, line),
      fn ip ->
        Vector.distance(a, ip)
      end,
      fn ->
        nil
      end
    )
  end

  defp intersects_helper([], _line, _prev_point) do
    :nointersection
  end

  defp intersects_helper([next_point | polygon], line, prev_point) do
    case Geo.line_segment_intersection(line, {prev_point, next_point}) do
      :parallel -> intersects_helper(polygon, line, next_point)
      :none -> intersects_helper(polygon, line, next_point)
      :on_segment -> :on_segment
      {:intersection, _} = result -> result
      {:point_intersection, _} = result -> result
    end
  end

  defp intersects_helper([], _line, _prev_point, acc) do
    acc
  end

  defp intersects_helper([next_point | polygon], line, prev_point, acc) when is_list(acc) do
    v = Geo.line_segment_intersection(line, {prev_point, next_point})
    intersects_helper(polygon, line, next_point, acc ++ [v])
  end

  @doc """
  Split a polygon into concave and convex vertices.

  When doing pathfinding, there will typically be a outer polygon bounding the
  "world" and multiple inner polygons describing "holes/obstacles".

  The path can only be within the outer polygon and has to "walk around" the
  holes.

  Classifying the polygons into concave and convex is used to determine the
  walkable graph.

  * The outer polygon's concave (pointing into the world) vertices are used.
    used.
  * The holes' convex (point out of the hole, into the world) vertices used used.

  In code, this looks like

  ```
  # Get the concave vectices of the bounding polygon
  {concave, _convex} = Polygon.classify_vertices(world)

  # Get al lthe convex vertices of all the holes
  convex = Enum.reduce(holes, [], fn points, acc ->
    {_, convex} = Polygon.classify_vertices(points)
    acc ++ convex
  end)

  # The initial walk map is the combined set
  vertices = concave ++ convex
  ```

  ## Params

  * `polygon` (`t:polygon/0`) the polygon to classify.

  ## Returns

  `{list of concave vertices, list of convex}`.

  * A tuple of two lists of `t:vector/0`.
  * The first list are all the _concave_ vertices or `[]` if none
  * The second list are all the _convex_ vertices or `[]` if none

  ## Note

  Three points that fall on the same line (`[{0, 0}, {1, 0}, {2, 0}]`) does not
  match neither the concave/convex definition (angle greater-than / less-than
  180 degrees) this function will discard these via `classify_vertex/2`.

  ## Examples
      # A vaguely M shaped polygon
      iex> Polygon.classify_vertices([{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}])
      {[{1, 0.5}], [{0, 0}, {2, 0}, {2, 1}, {0, 1}]}

      # A square around 0,0
      iex> Polygon.classify_vertices([{-1, -1}, {1, -1}, {1, 1}, {-1, 1}])
      {[], [{-1, -1}, {1, -1}, {1, 1}, {-1, 1}]}

      # A flat line
      iex> Polygon.classify_vertices([{0, 0}, {1, 0}, {2, 0}])
      {[], []}
  """
  @spec classify_vertices(polygon()) :: {[vector()], [vector()]}
  def classify_vertices(polygon) do
    {concave, convex} =
      Enum.reduce(polygon, {0, []}, fn point, {idx, acc} ->
        {idx + 1, acc ++ [{point, classify_vertex(polygon, idx)}]}
      end)
      |> elem(1)
      |> Enum.reject(fn {_point, type} -> type == :neither end)
      |> Enum.split_with(fn {_point, type} -> type == :concave end)

    # Remove the type
    {Enum.map(concave, fn {p, _} -> p end), Enum.map(convex, fn {p, _} -> p end)}
  end

  @doc """
  Check if a specific vertex is concave, convex or neither.

  Whehter a vertex is concave or convex is defined by it pointing out - it's
  inner angle is less than 180 means convex and more than 180 means concave.

  When testing a vertex, keep this in mind and negate appropriately depending
  on whether it's the boundary polygon or a hole polygon being tested.

  ## Params

  * `polygon` (`t:polygon/0`) the polygon in which to check a vertex.
  * `at` (`t:integer/0`), which vertex in the `polygon` to check.

  ## Returns

  * `:convex` for a convex vertice.
  * `:concave` for a concave vertice.
  * `:neither` for a vertice that's a straight edge, ie. 180 degrees.

  ## Examples
      # A vaguely M shaped polygon
      iex> m = [{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}]
      [{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}]
      iex> Polygon.classify_vertex(m, 0)
      :convex
      iex> Polygon.classify_vertex(m, 1)
      :neither
      iex> Polygon.classify_vertex(m, 4)
      :concave
  """
  @spec classify_vertex(polygon(), integer()) :: :concave | :convex | :neither
  def classify_vertex(polygon, at) do
    # See https://www.david-gouveia.com/pathfinding-on-a-2d-polygonal-map
    next = Enum.at(polygon, rem(at + 1, length(polygon)))
    current = Enum.at(polygon, at)
    prev = Enum.at(polygon, at - 1)

    left = Vector.sub(current, prev)
    right = Vector.sub(next, current)
    cross = Vector.cross(left, right)

    cond do
      cross < 0 -> :concave
      cross > 0 -> :convex
      true -> :neither
    end
  end

  @doc """
  Check if a specific vertex in a polygon is concave

  ## Params

  * `polygon` (`t:polygon/0`) the polygon in which to check a vertex.
  * `at` (`t:integer/0`), which vertex in the `polygon` to check.

  ## Returns

  `true` if the vertex is concave, otherwise `false`

  See also `classify_vertex/2`.

  ## Examples
      # A vaguely M shaped polygon
      iex> m = [{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}]
      [{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}]
      iex> Polygon.is_concave?(m, 0)
      false
      iex> Polygon.is_concave?(m, 1)
      false
      iex> Polygon.is_concave?(m, 2)
      false
      iex> Polygon.is_concave?(m, 3)
      false
      iex> Polygon.is_concave?(m, 4)
      true
      iex> Polygon.is_concave?(m, 5)
      false
  """
  @spec is_concave?(polygon(), number()) :: boolean()
  def is_concave?(polygon, at) do
    classify_vertex(polygon, at) == :concave
  end

  @doc """
  Check if a specific vertex in a polygon is convex

  ## Params

  * `polygon` (`t:polygon/0`) the polygon in which to check a vertex.
  * `at` (`t:integer/0`), which vertex in the `polygon` to check.

  ## Returns

  `true` if the vertex is convex, otherwise `false`

  See also `classify_vertex/2`.

  ## Examples
      # A vaguely M shaped polygon
      iex> m = [{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}]
      [{0, 0}, {1, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}]
      iex> Polygon.is_convex?(m, 0)
      true
      iex> Polygon.is_convex?(m, 1)
      false
      iex> Polygon.is_convex?(m, 2)
      true
      iex> Polygon.is_convex?(m, 3)
      true
      iex> Polygon.is_convex?(m, 4)
      false
      iex> Polygon.is_convex?(m, 5)
      true
  """
  @spec is_convex?(polygon(), number()) :: boolean()
  def is_convex?(polygon, at) do
    classify_vertex(polygon, at) == :convex
  end

  # Alternate, https://sourceforge.net/p/polyclipping/code/HEAD/tree/trunk/cpp/clipper.cpp#l438
  @doc """
  Check if a point is inside a polygon or not.

  ## Params

  * `polygon` (`t:polygon/0`) the polygon to check against.
  * `point` (`t:vector/0`) the point to check if is inside (or on) `polygon`.

  ## Options

  * `allow_border`, defaults to `true` and allows `point` to be the `polygon` edges.

  ## Returns

  * `true` is the `point` is inside the `polygon`
  * `true` is the `point` is on `polygon` edges if `allow_border` is `true`.

  ## Examples

      # A square around 0,0
      iex> square = [{-1, -1}, {1, -1}, {1, 1}, {-1, 1}]
      [{-1, -1}, {1, -1}, {1, 1}, {-1, 1}]
      iex> Polygon.is_inside?(square, {0, 0})
      true
      iex> Polygon.is_inside?(square, {-1, 0})
      true
      iex> Polygon.is_inside?(square, {-1, 0}, [allow_border: false])
      false
      iex> Polygon.is_inside?(square, {-2, 0})
      false

  """
  @spec is_inside?(polygon(), vector(), [allow_border: boolean()]) :: boolean()
  def is_inside?(polygon, point, opts \\ [])

  def is_inside?(polygon, _point, _opts) when length(polygon) < 3 do
    false
  end

  # See https://www.david-gouveia.com/pathfinding-on-a-2d-polygonal-map
  def is_inside?(polygon, {_, _} = point, opts) when is_list(polygon) do
    epsilon = 0.5

    prev = Enum.at(polygon, -1)
    prev_sq_dist = Vector.distance_squared(prev, point)

    {_, _, is_inside} =
      Enum.reduce_while(polygon, {prev, prev_sq_dist, false}, fn current,
                                                                 {prev, prev_sq_dist, inside} ->
        sq_dist = Vector.distance_squared(current, point)

        if prev_sq_dist + sq_dist + 2.0 * :math.sqrt(prev_sq_dist * sq_dist) -
             Vector.distance_squared(current, prev) < epsilon do
          allow = Keyword.get(opts, :allow_border, true)
          {:halt, {prev, prev_sq_dist, allow}}
        else
          {x, y} = point
          {px, _py} = prev

          {left, right} =
            if x > px do
              {prev, current}
            else
              {current, prev}
            end

          {lx, ly} = left
          {rx, ry} = right

          inside =
            if lx < x and x <= rx and (y - ly) * (rx - lx) < (ry - ly) * (x - lx) do
              not inside
            else
              inside
            end

          {:cont, {current, sq_dist, inside}}
        end
      end)

    is_inside
  end

  @doc """
  The opposite of `is_inside?/3`, provided for code readability.

  See `is_inside?/3` for behaviour and imagine the opposite.
  """
  def is_outside?(polygon, point, opts \\ [])

  def is_outside?(polygon, _point, _opts) when length(polygon) < 3 do
    false
  end

  def is_outside?(polygon, point, opts) do
    not is_inside?(polygon, point, opts)
  end

  @doc """
  Find the edge of a polygon nearest a given point.

  Given a `point` that's inside or outside a given `polygon`, this checks each
  segment of the polygon, and returns the nearest one.

  If multiple lines are "nearest", the first in the polygon is picked.

  ## Params

  * `polygon` (`t:polygon/0`) the polygion to find the nearest edge on.
  * `point` (`t:vector/0`) the point to find the nearest edge to.

  ## Returns

  A `t:line/0` that is a segment of `polygon` that is closest to `point`.

  ## Examples
      # A square around 0,0
      iex> square = [{-1, -1}, {1, -1}, {1, 1}, {-1, 1}]
      [{-1, -1}, {1, -1}, {1, 1}, {-1, 1}]
      iex> Polygon.nearest_edge(square, {0, 0})
      {{-1, -1}, {1, -1}}
      iex> Polygon.nearest_edge(square, {0.9, 0})
      {{1, -1}, {1, 1}}
      iex> Polygon.nearest_edge(square, {1.1, 0})
      {{1, -1}, {1, 1}}
  """
  @spec nearest_edge(polygon(), vector()) :: line()
  def nearest_edge(polygon, point) do
    # Get the closest segment of the polygon
    polygon
    |> Enum.chunk_every(2, 1, Enum.slice(polygon, 0, 2))
    |> Enum.map(fn [a, b] -> {a, b} end)
    |> Enum.min_by(&Geo.distance_to_segment(&1, point))
  end

  @doc """
  Find the point on the edge of a polygon nearest a given point.

  Given a `point` that's inside or outside a given `polygon`, this uses
  `nearest_edge/2` to find the closest edge and then computes the point on the
  edge nearest the given `point`.

  ## Params

  * `polygon` (`t:polygon/0`) the polygion to find the nearest point on.
  * `point` (`t:vector/0`) the point to find the nearest point to.

  ## Returns

  A `t:vector/0` that is a point on `polygon` that is closest to `point`.

  ## Examples
      # A square around 0,0
      iex> square = [{-1, -1}, {1, -1}, {1, 1}, {-1, 1}]
      [{-1, -1}, {1, -1}, {1, 1}, {-1, 1}]
      iex> Polygon.nearest_point_on_edge(square, {0, 0})
      {0.0, -1.0}
      iex> Polygon.nearest_point_on_edge(square, {0.9, 0})
      {1.0, 0.0}
      iex> Polygon.nearest_point_on_edge(square, {1.1, 0})
      {1.0, 0.0}
  """
  @spec nearest_point_on_edge(polygon(), vector()) :: vector()
  def nearest_point_on_edge(polygon, point) do
    # Get the closest segment of the polygon
    {{x1, y1}, {x2, y2}} = nearest_edge(polygon, point)

    {x, y} = point

    u =
      ((x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)) /
        ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1))

    cond do
      u < 0 -> {x1, y1}
      u > 1 -> {x2, y2}
      true -> {x1 + u * (x2 - x1), y1 + u * (y2 - y1)}
    end
  end

  @doc """
  Check if the polygon is clockwise within screen coordinates.

  This is provided as a utility to check polygons eg. if loading them from data
  files. The library internally _does not_ use this to validate polygons to
  avoid a runtime penalty.

  ## Params

  * `polygon` (`t:polygon/0`) the polygon to check to check.

  ## Returrns

  `true` if the points in the polygon are defined in a clockwise orientation.

  ## Examples
      iex> Polygon.is_clockwise?([{0, 0}, {2, 0}, {2, 1}, {1, 0.5}, {0, 1}])
      true
      iex> Polygon.is_clockwise?([{0, 0}, {0, 1}, {1, 0.5}, {2, 1}, {2, 0}])
      false

  """
  @spec is_clockwise?(polygon()) :: boolean()
  def is_clockwise?(polygon) do
    a =
      polygon
      |> Enum.chunk_every(2, 1, Enum.slice(polygon, 0, 2))
      |> Enum.reduce(0, fn [{x1, y1}, {x2, y2}], acc -> acc + (x2 - x1) * (y2 + y1) end)

    a < 0
  end
end