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

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 时，第二个开关也断开。不同的车轴在穿过 field 时打开和关闭不同的开关。

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

Answer 1

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

<罢工>O(log n)

另一种选择是利用火车沿着轨道移动并且只能靠近两个道岔的事实，一个在后面，一个在前面。

构造一个包含所有开关的双向链表，并在链表中的正确位置放置一个额外的节点来表示火车。然后只检查火车驶向的道岔附近。

O(1)

为了节省内存，将排序后的坐标存储在一个数组中，并简单地跟踪火车位于哪些索引之间。