search

mattools / matGeom

Matlab geometry toolbox for 2D/3D geometric computing
BSD 2-Clause "Simplified" License
265 stars 98 forks source link

non-recursive simplifyPolyline #68

Open kakila opened 5 years ago

kakila commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 3 years ago

The non-recursive functions are

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 commented 3 years ago

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 commented 3 years ago

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