FFMG 114 Report post Posted June 18, 2009 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 0 Share this post Link to post Share on other sites
jyk 2094 Report post Posted June 18, 2009 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 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. 0 Share this post Link to post Share on other sites
Lord_Evil 680 Report post Posted June 18, 2009 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.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 0 Share this post Link to post Share on other sites
FFMG 114 Report post Posted June 19, 2009 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 segmentSo 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 0 Share this post Link to post Share on other sites
FFMG 114 Report post Posted June 19, 2009 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 CThanks for that, unfortunately I am not that familiar with the dot notation.How would I do a dot product?FFMG 0 Share this post Link to post Share on other sites
Ezbez 1164 Report post Posted June 19, 2009 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. 0 Share this post Link to post Share on other sites
Waterwalker 431 Report post Posted June 19, 2009 dot products [google] 0 Share this post Link to post Share on other sites
FFMG 114 Report post Posted June 19, 2009 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 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted June 19, 2009 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. 0 Share this post Link to post Share on other sites
brandonman 102 Report post Posted June 19, 2009 It's somewhat late here, so sorry if this is incohesive. I think a bezier curve might work well with this problem! Wiki Article with a good explanationIf you work with them for a bit, bezier curves really are not too hard to implement. Judging by your picture, a 3rd or 4th order curve would be the way to go! 0 Share this post Link to post Share on other sites