What's the best way to implement one-dimensional collision detection?

Question

I'm writing a piece of simulation software, and need an efficient way to test for collisions along a line.

The simulation is of a train crossing several switches on a track. When a wheel comes within N inches of the switch, the switch turns on, then turns off when the wheel leaves. Since all wheels are the same size, and all switches are the same size, I can represent them as a single coordinate X along the track. Switch distances and wheel distances don't change in relation to each other, once set.

This is a fairly trivial problem when done through brute force by placing the X coordinates in lists, and traversing them, but I need a way to do so efficiently, because it needs to be extremely accurate, even when the train is moving at high speeds. There's a ton of tutorials on 2D collision detection, but I'm not sure the best way to go about this unique 1D scenario.

---

Apparently there's some confusion about what my data looks like.

I'm simulating a single site, not an entire region. The trains can be of any length, with different types of cars, but there is only ever one train. My train data is in the form {48,96,508,556,626,674,...}, indicating the distances from the front of the train (0) to the center of the axle.

(Train data will more likely come to me in the form of an ordered list of Car objects, each of which has a length and a list of integers representing axle distances from the front of that car, but it all gets aggregated into a single list, since all axles are the same to me.)

My switches are all within several hundred feet, and will often be entirely covered by the train, The switches can be at any interval from hundreds of feet to several inches apart, and is in the same form as the train: {0,8,512,520,...}, indicating the distances from the beginning of the site to the center of the switch.

Finally, I know the distance at which the wheel activates the switch, in inches.

For example, using the above sample data, and a an activation distance of 8 inches, the first switch at X=0 would activate when the train hits X=40, meaning the train is 40 inches into the site. When the train hits X=48, the switch at X=8 is also activated. At X=56, the first switch goes off, and at X=64, the second switch also goes off. Different axles are turning different switches on and off as it crosses the site.

The train is usually running at speeds under 10 mph, but can go much higher. (Right now our simulation is capped at 30 mph, but higher would be great.)

Answer 1

Have a sorted list of all the switches' coordinates and use binary search on the list to find the nearest switch. Then check to see how far it is and whether or not it's a collision.

O(log n)

Another option is to exploit the fact that the train moves along the track and can only ever come close to two switches, one behind and one ahead.

Construct a doubly-linked list of all the switches and position an extra node to represent the train in the correct location in the linked list. Then only check proximity to the switch the train is headed towards.

O(1)

To save memory, store the sorted coordinates in an array and simply keep track of which indexes the train is between.