How to find how many times an object's path crosses another?

I have several hundred objects that will move in a fixed area throughout the day. Frequently the objects will cross over another object's path, either at the same time (eg. a collision) or within a few seconds or minutes, the time window tolerance. How can I determine how many times that happens throughout a fixed period of time, let's say in a day?

For example, to visualize it on a simple level, let's say I have 2 points, A & B, arranged in a north-south and east-west configuration:

(A) - Loc 1

|
|

Loc 3---------------------- (B) Loc 4

|
|
Loc 2

Object A moves only from Loc 1 to Loc 2 throughout a given period of time. Likewise Object B only moves from Loc 3 to Loc 4 during that same period of time. They cross paths at the center. One could just calculate the speed of A and figure out when it hits the location of the path cross, and also do that with B. Then simply determine when those cross point time windows are close. However that logic breaks down when I have hundreds of objects, variable indirect paths, and changing speeds.

What I am given at the end of the day is the path of each object, timestamps along the path, stops and times. Is there a straightforward way or algorithm to determine how many times one path crossed another during a time window tolerance?

• Or, to put it another way, "What is the algorithm behind Strava's "Fly-bys" feature?" – David Richerby Dec 31 '18 at 21:50
• That seems to be very similar. Any ideas on how it's done? – MeeBee Jan 1 at 1:27
• How is the path given? Is it a list of line segments? – D.W. Feb 10 at 8:08

This can be done by what I'd call "accelerated replay" (I'm making up this term).

Let's suppose the movement of each object is piecewise linear: each object moves in a straight line at a constant speed for a while, then changes direction and moves in a different direction at a different speed, etc. So, object $$i$$'s path can be specified a sequence of times $$t_{i,0},t_{i,1},\dots,t_{i,n}$$ at which the object changes direction; between times $$t_{i,j}$$ to $$t_{i,j+1}$$, the object is moving in a straight line (with known endpoints) at a constant speed. The algorithm can be generalized to allow each individual piece of the path to be curved or other shapes as well, but it's easiest to describe in this setting.

So, let's take the union of all of the times $$t_{i,j}$$ and sort them. In this way, we get a set of "events", where each "event" corresponds to an object changing direction/speed. Now, we're going to replay all of the object movements. However, we're going to "fast forward" through all of the times that fall between two adjacent events. In other words, we're going to iterate through the events in time order.

At a single step of the algorithm, we're going to be processing a particular event, say the event at time $$t_{i,j}$$ where object $$i$$ changes direction. We know the line segment that each of the other objects are currently on; and we know the line segment that object $$i$$ will travel on after time $$t_{i,j}$$. So, for each other object $$i'$$, compute the location where the lines for objects $$i$$ and $$i'$$ intersect, check the time when that will happen, and check whether that time is before the end time for both line segments; if so, you've found a cross-over. Notice that finding the intersection point of two line segments can be done in constant time ($$O(1)$$ time). Once you've done that, you've taken into account all cross-overs that can occur until the next event. So, no need to continue simulating what happens in any future time, until the next event. So, fast-forward to the next event, and then do the same thing for the next event.

The total running time will be $$O(nm)$$, where $$n$$ is the number of objects and $$m$$ is the total number of events. Or, if you expect $$q$$ events per object (i.e., $$q$$ changes of direction), then the total running time will be $$O(n^2q)$$. Since you have only a few hundred objects, that should be quite reasonable.

It's plausible to me that it might be possible to reduce this to something more like $$O(nq \log n)$$, using techniques from computational geometry (e.g., Shamos-Hoey etc.), if that were really necessary -- but I haven't tried to think about whether that's possible, as given the numbers you listed in your question, the algorithm above should be fine.

If you want to find "points of closest approach" instead of "crossovers", it's easy to adjust the above algorithm to do that. Given two line segments, it is easy to find their point of closest approach in $$O(1)$$ time, so then you just apply the same ideas as before. If you want to deal with curved trajectories, that is also possible; if you have two curved lines that are parts of a circle, it is also possible to find whether they intersect in $$O(1)$$ time using some trigonometry, so again you can generalize the above algorithm to handle that as well.

There are probably many pragmatic ways one could speed this up, e.g., by using quadtrees to separate the plane into multiple regions and map each part of the path to the region(s) it visits, and then only look for crossovers within each region.