Re: [Lib2geom-devel] Maximum distance between curves

[Alexander B. <Bro...@we...>]

On 30/03/15 04:25, Krzysztof Kosiński wrote:
> For the new Boolean operations algorithm, I could use a routine which
> calculates the following: Given two curves, or even better two
> sequences of curves, find a time value on one of them that maximizes
> the distance from the other. In other words, I want to find t on c1
> such that the distance from c1.poinAt(t) to the nearest point on c2 is
> maximal. It can be assumed that the endpoints of both curve sequences
> are exactly equal.
>
> Is there some clever way to calculate this?
>
> I need this to determine whether the fragments of paths between two
> intersections are sufficiently similar to one another that they can be
> considered the same.

Do I understand correctly that you don't actually need the exact
distance but instead an algorithm which always gives one of the
following two results would be sufficient?
a) The curves are guaranteed to have a maximum distance of smaller than x
b) The curves are guaranteed to have a maximum distance of greater (or
equal) than x

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)

The second section leads to a method which should be rather easy to
implement and it gives upper and lower bounds for the maximum distance.

One problem is that different control points can parameterize similar
curves. Extreme example:
If the second and third control points lie anywhere on the straight line
between the first and fourth control point the result is always a
straight line.
If the second and third control points lie "almost" on the straight line
between the first and fourth control point you could probably change
them "a lot" without getting very different curves.

I think the ideas I wrote down might work for most cases (and fast). If
the upper and lower bounds are useless, e.g. in the extreme cases
mentioned you could fall back to converting the curves into sufficiently
accurate polygon segments and measure their distance (this is probably
slower).

Regards,
Alexander