Re: [Lib2geom-devel] Maximum distance between curves

[Krzysztof K. <twe...@gm...>]

2015-04-07 10:51 GMT+02:00 Alexander Brock <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

Yes.

However, maybe there is a simpler solution. What my boolops does is
the following:
- Compute all intersections.
- For each portion of the path between two intersections, pick a time
value that is somewhere not on the edge of the corresponding time
value interval. Compute the corresponding point.
- Compute the winding number of the other path at that point.
- Use that information to determine whether the relevant segment will
be in the result or not.

This algorithm works correctly even if there are second-order intersections.

The winding computation may return random results if the point is
exactly on the edge of the path. The only cases where my modification
of the Greiner-Hormann algorithm fails are:
- Shapes have common edges.
- By accident, a time value is picked which lies exactly at a
second-order intersection, which was not reported in step 1 due to
numeric precision issues.

Therefore, I need some way to determine whether two portions of the
path are sufficiently similar to consider them a common edge. If they
are, I can determine whether to include them in the result based on
the winding results for the surrounding portions. Otherwise the result
of the Boolean operation might be incorrect for this edge. For
instance, unioning two paths with a common edge may result in a path
which still has two subpaths.

> 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).

I also had an idea of this kind, probably I will use this.

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. 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.

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.

>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.

Regards, Krzysztof