Find self-intersection points of a trail

[byorgey]

Using functions like intersectPointsT it is possible to find the points where two trails intersect. It would be nice to have a function to find self-intersection points of a single trail. Passing the same trail twice to intersectPointsT will not work since they intersect at every point.

[byorgey]

See #207 which this might be useful for.

[kuribas]

You could split the bezier at vertical (or any) directions, then use the intersection functions on these.

[byorgey]

@kuribas I am not sure I understand what you mean. If a trail has a self-intersection, splitting it at some point does not guarantee that the intersection will be between the two halves---it could still be a self-intersection of one of the two pieces. One can continue doing this recursively, of course, but I am not sure how you would know when to stop.

[kuribas]

If the curve doesn't turn more than 180 degrees, it cannot self-intersect (assuming no singularities).

[fryguybob]

@kuribas do you have a precise method of computing this turn? For instance:

d :: Diagram B
d = fromSegments . (:[]) $ (bezier3 (4 ^& 5) ((-1) ^& 0) (4 ^& 4))

d' :: Diagram B
d' = fromSegments . (:[]) $ (bezier3 (4 ^& 5) ((-1) ^& (-1)) (4 ^& 4))

Here d has a loop and d' does not.

[byorgey]

Oh! Now I think I understand. You mean to split the bezier at every point where the normal vector (or its negation) is equal to some fixed direction. Yes, I think that should work nicely. We don't even have to so subdivision etc. since finding the parameters to split on just amounts to solving a quadratic.

[kuribas]

yes. I use the derivative curve, but the idea is the same. For example B_x'(t) = 0 for vertical directions.