mieko · February 24, 2024 15:47 · Sep 4, 2020 · Sep 4, 2020 · Sep 10, 2019
diff --git a/polygon-simplify.cc b/polygon-simplify.cc
@@ -1,5 +1,8 @@
-/* Polygon is just a vector<Point>, methods do exactly what you think. */
+/* You'll need a Point/Vec2 `dist_from_line` */
 
+typedef std::vector<Point> Polygon;
+typedef double Float;
+
 /* Polyline Simplification Algorithm */
 namespace DouglasPeucker {
   void simplify_section(const Polygon& pts,

diff --git a/MIT-LICENSE b/MIT-LICENSE
@@ -0,0 +1,15 @@
+Copyright 2016 Mike Owens
+
+Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation 
+files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, 
+modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the 
+Software is furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all copies or substantial portions of the 
+Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE 
+WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR 
+COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 
+OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
diff --git a/polygon-simplify.cc b/polygon-simplify.cc
@@ -0,0 +1,60 @@
+/* Polygon is just a vector<Point>, methods do exactly what you think. */
+
+/* Polyline Simplification Algorithm */
+namespace DouglasPeucker {
+  void simplify_section(const Polygon& pts,
+                        Float tolerance,
+                        size_t i, size_t j,
+                        std::vector<bool>* mark_map,
+                        size_t omitted = 0)
+  {
+    /* make sure we always return 2 points. */
+    if (pts.size() - omitted <= 2)
+      return;
+
+    assert(mark_map && mark_map->size() == pts.size());
+
+    if ((i + 1) == j) {
+      return;
+    }
+
+    Float max_distance = -1.0f;
+    size_t max_index = i;
+
+    for (size_t k = i + 1; k < j; k++) {
+      Float distance = abs(pts[k].dist_from_line(pts[i], pts[j]));
+
+      if (distance > max_distance) {
+        max_distance = distance;
+        max_index = k;
+      }
+    }
+
+    if (max_distance <= tolerance) {
+      for (size_t k = i + 1; k < j; k++) {
+        (*mark_map)[k] = false;
+        ++omitted;
+      }
+    } else {
+      simplify_section(pts, tolerance, i, max_index, mark_map, omitted);
+      simplify_section(pts, tolerance, max_index, j, mark_map, omitted);
+    }
+  }
+
+
+  Polygon simplify(const Polygon& vertices, Float tolerance)
+  {
+    std::vector<bool> mark_map(vertices.size(), true);
+
+    simplify_section(vertices, tolerance, 0, vertices.size() - 1, &mark_map);
+
+    Polygon result;
+    for (size_t i = 0; i != vertices.size(); ++i) {
+      if (mark_map[i]) {
+        result.push_back(vertices[i]);
+      }
+    }
+
+    return result;
+  }
+}