Lua polygon exploder and triangulator

exploder

--bobcook47@hotmail.com
--M.I.T. license
physics=require ("physics")
physics.start()
physics.setGravity(0,0)
local noObject = true
local function create()
  local vertices = { 0,-110, 27,-35, 105,-35, 43,16, 65,90, 0,45, -65,90, -43,15, -105,-35, -27,-35 }
  local r, g, b = math.random(),math.random(),math.random()
  local o = display.newPolygon( 0, 0, vertices )
  o:translate(math.random()*display.contentWidth, math.random()*display.contentHeight)
  o:setFillColor( r, g, b )
  o.vertices = vertices
  o.fillColor={r,g,b}
  return o
end --create
local function area(poly)
  local n = #poly
  local a = 0
  p = n-1
  for q=1, n, 2 do
    a = a+poly[p]*poly[q+1] - poly[q]*poly[p+1]
    p = q
  end --for q
  return a * 0.5
end --area

--[[
	 * Check if the point P is inside the triangle defined by
	 * the points A,B,C
	 * 
	 * @param Ax Point A x-coordinate
	 * @param Ay Point A y-coordinate
	 * @param Bx Point B x-coordinate
	 * @param By Point B y-coordinate
	 * @param Cx Point C x-coordinate
	 * @param Cy Point C y-coordinate
	 * @param Px Point P x-coordinate
	 * @param Py Point P y-coordinate
	 * @return True if the point specified is within the triangle
	 --]]
local function insideTriangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py)
		local ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy
		local cCROSSap, bCROSScp, aCROSSbp

		ax = Cx - Bx
		ay = Cy - By
		bx = Ax - Cx
		by = Ay - Cy
		cx = Bx - Ax
		cy = By - Ay
		apx = Px - Ax
		apy = Py - Ay
		bpx = Px - Bx
		bpy = Py - By
		cpx = Px - Cx
		cpy = Py - Cy

		aCROSSbp = ax * bpy - ay * bpx
		cCROSSap = cx * apy - cy * apx
		bCROSScp = bx * cpy - by * cpx

		return (aCROSSbp >= 0.0) and (bCROSScp >= 0.0) and (cCROSSap >= 0.0)
end --insideTriangle
print(insideTriangle(100, 100, 150, 200, 50, 200, 100, 99))
--[[
	 * Cut a the contour and add a triangle into V to describe the 
	 * location of the cut
	 * 
	 * @param contour The list of points defining the polygon
	 * @param u The index of the first point
	 * @param v The index of the second point
	 * @param w The index of the third point
	 * @param n ?
	 * @param V The array to populate with indicies of triangles
	 * @return True if a triangle was found
--]]
local EPSILON=0.000001
local function snip(contour, u, v, w, n, V)
		local Ax, Ay, Bx, By, Cx, Cy, Px, Py

		Ax = contour[V[u]]
		Ay = contour[V[u]+1]

		Bx = contour[V[v]]
		By = contour[V[v]+1]

		Cx = contour[V[w]]
		Cy = contour[V[w]+1]

		if (EPSILON > (((Bx - Ax) * (Cy - Ay)) - ((By - Ay) * (Cx - Ax)))) then
			return false
		end --if

		for p = 1, n do
			if (p == u) or (p == v) or (p == w) then
			else
			  Px = contour[V[p]]
			  Py = contour[V[p]+1]
			  if (insideTriangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py)) then
				  return false
			  end --if
      end --if
		end --for p
		return true
end
--[[translated from Public Source at FlipCode.com
 * SUBMITTED BY JOHN W. RATCLIFF (jratcliff@verant.com) July 22, 2000
 --]]
local function triangulate(poly)
  local result = {}
  if #poly < 6 then return nil end
  --poly must be counter-clockwise
  local nv = #poly/2
  local V = {}
  if area(poly) >= 0 then
    for i=1, nv do
      V[i] = i*2-1
    end --for i
  else
    for i=1, nv do
      V[i] = #poly-i*2+1
    end --for i
  end --if
  --remove nv-2 Vertices, creating 1 triangle every time
  local count = nv * 2
  local v = nv
  while nv > 2 do
    count = count - 1
    if count < 0 then
      return nil
    end
    --three consecutive vertices in current polygon, <u,v,w>
    local u = v
    if u > nv then u=1 end --previous
    v = u+1
    if v > nv then v=1 end --new v
    local w = v+1
    if w > nv then w=1 end --next
    if snip(poly, u, v, w, nv, V) then
      local a=V[u]
      local b=V[v]
      local c=V[w]
      table.insert(result, poly[a]) table.insert(result, poly[a+1])
      table.insert(result, poly[b]) table.insert(result, poly[b+1])
      table.insert(result, poly[c]) table.insert(result, poly[c+1])
      table.remove(V, v)
      nv = nv-1
      count = nv*2
    end --if
  end --while nv
  return result
end --triangulate
local bodies={}
local function explode(poly)
  local result = triangulate(poly.vertices)
  for i=1,#result-5,6 do
    local r,g,b=math.random(),math.random(),math.random()
    local p=display.newPolygon(poly.x, poly.y, {result[i],result[i+1],result[i+2],result[i+3],result[i+4],result[i+5]})
    p:setFillColor(unpack(poly.fillColor))
    physics.addBody(p)
    p:applyAngularImpulse(math.random()*72)
    bodies[#bodies+1] = p
  end --for i
end
local function touched(event)
  print(event.x, event.y)
  event.target:removeEventListener('tap', touched)
  explode(event.target)
  display.remove(event.target)
  noObject = true
end
local function update()
  for i=#bodies, 1, -1 do
    if bodies[i].x<0 or bodies[i].x>display.contentWidth then
      bodies[i]:removeSelf()
      table.remove(bodies, i)
    elseif bodies[i].y<0 or bodies[i].y>display.contentHeight then
      bodies[i]:removeSelf()
      table.remove(bodies, i)
    end --if
  end --for i
  if #bodies == 0 and noObject then
    create():addEventListener('tap', touched)
    noObject = false
  end --if
end
Runtime:addEventListener("enterFrame", update)