Detect when 2 moving objects in 2d plane are close

Question

Imagine we have a 2D sky (10000x10000 coordinates). Anywhere on this sky we can have an aircraft, identified by its position (x, y). Any aircraft can start moving to another coordinates (in straight line).

There is a single component that manages all this positioning and movement. When a aircraft wants to move, it send it a message in the form of (start_pos, speed, end_pos). How can I tell in the component, when one aircraft will move in the line of sight of another (each aircraft has this as a property as radius of sight) in order to notify it. Note that many aircrafts can be moving at the same time. Also, this algorithm is good to be effective sa it can handle ~1000 planes.

---

If there is some constraint, that is limiting your solution - it can probably be removed. The problem is not fixed.

Answer 1

I actually found an answer to this question.

It is in the book Real-Time Collision Detection, p. 223. It's better named, as well: Intersecting Moving Sphere Against Sphere, where a 2D sphere is a circle. It's not so simple (and I may also violate some rights) to explain it here, but the basic idea is to fix one of the circles as a point, adding its radius to the radius of the moving one. The new direction for the moving one is the sum of the two original vectors.

Answer 2

• Use a line to represent the flight path.
• Convert each line to a rectangle embracing it. The width of the rectangle is determined by your definition of "close" (The bigger the safety distance is, the wider the rectangle should be).
• For each new flight plan:
  • Check if the new rectangle intersects with another rectangle.
    • If so, calculate when will each plane reach the collision point. If the time difference is too small (and you should define too small according to the scenario), refuse the new flight plan.

Answer 3

If you want to deal with the temporal aspect (i.e. dealing with the fact that the aircraft move), then I think a potentially simplification is lifting the problem by the time dimension (adding one more dimension - hence, the original problem, being 2D, becomes a 3D problem).

Then, the problem becomes a matter of finding the point where a line intersects a (tilted) cylinder. Finding all possible intersections would then be n^2; not too sure if that is efficient enough.

Answer 4

See Wikipedia:Quadtree for a data structure that will make it easy to find which airplanes are close to a given airplane. It will save you from doing O(N^2) tests for closeness.

Answer 5

You have good answers, I'll comment only on one aspect and probably not correctly

• you say that you aircrafts move in form (start_pos, speed, end_pos)
• if all aircrafts have such, let's call them, flightplans then you should be able to calculate directly when and where they will be within certain distance from each other, or when will they be at closest point from each other or if the will collide/get too near

So, if they indeed move according to the flightplans and do not deviate from them your problem is deterministic - it boils down to solving a set of equations, which for ~1000 planes is not such a big task.

If you do need to solve these equations faster you can employ the techniques described in other answers

• using efficient structures that can speedup calculating distances (quadtree, octree, kd-trees),
• splitting the problem to solve the equations only for some relevant future timeslice
• prioritize solving equations for pairs for which the distance changes most rapidly

Of course converting time to a third dimension turns the aircrafts from points into lines and you end up searching for the closest points between two 3d lines (here's some math)