Hello,
In a current C++ project I'm working on, I need to segment a very big 3D polyline (between 100K and 1M pts) made by the path of a UAV into relatively straight segments. We implemented a 3D version of the Douglas-Peucker algorithm but it's not giving very good results, sometimes splitting very long segments of low curvature (it's only distance based without using curvature information). See attached screenshot to get a better idea of the problem.
Note that even though our path is in 3D, it could be projected in 2D for corner detection purpose if need be (it's not too far from being planar, UAV flying at relatively constant altitude).
I found many papers describing algorithms showing good results like:
- "ShortStraw: A Simple and Effective Corner Finder forPolylines"
- "A ShortStraw-based algorithm for corner finding in sketch-based interfaces" (named IStraw for short)
- "An Efficient Single Chord-based AccumulationTechnique (SCA) to Detect More Reliable Corners"
but no available Open Source implementation of any of these algorithms. I also need to be able to use it commercially (licensed like MIT, BOOST, etc), preferably in C++ or C. Would anybody know or could share such implementations?
Regards,
Bruno
I finally implemented a simplified version of the Short Straw algorithm from Wolin, Eoff and Hammond:
http://faculty.cse.tamu.edu/hammond/publications/pdf/2008WolinSBIM.pdf
It works very well for my kind of polylines.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Computer Graphics and Animation
- 3D