Provide an algorithm for collision of Bezier curves with a set of segments

[ybertot]

Input:

• a set of obstacles, described by a set of straight-line segments,
• a trajectory given by a sequence of elementary Bezier curve,

Output:
a list of pairs of a straight-line segment and an elementary Bezier curve, where potential collision has been detected.

The correctness will be stated in the following fashion: if the output list is empty, there is no intersection between any of the elementary segments and any of the straight-line segments.

How it works: for every straight-line segment and every elementary Bezier curve in the input:

• compute the convex hull of the control points : this is a sequence of points, which also gives a sequence of segments,
• compute whether the segments on the convex hull intersects the obstacle segment,
• if there is an intersection, then add the pair of the straight-line segment and elementary Bezier curve in the output
• if there is no intersection, then check whether one of the extremities is outside the convex hull (no need to check both)
• if one of the extremities is inside, this pair should be added to the output
• if one of the extremities is outside, this pair is safe and can be discarded

Possible refinement:

• When there is a potentially colliding pair, it may be worth collecting all the colliding pairs with the same Bezier curve, splitting this curve in two using Casteljau dichotomy, and check again collision only for the straight-line segments from the collected colliding pairs. This process can be repeated recursively, but it is difficult to choose a termination criterion.
• To decide termination one could decide to stop the the refinement process when the dichotomy obtains a convex hull where all points are too close to the obstacle.
• A stronger refinement would be to stop when proving collision. This can be obtained if the first and last control point are on both sides of the obstacle and the obstacle has a collision with the convex hull.

If the obstacles have been preprocessed in a vertical cell decomposition, there should be a way to reduce the number of pairs that need to be considered.