... I'm trying to bash-together two bezier curves. What I've got is a list of, essentially, travel plans. Plural vehicles travelling at varying velocities are going to be travelling through a physical system. They announce their intended paths as a (now-time, future-time, list-of-bezier-curves) tuple, with the now-time being what time they are issuing the intent at, the future-time being when they expect to be at the end of the list of curves, and then the list of curves they plan to travel. I've got a decent solution (which took Maple 4 minutes to grind out) for determining intersection-or-not of two 3-vertex 2nd-order bezier curves, and I've got an algorithm for breaking curves into subcurves if need be. My question asks about something a little more complex... My current solution only offers saying "these two vehicles might collide at this segment of their plans", and only assuming the two vehicles maintain constant speed over the course of their entire announced plan. I want to allow vehicles to issue a series of 3-vertex bezier curves representing velocity over time, which will match pairwise to the 3-vertex curves representing position over time, which will help me get much more reliable collide-or-not tests, but I'm not sure how to incorporate this into my existing mathematics. Any suggestions? More critically, my current solution seems to offer where the distance between the two curves actually reaches zero, but I'd prefer that vehicles can account for a safety margin of greater than a femtometer from their center of mass. Having already taken the absolute value of the solution, I'm pretty sure I can just add ±(r1+r2) tests onto the existing cases, right?

Clarification; the path curves do not make any statement about time at the moment; they are functions purely over physical space, not temporal. All the paths describe is a probable locus of position. Provided with the paths is the projected end time, which implies a constant and uniform velocity over the path. At current, I can find the estimated location at any time inside the [now,projected-end] range assuming constant velocity.

What I want to do is add the velocity curve so that given a time in the [now,future] range, I can find projected position anywhere along the path after accounting for varying speeds.

For instance, imagine one car is travelling a straight line at low speed, and another is zigging back and forth in a sine wave around this line at steadily increasing (but not linearly) speed.

In the current system, only the average velocity of the second car can be considered, which might lead to no projected collisions, when in fact the second car will T-bone the first on its third oscillation. I'm trying to improve on this.

The objective, by the way, is to make a general-purpose tactical path-planning and resolution system for automated or assisting systems of various kinds, like automating cars in a closed system, or assisting air-traffic control.

Except they aren't parameterized by arclength... they are parameterized by percentage along arc. My arc-chopping algorithm can make the endpoints of two curves line up, so that they begin and end at the same moments of time, but that doesn't solve the variable-speed problem. Also, intersection isn't good enough; I need closest approach, mainly because vehicles are of non-zero size, but also because 3D space is also a possible environment.

I could add time as an extra dimension of locus into the path information, so that in a 2-space environment each vertex will be (X,Y,T), which seems to solve a couple problems, including resolving path and velocity into a single curve. Now I just need a better way to find closest approach, because analyzing a function for its minimum at run-time is right out of the question, unless it can be done algebraicly. Any suggestions or references?

Further revelation; no, adding time as a dimension of the path does not solve any problems, and in fact adds on. When testing for closest-approach, it has to be at equal times. My cutting algorithm solves this. If I let time be a direction, I might start finding closest-approaches where the two paths do indeed come near to touching, but at thouroughly separate times. Not acceptable.

However, I think I can solve the variable-speed problem. I can still cut two arcs to be coincident in time-span; given a decent approximation of the length of the curves, I can just chop it up into acceptably small time-spans, and thus approximate varying velocity. This revelation came as a result of meditating on real-world vehicles' ability to accurately control velocity, only acceleration. Since acceleration over spans of 1/2-seconds is only a miniscule distance off from linear, this should be fine.

If I get any other show-stopping problems, I'll be back.

You could also try using dichotomy and bounding rectangles: it's fairly easy to compute a bounding rectangle for a portion of the curve between t1 and t2. Check if two bounding rectangles are colliding (4 comparisons), then compute two new bounding rectangles for each curve (using a new point at (t1+t2)/2 for instance), and do the additional 2 checks recursively. Whenever two checks fail, there won't be collision. Whenever two small enough rectangles collide (you can define "small" yourself) there is a collision.

Diagram from above post: