Line Simplification: Visvalingam's Algorithm
(Above: A screenshot of the demo of my implementation of Visvalingam's line simplification algorithm. Link below!)
For a secret project of mine I've been working on since about February time (if I recall correctly), I've discovered that I could make some considerable use of a line simplification algorithm. The tricky thing is though that I need an implementation in both Javascript and C♯ - which will both return identical results.
Initially, I chose the Ramer-Douglas-Peucker Algorithm, but I ended up implementing Visvalingam's Algorithm instead, as I encountered issues with calculating the shortest distance from a point to a line reliably along with other algorithmic problems that I determined weren't worth the time to fix.
Visvalingam's algorithm is actually really simple. Suppose we take a line:
If we create a sliding window with a width of 3 and slide it along the list of points, then we get a set of triangles. To simplify the line, we can calculate the area of each of these triangles, and remove the centre point of the triangle with the smallest area.
Then we can continue removing the centre point of the smallest triangle until we reach a triangle with an area that's above a threshold we set - and this is Visvalingam's Algorithm.
Though I haven't written the C♯ version yet, I've completed the Javascript implementation - and created a demo for you to play around with! Here's a link:
Note that you'll need to enable ES6 Module support in your browser to get it to work, as I've used ES6 Modules whilst building it.
In Firefox this can be done by setting dom.moduleScripts.enabled to true in about:config, and in chrome by visiting chrome://flags/#enable-javascript-harmony (sorry, hyperlinks don't work for chrome:// urls IIRC!), enabling it, and restarting your browser.
It's open-source, of course - under the Mozilla Public License 2.0. You can find my code on GitHub - and pull requests are welcome :D
Finally, I've released it as an npm package. If you aren't aware of npm, it's really cool. It's the primary package manager for Javascript - I've written a blog post on this here.
Once I've written the C♯ version I'll have another bash at trying to get Nuget to package it. I think I know what the issue has been so far - so hopefully it works this time! If it does I'll blog about that too.
Found this useful? Think it's cool? Let me know in the comments below!