Re: [Lib2geom-devel] Maximum distance between curves

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

On Tue, Apr 07, 2015 at 10:51:42AM +0200, Alexander Brock wrote:
> I have ideas:
> a) If the endpoints of the bezier _segments_ are identical things get a
> lot less complex. I experimented with two ideas on how to get an upper
> bound for the distance and wrote them both down. The second looks
> promising to me, it only involves calculating the roots of a square
> polynomial and the distances of the control points and gives you upper
> and lower bounds for the maximum distance.
> 
> b) Let's assume curve A is a single bezier segment and curve B composed
> of two bezier segments. Find the point Z on A which minimizes the
> distance between the curve A and the point on B where the first segment
> ends and the second starts. If that difference is greater than x you're
> finished.
> Otherwise decompose A at the point Z into two bezier segments which exactly
> represent A and use idea a).
> 
> c) Any two curves A and B which are exactly the same but composed
> differently can be decomposed into smaller bezier segments such that
> every segment in A' has an exactly equal corresponding segment in B'
> 
> https://github.com/abrock/optimization (I'll give push rights to anyone
> who asks)

Your pdf is written in terms of only $t$, but Krys needs argmin over
$t,s$ of $||P(t) - Q(s)||_2$.  If it were only 1 domain, transforming
the problem into root(Bezier) would be very fast and very robust.

I think your subdivsion approach has merit though.  It is very similar
to a common approach for computing
https://en.wikipedia.org/wiki/Fr%C3%A9chet_distance that uses dynamic
programming in the free space diagram.

There is some code written I think by Marco which gives minimum
distances.  From memory it worked by formulating the inter curve
extrema as normal matching, and hence being able to use bezier
clipping to efficiently find solutions.  But I also remember it being
quite slow.

The overall problem can be solved as dp over sequences of beziergons,
subdividing and potentially bounding using the curve-curve distance
once you are down to plausible pairs.  But I think this code exists :)

> One problem is that different control points can parameterize similar
> curves. Extreme example:

Yes, this single factor makes many otherwise simple problems very
difficult with parametric curves.  :(

As a result, I suspect that performing everything for boolops in the
implicit domain is a more tractable approach.  Especially with careful
bounding a la libaffa or interval bezier arithmetic.

njh