All Projects FreeCAD  Addon Manager  Arch  Assembly  Draft  Expressions  FEM  File formats  GCS  OpenSCAD  Part  PartDesign  Path  Project Tools & Websites  Raytracing  Robot  Sketcher  Spreadsheet  TechDraw

FreeCAD: master 6b3815a7

Diff Back to Repository
Author Committer Branch Timestamp Parent
Gabriel Wicke Gabriel Wicke master 2020-06-18 03:10:18 master f05253f8
Changeset [path] Implement Ramer-Douglas-Peucker line simplification

Implement an iterative version of the Ramer-Douglas-Peucker line
simplification algorithm
(https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm),
which reduces line complexity to a limited linear deviation from the
original polyline. The ability to reason about linear deflection is the
key improvement over the previous linear implementation.

Worst case complexity is O(n^2), but expected complexity for typical
cases is O(n log n). A potentially faster alternative would be to call
out to libclipper, treating the line as a closed polygon. However, in
practice, performance of this implementation seems good enough. A
complex 3d surface operation optimizes in a few seconds, and reduces
output gcode size from about 220MB with the previous implementation to
10MB.
mod - src/Mod/Path/PathScripts/PathSurface.py Diff File
mod - src/Mod/Path/PathScripts/PathUtils.py Diff File