Coastline Matching Algorithm

For the detection systematic search was used with a suitable error function.

Error function

The developed matching algorithm depends upon a function that can indicate the similarity of two curves. Most of the methods we considered applying are similar in that they all try to estimate the area of the shape made by the two curves, touching at thei r endpoints. The smaller this area is, the more similar the two curves are.

Development time was very limited, so we chose the approach that could be developed well in this short time. This approach is certainly less accurate than, for example the method that uses triangulisation. However, since we only seek a number that is inve rsely proportional to the similarity of the two curves and have no real need for the exact area, this simple method proved to be perfect for our purposes.

The algorithm first rotates and scales one of the paths, usually the subpath, in such a way that the curve's endpoints are on the main path. Then, using the lenght of the paths and a divider that needs to be supplied, it marks certain points on the curves at equal distances from each other. Having done these operations the two curves should have the same number of points marked. Considering the square distance between the corresponding points on the two paths it is possible to give an estimate of the area enclosed by the two curves.

Systematic search

The algorithm tries to find a starting and an ending point. Those points are selected systematically, and the error is calculated using the error function. The pointpair with the lower error is selected as the matching region.

Implementation details

• The error function was ceated by Marcell Nagy
• The search algorithm was ceated by Joonas Lehtinen

[ Main | Previous: Step 2 - chain code | Next: Step 4 - documentation ]