Re: [Lib2geom-devel] Maximum distance between curves

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

On Tue, Apr 07, 2015 at 09:33:44PM +0200, Krzysztof Kosiński wrote:

> Another idea I had is to somehow use the fact that Bezier curves are
> polynomial. It is well known that if two polynomials of degree n are
> equal at n+1 points, then they are equal everywhere. Perhaps this
> observation can be generalized to images of Bezier curves. It's very
> easy to see that this is the case for linear segments: if the
> endpoints of two linear segments are no further than delta apart, then
> no point on one segment is further than delta away from the nearest
> point on the other segment.

This is true for beziers because of the variation diminishing
property.  It is used for interval beziers.

> It's also true if the corresponding control points of Bezier curves
> are no further than delta away, but unfortunately the converse does
> not hold, i.e. there are some curves of equal images which have
> completely different control points.

Yes.

> Intuitively, it seems to me that the 'problematic' curves, such as
> Bezier curves with image equal to a line segment, may all be
> "redundant"; i.e. they can be represented exactly by a Bezier curve of
> lower degree.

You can transform any bezier into a higher order (only) by composing
with another polynomial (which is what these linelike segments are).
I'm not sure from your description whether you are aware that two
curves can be equal with completely different control points (compose
with an arbitrary linear polynomial = portion()); though I'm sure you
realise it.  You are correct that all 'problematic' curves have a
common factor and hence are under-constrained/degenerate because of
http://en.wikipedia.org/wiki/B%C3%A9zout%27s_theorem (and thus can be
degree reduced).

To prove two parameteric polynomial curves are equal requires sampling
at degree+1 points.  I think for bernstein basis the best points are
equaly spaced, as per
http://en.wikipedia.org/wiki/Bernstein_polynomial uniform
approximation theory.

> From the practical standpoint, I may be overthinking this - maybe I
> should just detect the most obvious cases, such as nearly-linear
> Bezier curves, and ignore the rest. I could simply use Alexander's
> idea b) and test the control points for nearness.

Thats certainly an excellent starting point - it should work in many
useful cases, and could potentially avoid a lot of expensive
numerics.  subdivision algorithms are generally very robust.  Do you
have a test set?

I've attached a collection of cases that mentalguy came up with (along
with an algorithm which is not too dissimilar to what you are
proposing :)

njh
p.s. I'm delighted you're working on this again :)