Squishfied version of https://github.com/vrld/HardonCollider

hc.lua

package.preload['hc.class'] = (function (...)
--[[
Copyright (c) 2010-2011 Matthias Richter

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

Except as contained in this notice, the name(s) of the above copyright holders
shall not be used in advertising or otherwise to promote the sale, use or
other dealings in this Software without prior written authorization.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
]]--

local function __NULL__() end

-- class "inheritance" by copying functions
local function inherit(class, interface, ...)
  if not interface then return end
	assert(type(interface) == "table", "Can only inherit from other classes.")

	-- __index and construct are not overwritten as for them class[name] is defined
	for name, func in pairs(interface) do
		if not class[name] then
			class[name] = func
		end
	end
	for super in pairs(interface.__is_a or {}) do
		class.__is_a[super] = true
	end

	return inherit(class, ...)
end

-- class builder
local function new(args)
	local super = {}
	local name = '<unnamed class>'
	local constructor = args or __NULL__
	if type(args) == "table" then
		-- nasty hack to check if args.inherits is a table of classes or a class or nil
		super = (args.inherits or {}).__is_a and {args.inherits} or args.inherits or {}
		name = args.name or name
		constructor = args[1] or __NULL__
	end
	assert(type(constructor) == "function", 'constructor has to be nil or a function')

	-- build class
	local class = {}
	class.__index = class
	class.__tostring = function() return ("<instance of %s>"):format(tostring(class)) end
	class.construct = constructor or __NULL__
	class.inherit = inherit
	class.__is_a = {[class] = true}
	class.is_a = function(self, other) return not not self.__is_a[other] end

	-- inherit superclasses (see above)
	inherit(class, unpack(super))

	-- syntactic sugar
	local meta = {
		__call = function(self, ...)
			local obj = {}
			setmetatable(obj, self)
			self.construct(obj, ...)
			return obj
		end,
		__tostring = function() return name end
	}
	return setmetatable(class, meta)
end

-- interface for cross class-system compatibility (see https://github.com/bartbes/Class-Commons).
if common_class ~= false and not common then
	common = {}
	function common.class(name, prototype, parent)
		local init = prototype.init or (parent or {}).init
		return new{name = name, inherits = {prototype, parent}, init}
	end
	function common.instance(class, ...)
		return class(...)
	end
end

-- the module
return setmetatable({new = new, inherit = inherit},
	{__call = function(_,...) return new(...) end})
 end)
package.preload['hc.vector-light'] = (function (...)
--[[
Copyright (c) 2012 Matthias Richter

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

Except as contained in this notice, the name(s) of the above copyright holders
shall not be used in advertising or otherwise to promote the sale, use or
other dealings in this Software without prior written authorization.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
]]--

local sqrt, cos, sin = math.sqrt, math.cos, math.sin

local function str(x,y)
	return "("..tonumber(x)..","..tonumber(y)..")"
end

local function mul(s, x,y)
	return s*x, s*y
end

local function div(s, x,y)
	return x/s, y/s
end

local function add(x1,y1, x2,y2)
	return x1+x2, y1+y2
end

local function sub(x1,y1, x2,y2)
	return x1-x2, y1-y2
end

local function permul(x1,y1, x2,y2)
	return x1*x2, y1*y2
end

local function dot(x1,y1, x2,y2)
	return x1*x2 + y1*y2
end

local function det(x1,y1, x2,y2)
	return x1*y2 - y1*x2
end

local function eq(x1,y1, x2,y2)
	return x1 == x2 and y1 == y2
end

local function lt(x1,y1, x2,y2)
	return x1 < x2 or (x1 == x2 and y1 < y2)
end

local function le(x1,y1, x2,y2)
	return x1 <= x2 and y1 <= y2
end

local function len2(x,y)
	return x*x + y*y
end

local function len(x,y)
	return sqrt(x*x + y*y)
end

local function dist(x1,y1, x2,y2)
	return len(x1-x2, y1-y2)
end

local function normalize(x,y)
	local l = len(x,y)
	return x/l, y/l
end

local function rotate(phi, x,y)
	local c, s = cos(phi), sin(phi)
	return c*x - s*y, s*x + c*y
end

local function perpendicular(x,y)
	return -y, x
end

local function project(x,y, u,v)
	local s = (x*u + y*v) / (u*u + v*v)
	return s*u, s*v
end

local function mirror(x,y, u,v)
	local s = 2 * (x*u + y*v) / (u*u + v*v)
	return s*u - x, s*v - y
end


-- the module
return {
	str = str,

	-- arithmetic
	mul    = mul,
	div    = div,
	add    = add,
	sub    = sub,
	permul = permul,
	dot    = dot,
	det    = det,
	cross  = det,

	-- relation
	eq = eq,
	lt = lt,
	le = le,

	-- misc operations
	len2          = len2,
	len           = len,
	dist          = dist,
	normalize     = normalize,
	rotate        = rotate,
	perpendicular = perpendicular,
	project       = project,
	mirror        = mirror,
}
 end)
package.preload['hc.gjk'] = (function (...)
--[[
Copyright (c) 2012 Matthias Richter

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

Except as contained in this notice, the name(s) of the above copyright holders
shall not be used in advertising or otherwise to promote the sale, use or
other dealings in this Software without prior written authorization.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
]]--

local _PACKAGE = (...):match("^(.+)%.[^%.]+")
local vector  = require(_PACKAGE .. '.vector-light')

local function support(shape_a, shape_b, dx, dy)
	local x,y = shape_a:support(dx,dy)
	return vector.sub(x,y, shape_b:support(-dx, -dy))
end

-- returns closest edge to the origin
local function closest_edge(simplex)
	local e = {dist = math.huge}

	local i = #simplex-1
	for k = 1,#simplex-1,2 do
		local ax,ay = simplex[i], simplex[i+1]
		local bx,by = simplex[k], simplex[k+1]
		i = k

		local ex,ey = vector.perpendicular(bx-ax, by-ay)
		local nx,ny = vector.normalize(ex,ey)
		local d = vector.dot(ax,ay, nx,ny)

		if d < e.dist then
			e.dist = d
			e.nx, e.ny = nx, ny
			e.i = k
		end
	end

	return e
end

local function EPA(shape_a, shape_b, simplex)
	-- make sure simplex is oriented counter clockwise
	local cx,cy, bx,by, ax,ay = unpack(simplex)
	if vector.dot(ax-bx,ay-by, cx-bx,cy-by) < 0 then
		simplex[1],simplex[2] = ax,ay
		simplex[5],simplex[6] = cx,cy
	end

	-- the expanding polytype algorithm
	local last_diff_dist = math.huge
	while true do
		local e = closest_edge(simplex)
		local px,py = support(shape_a, shape_b, e.nx, e.ny)
		local d = vector.dot(px,py, e.nx, e.ny)

		local diff_dist = d - e.dist 
		if diff_dist < 1e-6 or last_diff_dist - diff_dist < 1e-10 then
			return -d*e.nx, -d*e.ny
		end
		last_diff_dist = diff_dist

		-- simplex = {..., simplex[e.i-1], px, py, simplex[e.i]
		table.insert(simplex, e.i, py)
		table.insert(simplex, e.i, px)
	end
end

--   :      :     origin must be in plane between A and B
-- B o------o A   since A is the furthest point on the MD
--   :      :     in direction of the origin.
local function do_line(simplex)
	local bx,by, ax,ay = unpack(simplex)
	local abx,aby = bx-ax, by-ay

	local dx,dy = vector.perpendicular(abx,aby)
	if vector.dot(dx,dy, -ax,-ay) < 0 then
		dx,dy = -dx,-dy
	end
	return simplex, dx,dy
end

-- B .'
--  o-._  1
--  |   `-. .'     The origin can only be in regions 1, 3 or 4:
--  |  4   o A 2   A lies on the edge of the MD and we came
--  |  _.-' '.     from left of BC.
--  o-'  3
-- C '.
local function do_triangle(simplex)
	local cx,cy, bx,by, ax,ay = unpack(simplex)
	local aox,aoy = -ax,-ay
	local abx,aby = bx-ax, by-ay
	local acx,acy = cx-ax, cy-ay

	-- test region 1
	local dx,dy = vector.perpendicular(abx,aby)
	if vector.dot(dx,dy, acx,acy) > 0 then
		dx,dy = -dx,-dy
	end
	if vector.dot(dx,dy, aox,aoy) > 0 then
		-- simplex = {bx,by, ax,ay}
		simplex[1], simplex[2] = bx,by
		simplex[3], simplex[4] = ax,ay
		simplex[5], simplex[6] = nil, nil
		return simplex, dx,dy
	end

	-- test region 3
	dx,dy = vector.perpendicular(acx,acy)
	if vector.dot(dx,dy, abx,aby) > 0 then
		dx,dy = -dx,-dy
	end
	if vector.dot(dx,dy, aox, aoy) > 0 then
		-- simplex = {cx,cy, ax,ay}
		simplex[3], simplex[4] = ax,ay
		simplex[5], simplex[6] = nil, nil
		return simplex, dx,dy
	end

	-- must be in region 4
	return simplex
end

local function GJK(shape_a, shape_b)
	local ax,ay = support(shape_a, shape_b, 1,0)
	if ax == 0 and ay == 0 then
		-- only true if shape_a and shape_b are touching in a vertex, e.g.
		--  .---                .---.
		--  | A |           .-. | B |   support(A, 1,0)  = x
		--  '---x---.  or  : A :x---'   support(B, -1,0) = x
		--      | B |       `-'         => support(A,B,1,0) = x - x = 0
		--      '---'
		-- Since CircleShape:support(dx,dy) normalizes dx,dy we have to opt
		-- out or the algorithm blows up. In accordance to the cases below
		-- choose to judge this situation as not colliding.
		return false
	end

	local simplex = {ax,ay}
	local n = 2
	local dx,dy = -ax,-ay

	-- first iteration: line case
	ax,ay = support(shape_a, shape_b, dx,dy)
	if vector.dot(ax,ay, dx,dy) <= 0 then
		return false
	end
	simplex[n+1], simplex[n+2] = ax,ay
	simplex, dx, dy = do_line(simplex, dx, dy)
	n = 4

	-- all other iterations must be the triangle case
	while true do
		ax,ay = support(shape_a, shape_b, dx,dy)

		if vector.dot(ax,ay, dx,dy) <= 0 then
			return false
		end

		simplex[n+1], simplex[n+2] = ax,ay
		simplex, dx, dy = do_triangle(simplex, dx,dy)
		n = #simplex

		if n == 6 then
			return true, EPA(shape_a, shape_b, simplex)
		end
	end
end

return GJK
 end)
package.preload['hc.polygon'] = (function (...)
--[[
Copyright (c) 2011 Matthias Richter

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

Except as contained in this notice, the name(s) of the above copyright holders
shall not be used in advertising or otherwise to promote the sale, use or
other dealings in this Software without prior written authorization.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
]]--

local _PACKAGE, common_local = (...):match("^(.+)%.[^%.]+"), common
if not (type(common) == 'table' and common.class and common.instance) then
	assert(common_class ~= false, 'No class commons specification available.')
	require(_PACKAGE .. '.class')
	common_local, common = common, common_local
end
local vector = require(_PACKAGE .. '.vector-light')

----------------------------
-- Private helper functions
--
-- create vertex list of coordinate pairs
local function toVertexList(vertices, x,y, ...)
	if not (x and y) then return vertices end -- no more arguments

	vertices[#vertices + 1] = {x = x, y = y}   -- set vertex
	return toVertexList(vertices, ...)         -- recurse
end

-- returns true if three vertices lie on a line
local function areCollinear(p, q, r, eps)
	return math.abs(vector.det(q.x-p.x, q.y-p.y,  r.x-p.x,r.y-p.y)) <= (eps or 1e-32)
end
-- remove vertices that lie on a line
local function removeCollinear(vertices)
	local ret = {}
	local i,k = #vertices - 1, #vertices
	for l=1,#vertices do
		if not areCollinear(vertices[i], vertices[k], vertices[l]) then
			ret[#ret+1] = vertices[k]
		end
		i,k = k,l
	end
	return ret
end

-- get index of rightmost vertex (for testing orientation)
local function getIndexOfleftmost(vertices)
	local idx = 1
	for i = 2,#vertices do
		if vertices[i].x < vertices[idx].x then
			idx = i
		end
	end
	return idx
end

-- returns true if three points make a counter clockwise turn
local function ccw(p, q, r)
	return vector.det(q.x-p.x, q.y-p.y,  r.x-p.x, r.y-p.y) >= 0
end

-- test wether a and b lie on the same side of the line c->d
local function onSameSide(a,b, c,d)
	local px, py = d.x-c.x, d.y-c.y
	local l = vector.det(px,py,  a.x-c.x, a.y-c.y)
	local m = vector.det(px,py,  b.x-c.x, b.y-c.y)
	return l*m >= 0
end

local function pointInTriangle(p, a,b,c)
	return onSameSide(p,a, b,c) and onSameSide(p,b, a,c) and onSameSide(p,c, a,b)
end

-- returns starting/ending indices of shared edge, i.e. if p and q share the
-- edge with indices p1,p2 of p and q1,q2 of q, the return value is p1,q2
local function getSharedEdge(p,q)
	local pindex = setmetatable({}, {__index = function(t,k)
		local s = {}
		t[k] = s
		return s
	end})

	-- record indices of vertices in p by their coordinates
	for i = 1,#p do
		pindex[p[i].x][p[i].y] = i
	end

	-- iterate over all edges in q. if both endpoints of that
	-- edge are in p as well, return the indices of the starting
	-- vertex
	local i,k = #q,1
	for k = 1,#q do
		local v,w = q[i], q[k]
		if pindex[v.x][v.y] and pindex[w.x][w.y] then
			return pindex[w.x][w.y], k
		end
		i = k
	end
end

-----------------
-- Polygon class
--
local Polygon = {}
function Polygon:init(...)
	local vertices = removeCollinear( toVertexList({}, ...) )
	assert(#vertices >= 3, "Need at least 3 non collinear points to build polygon (got "..#vertices..")")

	-- assert polygon is oriented counter clockwise
	local r = getIndexOfleftmost(vertices)
	local q = r > 1 and r - 1 or #vertices
	local s = r < #vertices and r + 1 or 1
	if not ccw(vertices[q], vertices[r], vertices[s]) then -- reverse order if polygon is not ccw
		local tmp = {}
		for i=#vertices,1,-1 do
			tmp[#tmp + 1] = vertices[i]
		end
		vertices = tmp
	end
	self.vertices = vertices
	-- make vertices immutable
	setmetatable(self.vertices, {__newindex = function() error("Thou shall not change a polygon's vertices!") end})

	-- compute polygon area and centroid
	local p,q = vertices[#vertices], vertices[1]
	local det = vector.det(p.x,p.y, q.x,q.y) -- also used below
	self.area = det
	for i = 2,#vertices do
		p,q = q,vertices[i]
		self.area = self.area + vector.det(p.x,p.y, q.x,q.y)
	end
	self.area = self.area / 2

	p,q = vertices[#vertices], vertices[1]
	self.centroid = {x = (p.x+q.x)*det, y = (p.y+q.y)*det}
	for i = 2,#vertices do
		p,q = q,vertices[i]
		det = vector.det(p.x,p.y, q.x,q.y)
		self.centroid.x = self.centroid.x + (p.x+q.x) * det
		self.centroid.y = self.centroid.y + (p.y+q.y) * det
	end
	self.centroid.x = self.centroid.x / (6 * self.area)
	self.centroid.y = self.centroid.y / (6 * self.area)

	-- get outcircle
	self._radius = 0
	for i = 1,#vertices do
		self._radius = math.max(self._radius,
			vector.dist(vertices[i].x,vertices[i].y, self.centroid.x,self.centroid.y))
	end
end
local newPolygon


-- return vertices as x1,y1,x2,y2, ..., xn,yn
function Polygon:unpack()
	local v = {}
	for i = 1,#self.vertices do
		v[2*i-1] = self.vertices[i].x
		v[2*i]   = self.vertices[i].y
	end
	return unpack(v)
end

-- deep copy of the polygon
function Polygon:clone()
	return Polygon( self:unpack() )
end

-- get bounding box
function Polygon:bbox()
	local ulx,uly = self.vertices[1].x, self.vertices[1].y
	local lrx,lry = ulx,uly
	for i=2,#self.vertices do
		local p = self.vertices[i]
		if ulx > p.x then ulx = p.x end
		if uly > p.y then uly = p.y end

		if lrx < p.x then lrx = p.x end
		if lry < p.y then lry = p.y end
	end

	return ulx,uly, lrx,lry
end

-- a polygon is convex if all edges are oriented ccw
function Polygon:isConvex()
	local function isConvex()
		local v = self.vertices
		if #v == 3 then return true end

		if not ccw(v[#v], v[1], v[2]) then
			return false
		end
		for i = 2,#v-1 do
			if not ccw(v[i-1], v[i], v[i+1]) then
				return false
			end
		end
		if not ccw(v[#v-1], v[#v], v[1]) then
			return false
		end
		return true
	end

	-- replace function so that this will only be computed once
	local status = isConvex()
	self.isConvex = function() return status end
	return status
end

function Polygon:move(dx, dy)
	if not dy then
		dx, dy = dx:unpack()
	end
	for i,v in ipairs(self.vertices) do
		v.x = v.x + dx
		v.y = v.y + dy
	end
	self.centroid.x = self.centroid.x + dx
	self.centroid.y = self.centroid.y + dy
end

function Polygon:rotate(angle, cx, cy)
	if not (cx and cy) then
		cx,cy = self.centroid.x, self.centroid.y
	end
	for i,v in ipairs(self.vertices) do
		-- v = (v - center):rotate(angle) + center
		v.x,v.y = vector.add(cx,cy, vector.rotate(angle, v.x-cx, v.y-cy))
	end
	local v = self.centroid
	v.x,v.y = vector.add(cx,cy, vector.rotate(angle, v.x-cx, v.y-cy))
end

function Polygon:scale(s, cx,cy)
	if not (cx and cy) then
		cx,cy = self.centroid.x, self.centroid.y
	end
	for i,v in ipairs(self.vertices) do
		-- v = (v - center) * s + center
		v.x,v.y = vector.add(cx,cy, vector.mul(s, v.x-cx, v.y-cy))
	end
	self._radius = self._radius * s
end

-- triangulation by the method of kong
function Polygon:triangulate()
	if #self.vertices == 3 then return {self:clone()} end
	local triangles = {} -- list of triangles to be returned
	local concave = {}   -- list of concave edges
	local adj = {}       -- vertex adjacencies
	local vertices = self.vertices

	-- retrieve adjacencies as the rest will be easier to implement
	for i,p in ipairs(vertices) do
		local l = (i == 1) and vertices[#vertices] or vertices[i-1]
		local r = (i == #vertices) and vertices[1] or vertices[i+1]
		adj[p] = {p = p, l = l, r = r} -- point, left and right neighbor
		-- test if vertex is a concave edge
		if not ccw(l,p,r) then concave[p] = p end
	end

	-- and ear is an edge of the polygon that contains no other
	-- vertex of the polygon
	local function isEar(p1,p2,p3)
		if not ccw(p1,p2,p3) then return false end
		for q,_ in pairs(concave) do
			if q ~= p1 and q ~= p2 and q ~= p3 and pointInTriangle(q, p1,p2,p3) then
				return false
			end
		end
		return true
	end

	-- main loop
	local nPoints, skipped = #vertices, 0
	local p = adj[ vertices[2] ]
	while nPoints > 3 do
		if not concave[p.p] and isEar(p.l, p.p, p.r) then
			-- polygon may be a 'collinear triangle', i.e.
			-- all three points are on a line. In that case
			-- the polygon constructor throws an error.
			if not areCollinear(p.l, p.p, p.r) then
				triangles[#triangles+1] = newPolygon(p.l.x,p.l.y, p.p.x,p.p.y, p.r.x,p.r.y)
				skipped = 0
			end

			if concave[p.l] and ccw(adj[p.l].l, p.l, p.r) then
				concave[p.l] = nil
			end
			if concave[p.r] and ccw(p.l, p.r, adj[p.r].r) then
				concave[p.r] = nil
			end
			-- remove point from list
			adj[p.p] = nil
			adj[p.l].r = p.r
			adj[p.r].l = p.l
			nPoints = nPoints - 1
			skipped = 0
			p = adj[p.l]
		else
			p = adj[p.r]
			skipped = skipped + 1
			assert(skipped <= nPoints, "Cannot triangulate polygon (is the polygon intersecting itself?)")
		end
	end

	if not areCollinear(p.l, p.p, p.r) then
		triangles[#triangles+1] = newPolygon(p.l.x,p.l.y, p.p.x,p.p.y, p.r.x,p.r.y)
	end

	return triangles
end

-- return merged polygon if possible or nil otherwise
function Polygon:mergedWith(other)
	local p,q = getSharedEdge(self.vertices, other.vertices)
	assert(p and q, "Polygons do not share an edge")

	local ret = {}
	for i = 1,p-1 do
		ret[#ret+1] = self.vertices[i].x
		ret[#ret+1] = self.vertices[i].y
	end

	for i = 0,#other.vertices-2 do
		i = ((i-1 + q) % #other.vertices) + 1
		ret[#ret+1] = other.vertices[i].x
		ret[#ret+1] = other.vertices[i].y
	end

	for i = p+1,#self.vertices do
		ret[#ret+1] = self.vertices[i].x
		ret[#ret+1] = self.vertices[i].y
	end

	return newPolygon(unpack(ret))
end

-- split polygon into convex polygons.
-- note that this won't be the optimal split in most cases, as
-- finding the optimal split is a really hard problem.
-- the method is to first triangulate and then greedily merge
-- the triangles.
function Polygon:splitConvex()
	-- edge case: polygon is a triangle or already convex
	if #self.vertices <= 3 or self:isConvex() then return {self:clone()} end

	local convex = self:triangulate()
	local i = 1
	repeat
		local p = convex[i]
		local k = i + 1
		while k <= #convex do
			local success, merged = pcall(function() return p:mergedWith(convex[k]) end)
			if success and merged:isConvex() then
				convex[i] = merged
				p = convex[i]
				table.remove(convex, k)
			else
				k = k + 1
			end
		end
		i = i + 1
	until i >= #convex
	
	return convex
end

function Polygon:contains(x,y)
	-- test if an edge cuts the ray
	local function cut_ray(p,q)
		return ((p.y > y and q.y < y) or (p.y < y and q.y > y)) -- possible cut
			and (x - p.x < (y - p.y) * (q.x - p.x) / (q.y - p.y)) -- x < cut.x
	end

	-- test if the ray crosses boundary from interior to exterior.
	-- this is needed due to edge cases, when the ray passes through
	-- polygon corners
	local function cross_boundary(p,q)
		return (p.y == y and p.x > x and q.y < y)
			or (q.y == y and q.x > x and p.y < y)
	end

	local v = self.vertices
	local in_polygon = false
	local p,q = v[#v],v[#v]
	for i = 1, #v do
		p,q = q,v[i]
		if cut_ray(p,q) or cross_boundary(p,q) then
			in_polygon = not in_polygon
		end
	end
	return in_polygon
end

function Polygon:intersectsRay(x,y, dx,dy)
	--local p = vector(x,y)
	--local v = vector(dx,dy)
	local nx,ny = vector.perpendicular(dx,dy)
	local wx,xy,det

	local tmin = math.huge
	local q1,q2 = nil, self.vertices[#self.vertices]
	for i = 1, #self.vertices do
		q1,q2 = q2,self.vertices[i]
		wx,wy = q2.x - q1.x, q2.y - q1.y
		det = vector.det(dx,dy, wx,wy)

		if det ~= 0 then
			-- there is an intersection point. check if it lies on both
			-- the ray and the segment.
			local rx,ry = q2.x - x, q2.y - y
			local l = vector.det(rx,ry, wx,wy) / det
			local m = vector.det(dx,dy, rx,ry) / det
			if l >= 0 and m >= 0 and m <= 1 then
				-- we cannot jump out early here (i.e. when l > tmin) because
				-- the polygon might be concave
				tmin = math.min(tmin, l)
			end
		else
			-- lines parralel or incident. get distance of line to
			-- anchor point. if they are incident, check if an endpoint
			-- lies on the ray
			local dist = vector.dot(q1.x-x,q1.y-y, nx,ny)
			if dist == 0 then
				local l = vector.dot(dx,dy, q1.x-x,q1.y-y)
				local m = vector.dot(dx,dy, q2.x-x,q2.y-y)
				if l >= 0 and l >= m then
					tmin = math.min(tmin, l)
				elseif m >= 0 then
					tmin = math.min(tmin, m)
				end
			end
		end
	end
	return tmin ~= math.huge, tmin
end

Polygon = common_local.class('Polygon', Polygon)
newPolygon = function(...) return common_local.instance(Polygon, ...) end
return Polygon
 end)
package.preload['hc.shapes'] = (function (...)
--[[
Copyright (c) 2011 Matthias Richter

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

Except as contained in this notice, the name(s) of the above copyright holders
shall not be used in advertising or otherwise to promote the sale, use or
other dealings in this Software without prior written authorization.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
]]--

local math_min, math_sqrt, math_huge = math.min, math.sqrt, math.huge

local _PACKAGE, common_local = (...):match("^(.+)%.[^%.]+"), common
if not (type(common) == 'table' and common.class and common.instance) then
	assert(common_class ~= false, 'No class commons specification available.')
	require(_PACKAGE .. '.class')
end
local vector  = require(_PACKAGE .. '.vector-light')
local Polygon = require(_PACKAGE .. '.polygon')
local GJK     = require(_PACKAGE .. '.gjk') -- actual collision detection

-- reset global table `common' (required by class commons)
if common_local ~= common then
	common_local, common = common, common_local
end

--
-- base class
--
local Shape = {}
function Shape:init(t)
	self._type = t
	self._rotation = 0
end

function Shape:moveTo(x,y)
	local cx,cy = self:center()
	self:move(x - cx, y - cy)
end

function Shape:rotation()
	return self._rotation
end

function Shape:rotate(angle)
	self._rotation = self._rotation + angle
end

function Shape:setRotation(angle, x,y)
	return self:rotate(angle - self._rotation, x,y)
end

--
-- class definitions
--
local ConvexPolygonShape = {}
function ConvexPolygonShape:init(polygon)
	Shape.init(self, 'polygon')
	assert(polygon:isConvex(), "Polygon is not convex.")
	self._polygon = polygon
end

local ConcavePolygonShape = {}
function ConcavePolygonShape:init(poly)
	Shape.init(self, 'compound')
	self._polygon = poly
	self._shapes = poly:splitConvex()
	for i,s in ipairs(self._shapes) do
		self._shapes[i] = common_local.instance(ConvexPolygonShape, s)
	end
end

local CircleShape = {}
function CircleShape:init(cx,cy, radius)
	Shape.init(self, 'circle')
	self._center = {x = cx, y = cy}
	self._radius = radius
end

local PointShape = {}
function PointShape:init(x,y)
	Shape.init(self, 'point')
	self._pos = {x = x, y = y}
end

--
-- collision functions
--
function ConvexPolygonShape:support(dx,dy)
	local v = self._polygon.vertices
	local max, vmax = -math_huge
	for i = 1,#v do
		local d = vector.dot(v[i].x,v[i].y, dx,dy)
		if d > max then
			max, vmax = d, v[i]
		end
	end
	return vmax.x, vmax.y
end

function CircleShape:support(dx,dy)
	return vector.add(self._center.x, self._center.y,
		vector.mul(self._radius, vector.normalize(dx,dy)))
end

-- collision dispatching:
-- let circle shape or compund shape handle the collision
function ConvexPolygonShape:collidesWith(other)
	if self == other then return false end
	if other._type ~= 'polygon' then
		local collide, sx,sy = other:collidesWith(self)
		return collide, sx and -sx, sy and -sy
	end

	-- else: type is POLYGON
	return GJK(self, other)
end

function ConcavePolygonShape:collidesWith(other)
	if self == other then return false end
	if other._type == 'point' then
		return other:collidesWith(self)
	end

	-- TODO: better way of doing this. report all the separations?
	local collide,dx,dy = false,0,0
	for _,s in ipairs(self._shapes) do
		local status, sx,sy = s:collidesWith(other)
		collide = collide or status
		if status then
			if math.abs(dx) < math.abs(sx) then
				dx = sx
			end
			if math.abs(dy) < math.abs(sy) then
				dy = sy
			end
		end
	end
	return collide, dx, dy
end

function CircleShape:collidesWith(other)
	if self == other then return false end
	if other._type == 'circle' then
		local px,py = self._center.x-other._center.x, self._center.y-other._center.y
		local d = vector.len2(px,py)
		local radii = self._radius + other._radius
		if d < radii*radii then
			-- if circles overlap, push it out upwards
			if d == 0 then return true, 0,radii end
			-- otherwise push out in best direction
			return true, vector.mul(radii - math_sqrt(d), vector.normalize(px,py))
		end
		return false
	elseif other._type == 'polygon' then
		return GJK(self, other)
	end

	-- else: let the other shape decide
	local collide, sx,sy = other:collidesWith(self)
	return collide, sx and -sx, sy and -sy
end

function PointShape:collidesWith(other)
	if self == other then return false end
	if other._type == 'point' then
		return (self._pos == other._pos), 0,0
	end
	return other:contains(self._pos.x, self._pos.y), 0,0
end

--
-- point location/ray intersection
--
function ConvexPolygonShape:contains(x,y)
	return self._polygon:contains(x,y)
end

function ConcavePolygonShape:contains(x,y)
	return self._polygon:contains(x,y)
end

function CircleShape:contains(x,y)
	return vector.len2(x-self._center.x, y-self._center.y) < self._radius * self._radius
end

function PointShape:contains(x,y)
	return x == self._pos.x and y == self._pos.y
end


function ConcavePolygonShape:intersectsRay(x,y, dx,dy)
	return self._polygon:intersectsRay(x,y, dx,dy)
end

function ConvexPolygonShape:intersectsRay(x,y, dx,dy)
	return self._polygon:intersectsRay(x,y, dx,dy)
end

-- circle intersection if distance of ray/center is smaller
-- than radius.
-- with r(s) = p + d*s = (x,y) + (dx,dy) * s defining the ray and
-- (x - cx)^2 + (y - cy)^2 = r^2, this problem is eqivalent to
-- solving [with c = (cx,cy)]:
--
--     d*d s^2 + 2 d*(p-c) s + (p-c)*(p-c)-r^2 = 0
function CircleShape:intersectsRay(x,y, dx,dy)
	local pcx,pcy = x-self._center.x, y-self._center.y

	local a = vector.len2(dx,dy)
	local b = 2 * vector.dot(dx,dy, pcx,pcy)
	local c = vector.len2(pcx,pcy) - self._radius * self._radius
	local discr = b*b - 4*a*c
	if discr < 0 then return false end

	discr = math_sqrt(discr)
	local s1,s2 = discr-b, -discr-b
	if s1 < 0 then -- first solution is off the ray
		return s2 >= 0, s2/(2*a)
	elseif s2 < 0 then -- second solution is off the ray
		return s1 >= 0, s1/(2*a)
	end
	-- both solutions on the ray
	return true, math_min(s1,s2)/(2*a)
end

-- point shape intersects ray if it lies on the ray
function PointShape:intersectsRay(x,y,dx,dy)
	local px,py = self._pos.x-x, self._pos.y-y
	local t = vector.dot(px,py, dx,dy) / vector.len2(dx,dy)
	return t >= 0, t
end

--
-- auxiliary
--
function ConvexPolygonShape:center()
	return self._polygon.centroid.x, self._polygon.centroid.y
end

function ConcavePolygonShape:center()
	return self._polygon.centroid.x, self._polygon.centroid.y
end

function CircleShape:center()
	return self._center.x, self._center.y
end

function PointShape:center()
	return self._pos.x, self._pos.y
end

function ConvexPolygonShape:outcircle()
	local cx,cy = self:center()
	return cx,cy, self._polygon._radius
end

function ConcavePolygonShape:outcircle()
	local cx,cy = self:center()
	return cx,cy, self._polygon._radius
end

function CircleShape:outcircle()
	local cx,cy = self:center()
	return cx,cy, self._radius
end

function PointShape:outcircle()
	return self._pos.x, self._pos.y, 0
end

function ConvexPolygonShape:bbox()
	return self._polygon:bbox()
end

function ConcavePolygonShape:bbox()
	return self._polygon:bbox()
end

function CircleShape:bbox()
	local cx,cy = self:center()
	local r = self._radius
	return cx-r,cy-r, cx+r,cy+r
end

function PointShape:bbox()
	local x,y = self:center()
	return x,y,x,y
end


function ConvexPolygonShape:move(x,y)
	self._polygon:move(x,y)
end

function ConcavePolygonShape:move(x,y)
	self._polygon:move(x,y)
	for _,p in ipairs(self._shapes) do
		p:move(x,y)
	end
end

function CircleShape:move(x,y)
	self._center.x = self._center.x + x
	self._center.y = self._center.y + y
end

function PointShape:move(x,y)
	self._pos.x = self._pos.x + x
	self._pos.y = self._pos.y + y
end


function ConcavePolygonShape:rotate(angle,cx,cy)
	Shape.rotate(self, angle)
	if not (cx and cy) then
		cx,cy = self:center()
	end
	self._polygon:rotate(angle,cx,cy)
	for _,p in ipairs(self._shapes) do
		p:rotate(angle, cx,cy)
	end
end

function ConvexPolygonShape:rotate(angle, cx,cy)
	Shape.rotate(self, angle)
	self._polygon:rotate(angle, cx, cy)
end

function CircleShape:rotate(angle, cx,cy)
	Shape.rotate(self, angle)
	if not (cx and cy) then return end
	self._center.x,self._center.y = vector.add(cx,cy, vector.rotate(angle, self._center.x-cx, self._center.y-cy))
end

function PointShape:rotate(angle, cx,cy)
	Shape.rotate(self, angle)
	if not (cx and cy) then return end
	self._pos.x,self._pos.y = vector.add(cx,cy, vector.rotate(angle, self._pos.x-cx, self._pos.y-cy))
end


function ConcavePolygonShape:scale(s)
	assert(type(s) == "number" and s > 0, "Invalid argument. Scale must be greater than 0")
	local cx,cy = self:center()
	self._polygon:scale(s, cx,cy)
	for _, p in ipairs(self._shapes) do
		local dx,dy = vector.sub(cx,cy, p:center())
		p:scale(s)
		p:moveTo(cx-dx*s, cy-dy*s)
	end
end

function ConvexPolygonShape:scale(s)
	assert(type(s) == "number" and s > 0, "Invalid argument. Scale must be greater than 0")
	self._polygon:scale(s, self:center())
end

function CircleShape:scale(s)
	assert(type(s) == "number" and s > 0, "Invalid argument. Scale must be greater than 0")
	self._radius = self._radius * s
end

function PointShape:scale()
	-- nothing
end


function ConvexPolygonShape:draw(mode)
	local mode = mode or 'line'
	love.graphics.polygon(mode, self._polygon:unpack())
end

function ConcavePolygonShape:draw(mode, wireframe)
	local mode = mode or 'line'
	if mode == 'line' then
		love.graphics.polygon('line', self._polygon:unpack())
		if not wireframe then return end
	end
	for _,p in ipairs(self._shapes) do
		love.graphics.polygon(mode, p._polygon:unpack())
	end
end

function CircleShape:draw(mode, segments)
	love.graphics.circle(mode or 'line', self:outcircle())
end

function PointShape:draw()
	love.graphics.point(self:center())
end


Shape = common_local.class('Shape', Shape)
ConvexPolygonShape  = common_local.class('ConvexPolygonShape',  ConvexPolygonShape,  Shape)
ConcavePolygonShape = common_local.class('ConcavePolygonShape', ConcavePolygonShape, Shape)
CircleShape         = common_local.class('CircleShape',         CircleShape,         Shape)
PointShape          = common_local.class('PointShape',          PointShape,          Shape)

local function newPolygonShape(polygon, ...)
	-- create from coordinates if needed
	if type(polygon) == "number" then
		polygon = common_local.instance(Polygon, polygon, ...)
	else
		polygon = polygon:clone()
	end

	if polygon:isConvex() then
		return common_local.instance(ConvexPolygonShape, polygon)
	end

	return common_local.instance(ConcavePolygonShape, polygon)
end

local function newCircleShape(...)
	return common_local.instance(CircleShape, ...)
end

local function newPointShape(...)
	return common_local.instance(PointShape, ...)
end

return {
	ConcavePolygonShape = ConcavePolygonShape,
	ConvexPolygonShape  = ConvexPolygonShape,
	CircleShape         = CircleShape,
	PointShape          = PointShape,
	newPolygonShape     = newPolygonShape,
	newCircleShape      = newCircleShape,
	newPointShape       = newPointShape,
}

 end)
package.preload['hc.spatialhash'] = (function (...)
--[[
Copyright (c) 2011 Matthias Richter

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

Except as contained in this notice, the name(s) of the above copyright holders
shall not be used in advertising or otherwise to promote the sale, use or
other dealings in this Software without prior written authorization.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
]]--

local floor = math.floor
local min, max = math.min, math.max

local _PACKAGE, common_local = (...):match("^(.+)%.[^%.]+"), common
if not (type(common) == 'table' and common.class and common.instance) then
	assert(common_class ~= false, 'No class commons specification available.')
	require(_PACKAGE .. '.class')
	common_local, common = common, common_local
end

local Spatialhash = {}
function Spatialhash:init(cell_size)
	self.cell_size = cell_size or 100
	self.cells = {}
end

function Spatialhash:cellCoords(x,y)
	return floor(x / self.cell_size), floor(y / self.cell_size)
end

function Spatialhash:cell(i,k)
	local row = rawget(self.cells, i)
	if not row then
		row = {}
		rawset(self.cells, i, row)
	end

	local cell = rawget(row, k)
	if not cell then
		cell = setmetatable({}, {__mode = "kv"})
		rawset(row, k, cell)
	end

	return cell
end

function Spatialhash:cellAt(x,y)
	return self:cell(self:cellCoords(x,y))
end

function Spatialhash:inRange(x1,y1, x2,y2)
	local set = {}
	x1, y1 = self:cellCoords(x1, y1)
	x2, y2 = self:cellCoords(x2, y2)
	for i = x1,x2 do
		for k = y1,y2 do
			for obj in pairs(self:cell(i,k)) do
				rawset(set, obj, obj)
			end
		end
	end
	return set
end

function Spatialhash:rangeIter(...)
	return pairs(self:inRange(...))
end

function Spatialhash:insert(obj, x1, y1, x2, y2)
	x1, y1 = self:cellCoords(x1, y1)
	x2, y2 = self:cellCoords(x2, y2)
	for i = x1,x2 do
		for k = y1,y2 do
			rawset(self:cell(i,k), obj, obj)
		end
	end
end

function Spatialhash:remove(obj, x1, y1, x2,y2)
	-- no bbox given. => must check all cells
	if not (x1 and y1 and x2 and y2) then
		for _,row in pairs(self.cells) do
			for _,cell in pairs(row) do
				rawset(cell, obj, nil)
			end
		end
		return
	end

	-- else: remove only from bbox
	x1,y1 = self:cellCoords(x1,y1)
	x2,y2 = self:cellCoords(x2,y2)
	for i = x1,x2 do
		for k = y1,y2 do
			rawset(self:cell(i,k), obj, nil)
		end
	end
end

-- update an objects position
function Spatialhash:update(obj, old_x1,old_y1, old_x2,old_y2, new_x1,new_y1, new_x2,new_y2)
	old_x1, old_y1 = self:cellCoords(old_x1, old_y1)
	old_x2, old_y2 = self:cellCoords(old_x2, old_y2)

	new_x1, new_y1 = self:cellCoords(new_x1, new_y1)
	new_x2, new_y2 = self:cellCoords(new_x2, new_y2)

	if old_x1 == new_x1 and old_y1 == new_y1 and
	   old_x2 == new_x2 and old_y2 == new_y2 then
		return
	end

	for i = old_x1,old_x2 do
		for k = old_y1,old_y2 do
			rawset(self:cell(i,k), obj, nil)
		end
	end
	for i = new_x1,new_x2 do
		for k = new_y1,new_y2 do
			rawset(self:cell(i,k), obj, obj)
		end
	end
end

function Spatialhash:draw(how, show_empty, print_key)
	if show_empty == nil then show_empty = true end
	for k1,v in pairs(self.cells) do
		for k2,cell in pairs(v) do
			local is_empty = (next(cell) == nil)
			if show_empty or not is_empty then
				local x = k1 * self.cell_size
				local y = k2 * self.cell_size
				love.graphics.rectangle(how or 'line', x,y, self.cell_size, self.cell_size)

				if print_key then
					love.graphics.print(("%d:%d"):format(k1,k2), x+3,y+3)
				end
			end
		end
	end
end

return common_local.class('Spatialhash', Spatialhash)
 end)
--[[
Copyright (c) 2011 Matthias Richter

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

Except as contained in this notice, the name(s) of the above copyright holders
shall not be used in advertising or otherwise to promote the sale, use or
other dealings in this Software without prior written authorization.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
]]--

local _NAME, common_local = ..., common
if not (type(common) == 'table' and common.class and common.instance) then
	assert(common_class ~= false, 'No class commons specification available.')
	require(_NAME .. '.class')
end
local Shapes      = require(_NAME .. '.shapes')
local Spatialhash = require(_NAME .. '.spatialhash')

-- reset global table `common' (required by class commons)
if common_local ~= common then
	common_local, common = common, common_local
end

local newPolygonShape = Shapes.newPolygonShape
local newCircleShape  = Shapes.newCircleShape
local newPointShape   = Shapes.newPointShape

local function __NULL__() end

local HC = {}
function HC:init(cell_size, callback_collide, callback_stop)
	self._active_shapes  = {}
	self._passive_shapes = {}
	self._ghost_shapes   = {}
	self.groups          = {}
	self._colliding_only_last_frame = {}

	self.on_collide = callback_collide or __NULL__
	self.on_stop    = callback_stop    or __NULL__
	self._hash      = common_local.instance(Spatialhash, cell_size)
end

function HC:clear()
	self._active_shapes  = {}
	self._passive_shapes = {}
	self._ghost_shapes   = {}
	self.groups          = {}
	self._colliding_only_last_frame = {}
	self._hash           = common_local.instance(Spatialhash, self._hash.cell_size)
	return self
end

function HC:setCallbacks(collide, stop)
	if type(collide) == "table" and not (getmetatable(collide) or {}).__call then
		stop = collide.stop
		collide = collide.collide
	end

	if collide then
		assert(type(collide) == "function" or (getmetatable(collide) or {}).__call,
			"collision callback must be a function or callable table")
		self.on_collide = collide
	end

	if stop then
		assert(type(stop) == "function" or (getmetatable(stop) or {}).__call,
			"stop callback must be a function or callable table")
		self.on_stop = stop
	end

	return self
end

function HC:addShape(shape)
	assert(shape.bbox and shape.collidesWith,
		"Cannot add custom shape: Incompatible shape.")

	self._active_shapes[shape] = shape
	self._hash:insert(shape, shape:bbox())
	shape._groups = {}

	local hash = self._hash
	local move, rotate,scale = shape.move, shape.rotate, shape.scale
	for _, func in ipairs{'move', 'rotate', 'scale'} do
		local old_func = shape[func]
		shape[func] = function(self, ...)
			local x1,y1,x2,y2 = self:bbox()
			old_func(self, ...)
			local x3,y3,x4,y4 = self:bbox()
			hash:update(self, x1,y1, x2,y2, x3,y3, x4,y4)
		end
	end

	function shape:neighbors()
		local neighbors = hash:inRange(self:bbox())
		rawset(neighbors, self, nil)
		return neighbors
	end

	function shape:_removeFromHash()
		return hash:remove(shape, self:bbox())
	end

	function shape:inGroup(group)
		return self._groups[group]
	end

	return shape
end

function HC:activeShapes()
	return pairs(self._active_shapes)
end

function HC:shapesInRange(x1,y1, x2,y2)
	return self._hash:inRange(x1,y1, x2,y2)
end

function HC:addPolygon(...)
	return self:addShape(newPolygonShape(...))
end

function HC:addRectangle(x,y,w,h)
	return self:addPolygon(x,y, x+w,y, x+w,y+h, x,y+h)
end

function HC:addCircle(cx, cy, radius)
	return self:addShape(newCircleShape(cx,cy, radius))
end

function HC:addPoint(x,y)
	return self:addShape(newPointShape(x,y))
end

function HC:share_group(shape, other)
	for name,group in pairs(shape._groups) do
		if group[other] then return true end
	end
	return false
end

-- check for collisions
function HC:update(dt)
	-- cache for tested/colliding shapes
	local tested, colliding = {}, {}
	local function may_skip_test(shape, other)
		return (shape == other)
		    or (tested[other] and tested[other][shape])
		    or self._ghost_shapes[other]
		    or self:share_group(shape, other)
	end

	-- collect active shapes. necessary, because a callback might add shapes to
	-- _active_shapes, which will lead to undefined behavior (=random crashes) in
	-- next()
	local active = {}
	for shape in self:activeShapes() do
		active[shape] = shape
	end

	local only_last_frame = self._colliding_only_last_frame
	for shape in pairs(active) do
		tested[shape] = {}
		for other in self._hash:rangeIter(shape:bbox()) do
			if not self._active_shapes[shape] then
				-- break out of this loop is shape was removed in a callback
				break
			end

			if not may_skip_test(shape, other) then
				local collide, sx,sy = shape:collidesWith(other)
				if collide then
					if not colliding[shape] then colliding[shape] = {} end
					colliding[shape][other] = {sx, sy}

					-- flag shape colliding this frame and call collision callback
					if only_last_frame[shape] then
						only_last_frame[shape][other] = nil
					end
					self.on_collide(dt, shape, other, sx, sy)
				end
				tested[shape][other] = true
			end
		end
	end

	-- call stop callback on shapes that do not collide anymore
	for a,reg in pairs(only_last_frame) do
		for b, info in pairs(reg) do
			self.on_stop(dt, a, b, info[1], info[2])
		end
	end

	self._colliding_only_last_frame = colliding
end

-- get list of shapes at point (x,y)
function HC:shapesAt(x, y)
	local shapes = {}
	for s in pairs(self._hash:cellAt(x,y)) do
		if s:contains(x,y) then
			shapes[#shapes+1] = s
		end
	end
	return shapes
end

-- remove shape from internal tables and the hash
function HC:remove(shape, ...)
	if not shape then return end
	self._active_shapes[shape]  = nil
	self._passive_shapes[shape] = nil
	self._ghost_shapes[shape]   = nil
	for name, group in pairs(shape._groups) do
		group[shape] = nil
	end
	shape:_removeFromHash()

	return self:remove(...)
end

-- group support
function HC:addToGroup(group, shape, ...)
	if not shape then return end
	assert(self._active_shapes[shape] or self._passive_shapes[shape],
		"Shape is not registered with HC")
	if not self.groups[group] then self.groups[group] = {} end
	self.groups[group][shape] = true
	shape._groups[group]      = self.groups[group]
	return self:addToGroup(group, ...)
end

function HC:removeFromGroup(group, shape, ...)
	if not shape or not self.groups[group] then return end
	assert(self._active_shapes[shape] or self._passive_shapes[shape],
		"Shape is not registered with HC")
	self.groups[group][shape] = nil
	shape._groups[group]      = nil
	return self:removeFromGroup(group, ...)
end

function HC:setPassive(shape, ...)
	if not shape then return end
	if not self._ghost_shapes[shape] then
		assert(self._active_shapes[shape], "Shape is not active")
		self._active_shapes[shape] = nil
		self._passive_shapes[shape] = shape
	end
	return self:setPassive(...)
end

function HC:setActive(shape, ...)
	if not shape then return end
	if not self._ghost_shapes[shape] then
		assert(self._passive_shapes[shape], "Shape is not passive")
		self._active_shapes[shape]  = shape
		self._passive_shapes[shape] = nil
	end

	return self:setActive(...)
end

function HC:setGhost(shape, ...)
	if not shape then return end
	assert(self._active_shapes[shape] or self._passive_shapes[shape],
		"Shape is not registered with HC")

	self._active_shapes[shape] = nil
	-- dont remove from passive shapes, see below
	self._ghost_shapes[shape] = shape
	return self:setGhost(...)
end

function HC:setSolid(shape, ...)
	if not shape then return end
	assert(self._ghost_shapes[shape], "Shape not a ghost")

	-- re-register shape. passive shapes were not unregistered above, so if a shape
	-- is not passive, it must be registered as active again.
	if not self._passive_shapes[shape] then
		self._active_shapes[shape] = shape
	end
	self._ghost_shapes[shape] = nil
	return self:setSolid(...)
end

-- the module
HC = common_local.class("HardonCollider", HC)
local function new(...)
	return common_local.instance(HC, ...)
end

return setmetatable({HardonCollider = HC, new = new},
	{__call = function(_,...) return new(...) end})