This article is the first part of a two part tutorial to do curve fitting. The motivation to do this came when I was playing the Flight Control Center game on my IPhone. I was very interested in this kind of game and wanted to know how to build a game like that. I wrote a sample on Corona SDK but the result was not as I expected. I found the airplane oscillated like a doll 🙂 Soon, I recognized the reason: because the path I had made was not smooth. Moreover, I recognized that to draw a smooth curve on a touched screen is almost impossible. So my mission was quite clear: “drawing a smooth curve that approximately like the curve made”.

I looked on the Internet for the solution and came up with the combination of 2 algorithms for curve fitting that solve the issue beautifully. Basically, there are two steps to be implemented:

– First, reduce the points of the handmade curve by approximating it using the algorithm of Ramer-Douglas-Peucker. This article is all about the implementation of this on LUA language for Corona SDK. I won’t write too much about the algorithm’s explanation as it was done greatly in the wiki.

– Second, draw a continuous curve through the received points in step 1 using the algorithm of P.J.Schneider. The implementation of this is also on Corona and comes on the next post.

Let’s have a look on the pseudo code provided from the wiki:

function DouglasPeucker(PointList[], epsilon) // Find the point with the maximum distance dmax = 0 index = 0 for i = 2 to (length(PointList) - 1) d = PerpendicularDistance(PointList[i], Line(PointList[1], PointList[end])) if d > dmax index = i dmax = d // If max distance is greater than epsilon, recursively simplify if dmax >= epsilon // Recursive call recResults1[] = DouglasPeucker(PointList[1...index], epsilon) recResults2[] = DouglasPeucker(PointList[index...end], epsilon) // Build the result list ResultList[] = {recResults1[1...end-1] recResults2[1...end]} else ResultList[] = {PointList[1], PointList[end]} // Return the result return ResultList[] end

The PerpendicularDistance mentioned in the pseudo code is the distance from a point to a line that is measured by the length of the line that perpendicularly connects that point to the line. It is more explained by the below figure:

The LUA code for calculating perpendicular distance:

-- calculating the distance from point1 to the line goes through point2 and point3 -- cross product of two vectors: v1 = (point1, point2) and v2 = (point1, point3) -- ==> v1(x, y) = (point2.x - point1.x, point2.y - point1. y); v2(x, y) = (point3.x - point1.x, point3.y - point1. y) -- v1 x v2 = v1.x.v2.y - v1.y.v2.x function dPointLine(point1, point2, point3) -- calculates area of the triangle local area = math.abs(0.5 * (point2.x * point3.y + point3.x * point1.y + point1.x * point2.y - point3.x * point2.y - point1.x * point3.y - point2.x * point1.y)) -- calculates the length of the bottom edge local bottom = math.sqrt((point2.x - point3.x) ^ 2 + (point2.y - point3.y) ^ 2) -- the triangle's height is also the distance found local height = area / bottom return height end

Here’s the code for implementing the main algorithm, please refer to the above pseudo code

-- points are the set of points to be reduced -- tolerance is value indicates degree of correctness for approximation -- the other parameters are for recursion function douglaspeucker(points, firstpoint, lastpoint, tolerance, pointIndices) local maxD = 0 local indexFurthest = 0 for i = firstpoint, lastpoint do local distance = dPointLine(points[i], points[firstpoint], points[lastpoint]) if distance > maxD then maxD = distance indexFurthest = i end end if maxD > tolerance and indexFurthest ~= 1 then table.insert(pointIndices, indexFurthest) douglaspeucker(points, firstpoint, indexFurthest, tolerance, pointIndices) douglaspeucker(points, indexFurthest, lastpoint, tolerance, pointIndices) end end

And here’s the full source code. Enjoy 🙂