Closest Distance to a complex Line

I have a vehicle traveling along a road, and want to constantly monitor its distance from the ideal line, which I have as a mesh-object (Geometry) drawn with a vertex buffer. The way I am doing it right now, is by adding a bounding sphere to the vehicle and constantly checking the collision-results with the line-object. This of course is very precise, but very frame-expensive. What I am looking for is a method, to get the closest distance between the “line” object and the vehicle. If the line consisted of a dense row of vertices, this of course would not be a problem, but the line has sections that go over a long distance just straight, and has only two vertices forming that sections. Also, If I could find out the current line “segment”, I could simply use pythagoras to calculate the distance, but how would I identify the currently counting line segment?

Maybe someone has had a similar problem and has a good (precise and efficient) approach to solve this?

Thanks for any hints!


How many line segements have you?

A usuall approach would be to create some kind of acceleration structure, that you feed with vehicle position, and that returns a few possible lines, then brute force those preselected lines with pytagoras, and use best result.

Possibilites would be split the world into X*Y parts, and store for each part a array, of all lines intersecting it. -> Could be done at load or even precompiled.

Hey, thanks, thats the way I actually did it. The most tricky thing was to deal with sharp corners in the path. When simply using phytogoras on the closest line segments, this would give you a close distance if you just kept on riding straight over a turn. But, of course, this could be fixed, by checking, whether the car is actually within the range of the line-segment:

// line passed, do not use for calculation

Thanks for your answer though!

Generally, I suggest that when you have an algorithm that works you should just go on implementing your actual game and not worry too much about how ideal the implementation is. You can micro-optimize later and in fact more sensible because you know how (and how much) the game actually uses the created algorithms, so you can test your optimizations in the actual context. Its also a lot of fun improving your games performance by “simple” small-scalle optimizations, without having to think about the whole application context all the time as you do when you still implement the “framing” for everything. You also instantly know when your optimization code works or doesn’t work, because the game already works :slight_smile:

Just sayin’ though, its not any form of criticism, just came to my mind in this context.

@nromen: I think you are absolutely right! I am just still pretty new to all this, and that’s why I wanted to know, if others have dealt with this kind of thing in a way, that my “non-3d”-brain did not think about :slight_smile:

By the way, JME has a line segment math class that can give you distance to a line segment… ie: it takes care of the endpoints.

doh, thats right :slight_smile: now it´s as easy as it gets !