• 12
• 12
• 9
• 10
• 13

# Remain on track between points

This topic is 3197 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I have a number of points on a path that I want my vehicles to follow, (to an end point). But the vehicles do not always start/apear at the beginning of the path, (or even anywhere near the path), they can join at any point. In the example above, the vehicle X, Y and Z need to fly toward B, C and D respectively to 'rejoin' the path. At first I thought it was a matter of distance, (rejoin the nearest point), but as in the case of 'Y' or 'Z' this would not work. What would be the easiest way of knowing what the 'next' point should be for the vehicle to aim in order to rejoin the path? Thanks FFMG

##### Share on other sites
Here is a relatively straightward way to determine the 'next' waypoint on the path given the vehicle's current position:

- Find the closest point on the path to the vehicle position
- Determine which path segment this closest point lies on
- The next waypoint is the second endpoint of this segment

The easiest way to find the closest point on the path would be to find the closest point on each path segment, and then choose the closest of these (this process will also tell you to which segment the next waypoint belongs).

Let me know if you need further info.

##### Share on other sites
You could also calculate the direction to the closest point on the path and take the dot product with the direction the next point on the path (the one after the closest). If the dot product is positive, go to the closest point, if it is negative (or 0) go to the next point.

XA dot XB would be negative -> go to B
YB dot YC would be 0 (more or less) -> go to C
ZC dot ZD would be positive -> go to C

##### Share on other sites
Quote:
 Original post by jykHere is a relatively straightward way to determine the 'next' waypoint on the path given the vehicle's current position:- Find the closest point on the path to the vehicle position- Determine which path segment this closest point lies on- The next waypoint is the second endpoint of this segmentThe easiest way to find the closest point on the path would be to find the closest point on each path segment, and then choose the closest of these (this process will also tell you to which segment the next waypoint belongs).Let me know if you need further info.

Thanks, I just want to make sure I understand.
In the case of 'X', (in my example).

It looks like X is closer to A.
A is part of the A->B segment
So the vehicle must travel toward 'B'

This seems to make sense.

What would be the best way 'calculate/compute' what segment a point lies on?

Because, in the case 'Z', the nearest point is 'C'. But how do I know that the segment is B->C and not C->D and that I should be travelling toward 'D'?

FFMG

##### Share on other sites
Quote:
 Original post by Lord_EvilYou could also calculate the direction to the closest point on the path and take the dot product with the direction the next point on the path (the one after the closest). If the dot product is positive, go to the closest point, if it is negative (or 0) go to the next point.In your example:XA dot XB would be negative -> go to BYB dot YC would be 0 (more or less) -> go to CZC dot ZD would be positive -> go to C

Thanks for that, unfortunately I am not that familiar with the dot notation.

How would I do a dot product?

FFMG

##### Share on other sites
Find the minimum distance between the point and line. The math is easy and there are lots of explanations (eg: this one, just make sure to follow the second note). Do this for every line segment in your path, as jyk described, and the one with the smallest distance is the segment you are closest to. Then just proceed towards the end point of the line. You only need to know which line, not which vertex, the point is closest to.

Edit: Maybe you should Google dot product - I know there's plenty of information out there for it.

##### Share on other sites
Quote:
 Original post by EzbezFind the minimum distance between the point and line. The math is easy and there are lots of explanations (eg: this one, just make sure to follow the second note). Do this for every line segment in your path, as jyk described, and the one with the smallest distance is the segment you are closest to. Then just proceed towards the end point of the line. You only need to know which line, not which vertex, the point is closest to.

Thanks for the info, I'll try and come up with a function to get me the next point to head to.

I mis-understood, I thought I had to find the nearest distance to a point, not to a line, it makes more sense now.

Quote:
 Original post by EzbezEdit: Maybe you should Google dot product - I know there's plenty of information out there for it.

Ok, ok, maybe I asked for that.

FFMG

##### Share on other sites
nearest point on a segment, to a point, plus the distanced squared.

Quote:
 float pointSegmentDistance(const Vector& point, const Vector& start, const Vector& end, Vector& closestPointOnSegment){ Vector edge = (end - start); Vector delta = (point - start); float edge_length_squared = edge.dotProduct(edge); float edge_project = delta.dotProduct(edge); float t = edge_project / edge_length_squared; if(t < 0.0f) t = 0.0f; else if(t > 1.0f) t = 1.0f; closestPointOnSegment = start + edge * t; Vector distance = (closestPointOnSegment - point); float distance_squared = distance.dotProduct(distance); return distance_squared;}

so in the end, you just pick the edge with the smallest distance, and the closest point on edge could be, for example, the point to aim at to rejoin the track.