Line Simplification: Visvalingam's Algorithm
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.
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
about:config, and in chrome by visiting
chrome:// urls IIRC!), enabling it, and restarting your browser.
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!