Algorithms for 2D polygon simplification by collapsing segments?

Question

Recently I've been looking into some different methods of polygon simplification.

Popular methods include Ramer-Douglas-Peucker path simplification algorithm & Visvalingam, while they are both good algorithms, in some cases gives poor results by only ever removing points, never placing points in new locations (both a pro and a con depending on the usage).

I've been looking into using a simplified segment collapsing method, common for 3D geometry, see: Surface simplification using quadric error metrics.

From some quick tests this works reasonably well, however I suspect this isn't all that novel, possibly there are better methods for 2D polygons too.

I also looked into PO-Trace's method of polygon simplification, which is excellent, but focused on simplifying polygons extracted from bitmap images.

---

Are there well known algorithms for polygon simplification using segment collapsing?

Asking because I'm about to write my own function that uses quadric error metrics, but suspect this may exist already, possibly named differently.

If not, I'll link the code once its done.

Answer 1

The CGAL library provides an implementation of a polyline simplification algorithm.

It is based on the work of Dyken et al..