实现一维碰撞检测的最佳方法是什么？

Question

我正在编写一个模拟软件,需要一种有效的方法来测试沿线的碰撞.

模拟的是火车穿越轨道上的几个开关.当车轮在开关N英寸范围内时,开关打开,然后在车轮离开时关闭.由于所有车轮尺寸相同,并且所有开关尺寸相同,我可以将它们表示为沿轨道的单个坐标X. 一旦设定,开关距离和车轮距离就不会相互改变.

当通过将X坐标放入列表并遍历它们时通过蛮力完成这是一个相当微不足道的问题,但我需要一种有效的方法,因为它需要非常准确,即使列车高速移动.有大量关于2D碰撞检测的教程,但我不确定这种独特的1D场景的最佳方法.

---

显然,我的数据看起来有些混乱.

我正在模拟一个站点,而不是整个区域.火车可以是任何长度的,有不同类型的汽车,但只有一列火车.我的列车数据是表格{48,96,508,556,626,674,...},表示从火车前部(0)到车轴中心的距离.

(列车数据更有可能以有序的 物体列表的形式出现在我的身上Car ,每个物体都有一个长度和一个整数列表,表示距离汽车前部的车轴距离,但它们都聚合成一个列表,因为所有车轴对我来说都是一样的.)

我的开关都在几百英尺内,通常完全由火车覆盖.开关可以在几百英尺到几英寸之间的任何间隔,并且与火车的形式相同:{0,8,512,520,...},表示距离站点的开头到交换机的中心.

最后,我知道车轮启动开关的距离,以英寸为单位.

例如,使用上述样本数据和8英寸的激活距离,当列车到达X = 40时,X = 0处的第一个开关将激活,这意味着火车距离现场40英寸.当火车到达X = 48时,X = 8的开关也被激活.在X = 56时,第一个开关熄灭,而在X = 64时,第二个开关也熄灭.不同的轴在穿过现场时打开和关闭不同的开关.

火车通常以低于10英里/小时的速度运行,但可以更高.(现在我们的模拟时速仅为30英里/小时,但更高会更好.)

Answer 1

拥有所有开关坐标的排序列表,并在列表中使用二进制搜索来查找最近的开关.然后检查它是否有多远,以及它是否是碰撞.

O(log n)

另一个选择是利用火车沿轨道移动的事实,并且只能接近两个开关,一个在后面,一个在前面.

构建所有开关的双向链接列表,并定位一个额外的节点,以在链表中的正确位置表示列车.然后只检查火车前往的开关的接近程度.

O(1)

为了节省内存,将排序的坐标存储在一个数组中,并简单地跟踪列车在哪些索引之间.

Answer 2

将您的开关位置和灵敏度范围预处理为轨道段列表。每个段都有一个长度，并且在每个段之间有一组开关“开”或“关”事件。

switch_on ( 0 ), ( length: 8 ), switch_on ( 1 ), // x = zero here 
segment ( length: 8 ), switch_off ( 0 ),
segment ( length: 8 ), switch_off ( 1 ),
segment ( length: 488 ), switch_on ( 2 ),
segment ( length: 8 ), switch_on ( 3 ),
segment ( length: 8 ), switch_off ( 2 ),
segment ( length: 8 ), switch_off ( 3 ),
...

对于每个车轴，还显示其当前位置及其所在的轨道段。

如果您正在进行基于事件的模拟，则应将下一个事件安排为从车轴到其当前轨道段末端的距离的最小值。这与火车速度无关，并且准确（如果火车速度更快，您将不会错过转乘点）。如有必要，将事件存储在堆中（少于 30 个左右通常不值得，如有必要，请分析事件调度）。

处理一个事件的时间复杂度为 O(no-of-axles)。大多数步骤将涉及一两个开关状态更改和位置更新。在每个事件中，一个轴将导致一个开关打开或关闭（根据数据，同时发生的开关会导致两个事件，间隔为零），并且需要比较到其段结束的所有轴时间。您可以假设所有车轴以相同的速度行驶，也可以假设不同；就处理事件而言并不重要，它只会计算到达特定于相关轴的下一个开关的时间。

如果您正在进行固定时间步模拟，则处理在步骤结束时发生的所有事件，然后处理一个事件，将轴移动到它们在步骤结束时到达的点。