如何最好地实现一维碰撞检测？

Question

我正在编写一款模拟软件，需要一种有效的方法来沿着一条线检测碰撞。这个模拟是火车在轨道上通过几个开关的情景。当车轮距离开关N英寸时，开关会打开，然后车轮离开时��关闭。由于所有车轮大小相同，所有开关大小也相同，我可以将它们表示为沿着轨道的单个坐标X。一旦设置，开关距离和车轮距离不会相互改变。

当使用列表将X坐标放置到其中并遍历它们时，这是一个相当琐碎的问题，但我需要一种高效的方法来做到这一点，因为即使火车以高速行驶，它也需要非常精确。有很多关于2D碰撞检测的教程，但我不确定如何处理这个独特的1D场景。

显然，对于我的数据有一些混淆。

我正在模拟一个站点，而不是整个区域。火车的长度可以是任意的，具有不同类型的车辆，但只有一个火车。我的火车数据是以{48,96,508,556,626,674,...}的形式表示，表示从火车前端(0)到轴心的距离。

（火车数据更可能以有序列表的形式出现，每个对象都有一个长度和表示轴距离的整数列表，但它们都被聚合成一个单一的列表，因为对我来说所有的轴都是相同的。）

我的开关都在几百英尺内，通常会完全被火车覆盖。开关可以在数百英尺至几英寸之间的任何间隔处，并且与火车相同： {0,8,512,520,...}，表示从站点开始到开关中心的距离。

最后，我知道车轮激活开关的距离，单位为英寸。

例如，使用上面的示例数据和8英寸的激活距离，X=0处的第一个开关将在火车达到X=40时激活，这意味着火车已经进入了40英寸的站点。当火车达到X=48时，X=8处的开关也被激活。当X=56时，第一个开关关闭，当X=64时，第二个开关也关闭。不同的轴正在跨越站点时打开和关闭不同的开关。

火车通常以低于10英里/小时的速度行驶，但可以更快。 （现在我们的模拟速度限制在30英里/小时，但更高的速度会更好。）

- dlras2

---

嗯...对我来说，显而易见的答案是采用2D解决方案并进行调整 - 最简单的方法是始终将一个维度保持不变（所有内容都具有y坐标为0）。那些解决方案不能轻松地进行调整，有什么原因吗？ - FrustratedWithFormsDesigner

那么你的数据集是什么样子的？你只有位置（相对于某个点的绝对距离），还是有可以进行掩码处理的东西？ - Clinton Pierce

我已经在上面添加了一些示例数据。你说的“mask against”是什么意思？我可以将数据从列表转换为其他结构。 - dlras2

@FrustratedWithFormsDesigner：考虑到数据的静态本质和单一维度，我认为采用二维解决方案会过于复杂。 - dlras2

轴间距是否可能小于激活距离？ - AShelly

Answer 1

有一个已排序的开关坐标列表，可以使用二分查找在列表中查找最近的开关。然后检查距离以及是否发生碰撞。

O(log n)

另一个选项是利用火车沿轨道移动并且只能接近两个开关（一个在后面，一个在前面）这一事实。

构造一个所有开关的双向链表，并将额外节点放置在正确位置以表示火车在链表中的位置。然后仅检查火车即将到达的开关的接近程度。

O(1)

为了节省内存，将排序后的坐标存储在数组中，并仅跟踪火车所处的索引。

- Ben S

---

我会担心第一个解决方案有两个问题。数据的“团块性”。在美国中西部，铁路线上的有趣点可能相距数百英里，导致二分搜索在高密度地区停滞不前。而且大多数情况下，搜索将返回空结果，这是二分搜索最慢的可能结果。 - Clinton Pierce

这正是我提供更好解决方案的原因。我会划掉那个糟糕的建议。 - Ben S

你误解了我的数据。我添加了一些样本 - 如果您有任何其他问题，请告诉我。 - dlras2

（虽然这可能是一个好的解决方案，但只要火车始终在两个开关之间，就可以实现。） - dlras2

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（轴数）。大多数步骤都涉及一到两个交换机状态更改和位置更新。每次事件中，一个轴会导致一个交换机开或关（根据数据同时发生的开关会导致两个事件，时间间隔为零），并需要比较所有轴到达其段末端的时间。您可以假设所有轴以相同的速度行驶，也可以不假设；对于事件的处理而言，这并不重要，它只是使到达下一个开关的时间计算特定于相关的轴。

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

- Pete Kirkham

---

对于相同的数据 - 6个轴，4个传感器 - 使用基于列表的调度程序（线性搜索下一个事件）将生成90个事件，用时0.09毫秒，并且使用基于二叉堆的调度程序（O(logN)搜索下一个事件）需要0.19毫秒，这对于大多数应用程序来说应该足够快了。如果您的火车长度真的是几倍于此（挂起事件的数量等于轴数，与传感器数量无关），那么基于堆的调度程序可能更好。 - Pete Kirkham

Answer 3

假设轴距始终大于激活距离，并且列车进入后路线不经常更改，您应该能够通过预先计算加快速度。基本上，对于每个开关，计算它将切换的火车行驶距离列表，然后随着火车前进遍历这些列表。

伪代码：

axles  = {48,96,508,556,626,674,...}
switches ={0,8,512,520,...}
activate = 8
float toggledist[num_switches]
boolean switchState[num_switches]={false,false,false,...}
int idx[num_switches]

for (i in switches)
  n = 0
  for (a in axles)
    toggledist[n++] = switches[i]+axles[a]-activate
    toggledist[n++] = switches[i]+axles[a]+activate

travel= 0.0f;

each (cycle)
  travel += TrainVelocity*time;
  for (i in switches)
    while (trigger>=toggledist[idx[i]])
      switchState[i]=!switchState[i];
      //additional processing for switch change here, if needed
      idx[i]++;

- AShelly

Answer 4

按照Ben的建议，将开关列表存储为双向链表。

在轮子对象（或结构体，如果有的话）中保留指向当前位置的下一个开关和上一个开关的指针。在轮子放置在轨道上时进行初始化。

当您移动到每个开关时，通过检查双向链表可以快速获取新的“下一个”和“上一个”开关，并将其替换为轮子对象中的“下一个”和“上一个”开关。

这避免了所有搜索，除了可能是轮子的初始放置。

此外，“开关”结构体可以用于保存指向所有将其列为“前一个”或“后一个”的轮子的接近度指针。（这里有一个互斥锁，因此要小心谁更新它。）这可以快速更新谁正在接近任何给定的开关以及他们与之间的距离。

- Clinton Pierce