# Corona SDK – Curve fitting 1 – Implementation of Ramer-Douglas-Peucker algorithm to reduce points of a curve

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 🙂