Closed bacchanalia closed 5 years ago
I can reproduce the issue. Tracking it down further now.
We can make bezierClip
in Diagrams.TwoD.Segment
much more robust. It tries to narrow down potential intersections by intersecting a "fat line" of a portion of one curve with the convex hull of part of the other. In this case, there is no viable end condition as the end points of the two original segments match. There is no handling of the case where we have subdivided to a zero length line. It may be the case that the cubicbezier
package has improved this code, but otherwise, we need to at least make lineEquation
not produce NaN and bezierClip
detect when the t
and u
intervals are equal (this might be as simple as changing the order of the cases, but that might have other implications).
It looks like there are significant changes in the cubicbezier
package, but it
isn't immediately clear how they map to the code we have.
Here are some of the issues I see in Diagrams.TwoD.Segment
as it is right now:
lineEquation
function does not work if the two points are the same or very close.
lineDistance
. Logically that function should fallback
to just being the distance to the point, but given it's type, we cannot
check for NaN from lineEquation
. Do we every rely on Floating
not
being RealFloat
? How safe are zero checks?lineEquation
altogether in some cases
or do it once, so it should probably return four values.intersectPt
:
chopHull
and it does some (not
sufficient I don't think) checking. It should be moved closer to those
assumptions and the assumptions checked.inRange
function uses defEps
and is used by functions that have an
epsilon argument.
A broader issue with segmentSegment
is the behavior when curves overlap. I
think we might be able do a reasonable job with that situation, but we need to
be really clear what the semantics are. For instance, there are Bezier curves
that have parts that overlap, don't overlap, and intersect at a single point.
For example:
import Diagrams.Prelude
import Diagrams.Backend.SVG.CmdLine
b = fromSegments [bezier3 (V2 4 0) (V2 1 3) (V2 1 (-1))] :: Located (Trail V2 Double)
b1 = stroke $ section b 0.0 0.6 :: Diagram B
b2 = stroke $ section b 0.4 1.0 :: Diagram B
main = mainWith . pad 1.1 . lw 7.0 $ mconcat
[ b1 # lcA (blue `withOpacity` 0.5)
, b2 # lcA (red `withOpacity` 0.5)
]
I think for this example it is clear what we would ideally want, segmentSegment
to result in a list of values from a sum type that separates individual intersections from overlaps. What is less clear is the situation where there is a large part of the curve that "overlaps within epsilon". We probably need separate functions for the different meanings people might have.
I think "overlaps within epsilon" aught to have to same behaviour as precise overlap because "precise" is going to be often be fuzzy do to floating point math anyway and otherwise we run into the problem of sectionSection trying to return a huge set of points along the overlap.
I imagine having two functions: segmentSegmentPoints
and
segmentSegmentOverlaps
for lack of better names. Both would have the same
result type:
data Intersection n = IPoint n n | IOverlap (n,n) (n,n)
segmentSegmentPoints :: OrderedField n
=> n -- epsilon in the parameter space
-> FixedSegment V2 n
-> FixedSegment V2 n
-> [Intersection n]
segmentSegmentOverlaps :: OrderedField n
=> n -- epsilon in V2 Euclidean space
-> FixedSegment V2 n
-> FixedSegment V2 n
-> [Intersection n]
The Points
version will still include "exact" overlaps when they happen, but
will only include up to the maximum number of possible intersections for the
rest of the curve guided by the epsilon in parameter space (two intersections
within epsilon of each other may count as one). The Overlaps
version would
try to find inexact overlaps guided by an epsilon in Euclidean space (as long
a stretch where the curves are within epsilon of each other).
Slight perturbations of d and r avoid the bug, as does increasing e (default 1e-8).