检测 2d 平面中的 2 个移动物体何时靠近
假设我们有一个 2D 天空（10000x10000 坐标）。在天空中的任何地方，我们都可以拥有一架飞机，通过其位置(x, y)来识别。任何飞机都可以开始移动到另一个坐标（直线）。
有一个组件可以管理所有这些定位和移动。当飞机想要移动时，它会以(start_pos, speed, end_pos)的形式发送消息。我如何在组件中判断一架飞机何时会在另一架飞机的视线内移动（每架飞机都将其作为视线半径的属性）以便通知它。请注意，许多飞机可以同时移动。此外，该算法非常有效，它可以处理约 1000 个平面。
如果存在一些限制，那就限制了您的解决方案 - 它可能可以被删除。问题还没有解决。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
如果你想处理时间方面（即处理飞机移动的事实），那么我认为一种潜在的简化是通过时间维度来提升问题（增加一个维度 - 因此，原始问题是二维的，成为 3D 问题）。
然后，问题就变成了找到直线与（倾斜的）圆柱体相交的点。找到所有可能的交点将是 n^2；不太确定这是否足够有效。
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.
请参阅 Wikipedia:Quadtree 了解数据结构，可以轻松找到哪些飞机靠近给定的飞机。它将使您免于进行 O(N^2) 的紧密度测试。
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.
你有很好的答案，我只会评论一个方面，可能不正确，
所以，如果它们确实按照飞行计划并且不要偏离它们，你的问题是确定性的 - 它归结为求解一组方程，这对于大约 1000 架飞机来说并不是一项艰巨的任务。
如果您确实需要更快地求解这些方程，您可以采用其他答案中描述的技术，
当然，将时间转换为三维会将飞机从点变成线，最终您将搜索两条 3d 线之间最近的点（这里有一些 数学)
You have good answers, I'll comment only on one aspect and probably not correctly
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
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)
我实际上找到了这个问题的答案。
它位于实时碰撞检测一书中，p. 223. 它的名字也更好：与球体相交，其中 2D 球体是一个圆。在这里解释它并不是那么简单（而且我也可能违反了一些权利），但基本思想是将其中一个圆固定为一个点，将其半径添加到移动圆的半径上。移动方向的新方向是两个原始向量的和。
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.