Re: [Lib2geom-devel] Maximum distance between curves

[Nathan H. <nj...@nj...>]

I think I had a response to your earlier post but I don't think I ever
sent it.  Anyway, looks promising.  Why not implement it and we can
see how well it performs in practice.  That's always the real test :)

If you can get a reasonably tight bound root polishing will work well.

roots() is very fast for low order polynomials (e.g. cubic) btw (100 ns).  I
would suggest transforming problems into roots() and benchmarking
before spending time on other approaches, as it's very hard to beat.

hausdorf distance turns out to be a bad measure for curve comparison
because it induces zigzags.
https://en.wikipedia.org/wiki/Fr%C3%A9chet_distance is much better in
this regard.

I might be missing something, but you are computing and approximation
of argmin_t |p(t) - q(t)|, but what you actually need is argmin_{s,t}
|p(s) - q(t)|.  Consider a line broken into two touching segments:
although the distance is 0, your algorithm will find the distance to
be the length of the curve.  This could be solved with some kind of
subdivision algorithm, but then you're back to the frechet polygon
problem, with bounds.

njh

On Wed, Jun 03, 2015 at 04:10:11PM +0200, Alexander Brock wrote:
> On 07/04/15 10:51, Alexander Brock wrote:
> > https://github.com/abrock/optimization (I'll give push rights to anyone
> > who asks)
> 
> I have two new estimations of the maximum distance, both do not depend
> on finding roots of polynomials (sections 0.3 and 0.4).
> 
> Regards
> Alexander
> 
> ------------------------------------------------------------------------------
> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel