non-recursive simplifyPolyline

[kakila]

Hi, The geometry package in GNU Octave had since long a simplifyPolyline function implementing non-recursive Here is the code https://sourceforge.net/p/octave/geometry/ci/release-3.0.0/tree/inst/polygons2d/simplifyPolyline.m

Now that geometry is trying to mirror matgeom we found out that matGeom now has its own implementation (but recursive).

Would you accept defining a upper level simplifyPolyline which accepts 'method' as an optional argument which allows the user to select recursive or non-recursive algorithm? In this way we could have both implementations. This allows for long time checks of performance (time , memory) and borderline cases. Otherwise one could just bechmark the two implementations (spoiler, non-recursive is faster) and decide for one.

The need to have the Octave implementation is not to get a penalty in runtime due to the implementation in matGeom, but let matGeom use the algorithm they like.

[dlegland]

Hi,

yes, it would be good to have both implementation, and let the user choose the most appropriate one depending on the needs.

Adding a "method" optional argument is fine for me. Not sure about the possible values ("recursive" vs "non-recursive" ?).

By the way, it seems to me that (Ramer-)Douglas-Peucker algorihtm is recursive by defintion... So what do you mean by non recursive? The use of bounding indices instead of creating subpolylines?

Also it's good to have a faster version! I can integrate it into the matlab version to benefit from the improvement as well, and to ensure better compatibility between matlab-octave.

[kakila]

Hi,

Ok, I will work on it. The (Ramer-)Douglas-Peucker algorihtm is recursive by definition, but it is quite easy to re-write it as non-recursive (that's should be what I did here). The class of recursive and non-recursive functions is equivalent.

[kakila]

The non-recursive functions are

• https://sourceforge.net/p/octave/geometry/ci/default/tree/inst/simplifyPolyline_geometry.m
• https://sourceforge.net/p/octave/geometry/ci/default/tree/inst/simplifyPolygon_geometry.m
• https://sourceforge.net/p/octave/geometry/ci/default/tree/inst/curve2polyline.m

Their code only needs to be adapted to matlab.

For future references: https://scicomp.stackexchange.com/questions/1906/converting-from-planar-polynomial-domain-to-planar-polygon

[dlegland]

Hi, and thanks a lot for the links! I had a very quick look, and I agree it would be interesting to include the algorithm. I think I can work on this during this summer.

[kakila]

Let me know if I can offer support on the conversion, but be aware that I do not have access to matlab.