-- Copyright (C) 2010 Tyson Brown
-- 
-- This file is part QuestHelper2, an AddOn for World of Warcraft.
-- 
-- QuestHelper2 is free software: you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation, either version 3 of the License, or
-- (at your option) any later version.
-- 
-- QuestHelper2 is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-- GNU General Public License for more details.
-- 
-- You should have received a copy of the GNU General Public License
-- along with QuestHelper2. If not, see <http://www.gnu.org/licenses/>.

if LibDebug then LibDebug() end
local shared = select(2, ...)

local functions = {}

-- ConvexPoly is a class for creating convex polygons around an arbitrary collection of points.
-- The constructed polygons wind counter-clockwise.

shared.meta.ConvexPoly = {
  __index = functions,
  name = "ConvexPoly"
}

function shared.createConvexPoly()
  return setmetatable({}, shared.meta.ConvexPoly)
end

-- Returns true if the polygon has at least three vertices.
function functions:valid()
  return #self >= 6
end

-- Returns the number of vertices the polygon has.
function functions:vertices()
  return #self/2
end

-- Returns the x,y coordinate of vertex number i.
-- Supports wrap-around if i isn't a valid vertex.
-- Returns nil,nil if the polygon has no vertices
function functions:vertex(i)
  local len = #self/2
  if len == 0 then
    return nil, nil
  else
    i = ((i-1)%len+1)*2
    return self[i-1], self[i]
  end
end

local min, max = math.min, math.max
function functions:boundingBox()
  local vertices = self:vertices()
  local x1, y1 = self:vertex(1)
  local x2, y2 = x1, y1
  for i=2,vertices do
    local x, y =self:vertex(i)
    x1, y1, x2, y2 = min(x1,x), min(y1,y), max(x2,x), max(y2,y)
  end
  
  return x1, y1, x2, y2
end

function functions:area()
  local area = 0
  
  local x1, y1 = self:vertex(0)
  for i=1,self:vertices() do
    local x2, y2 = self:vertex(i)
    area = area + x2*y1 - x1*y2
    x1, y1 = x2, y2
  end
  
  return area*0.5
end

function functions:centroid()
  local weight_sum = 0
  
  local cx, cy, x1, y1 = 0, 0, self:vertex(0)
  
  for i=1,self:vertices() do
    local x2, y2 = self:vertex(i)
    local weight = (x2*y1-x1*y2)
    weight_sum, cx, cy = weight_sum + weight, cx + (x1+x2)*weight, cy + (y1+y2)*weight
    x1,y1 = x2,y2
  end
  
  local weight_inverse = 1/(3*weight_sum)
  
  return cx*weight_inverse, cy*weight_inverse
end

-- If you were to rotate the line so that [x1,y1] were at the bottom and [x2,y2] were at the top,
-- this returns whether or not the point x,y would be to the right of that line.
-- This test is to help determine if a point is inside a polygon; if any of the
-- tests return true, the point is outside the polygon.
local function lineTest(x1, y1, x2, y2, x, y)
  return (x-x1)*(y2-y1)+(x1-x2)*(y-y1) < 0
end

-- Returns the squared distance of the specified point from the
-- polygon, and the x,y coordinate of the nearest point,
-- or 0 and the passed point if the point is inside the polygon.
-- Returns nil if the polygon has no points.
function functions:distance(x, y)
  local vertices = self:vertices()
  
  if vertices == 0 then
    return nil
  end
  
  if vertices == 1 then
    local dx, dy = x-self[1], y-self[2]
    return dx*dx+dy*dy, self[1], self[2]
  end
  
  local d2,nx,ny
  
  local x1, y1 = self:vertex(0)
  for i=1,vertices do
    local x2, y2 = self:vertex(i)
    
    if lineTest(x1, y1, x2, y2, x, y) then
      local p = ((y-y1)*(y2-y1)+(x-x1)*(x2-x1))/((y2-y1)^2+(x2-x1)^2)
      
      if p <= 0 then
        -- The intersection point is before the first vertex, so clamp to the first vertex.
        local dx, dy = x1-x, y1-y
        local d = dx*dx+dy*dy
        if not d2 or d < d2 then
          d2,nx,ny = d,x1,y1
        end
      elseif p >= 1 then
        -- The intersection point is after the last vertex, so clamp to the last vertex.
        local dx, dy = x2-x, y2-y
        local d = dx*dx+dy*dy
        if not d2 or d < d2 then
          d2,nx,ny = d,x2,y2
        end
      else
        -- The intersection point is between the two verticies, interpolate.
        local _x, _y = x1+p*(x2-x1), y1+p*(y2-y1)
        local dx, dy = _x-x, _y-y
        local d = dx*dx+dy*dy
        if not d2 or d < d2 then
          d2,nx,ny = d,_x,_y
        end
      end
    end
    
    x1,y1 = x2,y2
  end
  
  if d2 then
    return d2,nx,ny
  else
    return 0,x,y
  end
end

-- Returns true if a point is inside the polygon.
function functions:isInside(x, y)
  if self:valid() then
    local x1, y1 = self:vertex(0)
    
    for i=1,self:vertices() do
      local x2, y2 = self:vertex(i)
      
      if lineTest(x1,y1,x2,y2,x,y) then
        return false
      end
      
      x1,y1 = x2,y2
    end
    
    return true
  else
    return false
  end
end

-- Adds a point to the polygon, maybe.
-- If the point is inside the polygon, this function returns false
-- and does nothing, otherwise the perimeter of the polygon is extended to include
-- this new point and returns true.
function functions:addVertex(x, y)
  local vertices = self:vertices()
  
  -- Check to see if we have a similar vertex, if we do, don't add a new one.
  -- This is required because if we end up with an edge that has zero length,
  -- everything goes to hell.
  for i = 1,vertices do
    local x1, y1 = self:vertex(i)
    local dx, dy = x-x1, y-y1
    local d2 = dx*dx + dy*dy
    
    -- It appears we already have this vertex.
    if d2 < 0.0000001 then
      return false
    end
  end
  
  -- If the polygon has 0 or 1 vertices, then
  -- we can go ahead and add the new vertex without any checks.
  if vertices < 2 then
    self[vertices*2+1], self[vertices*2+2] = x, y
    return true
  end
  
  -- If the polygon has 2 vertices, then
  -- we need to be careful about where we add
  -- the new vertex, to make sure the vertices
  -- are in a counter clockwise order.
  if vertices == 2 then
    if lineTest(self[1], self[2], self[3], self[4], x, y) then
      self[3], self[4], self[5], self[6] = x, y, self[3], self[4]
    else
      self[5], self[6] = x, y
    end
    
    return true
  end
  
  local x1, y1 = self:vertex(0)
  
  for n=1,self:vertices() do
    local x2, y2 = self:vertex(n)
    
    if not lineTest(x1,y1,x2,y2,x,y) then
      x1,y1 = x2,y2
      
      for i=n+1,n+vertices+1 do
        x2, y2 = self:vertex(i)
        
        if lineTest(x1,y1,x2,y2,x,y) then
          x1,y1 = x2,y2
          
          for j=i+1,i+vertices+1 do
            x2, y2 = self:vertex(j)
            
            if not lineTest(x1,y1,x2,y2,x,y) then
              if j-2>=i then
                local n = (j-i-2)*2
                i = 1+(i-1)%vertices
                self[i*2-1] = x
                self[i*2]   = y
                
                for j=1,n do
                  if self[i*2+1] then
                    table.remove(self, i*2+1)
                  else
                    table.remove(self, 1)
                  end
                end
                
              else
                i = 1+(i-1)%vertices
                table.insert(self, i*2-1, y)
                table.insert(self, i*2-1, x)
              end
              
              return true
            end
            
            x1,y1 = x2,y2
          end
          
          assert(false)
        end
        
        x1,y1 = x2,y2
      end
      
      return false
    end
    
    x1,y1 = x2,y2
  end
  
  return false
end
