Calculating specific coordinate along a path

Question

Let's say I have a path comprised of a sequence of points that are connect by lines and arcs. The entire path has some specific length. Let's call that length 100.

What would be the mechanism to determine the exact x,y coordinate for any given point on that path?

meaning...

 Path path = new Path();
//fill in various lineTos and arcTos to the path here
....


Point p = getCoordsFromPath(path, 50.0f); //get the coords at the half way point on the path

Point getCoordsFromPath(Path inP, float position){
    Point ret;
    //do some magic and get the x,y at the point in the path 
    //that is the position distance from start

    return ret;
}

TIA

Answer 1

Unless your paths are parameterized based on lengths, then you'll have a bit of difficulty doing this. I'm going to give you a solution outline for paths containing only line segments, because distances are easy to calculate on line segments as they are with parameterizations.

The setup I'm assuming there is that you have n + 1 points P_1, P_2, ..., P_{n}, P_{n + 1} and a collection of n parameterized intervals: I_{k}(t) = P_{k} * (1 - t_k) + t_k * P_{k + 1}.

You'll need to compute the lengths of these intervals as well. I'll call these L_{1}, ..., L_{n}.

First, you need to figure out which interval you are working over. To do this, we can simply take the input distance D and begin subtracting the distances until we find the parameterization for which that subtract causes our distance to become negative:

D = initial distance
k = 0
while (D >= 0)
  D -= L[k]
  k += 1
end

This value of k computed here tells me I'm on the kth parameterization. I take my value of D, add L[k] back onto it, and this number here is the length along that parameterization that I have traveled since the start of that parameterization. So to get the point along the curve, I use

D += L[k]
t_location = D / L[k]
point_to_be_found = P_{k} * (1 - t_location ) + t_location * P_{k + 1}

I'm sorry for being too abstract, but hopefully this helps with the case of line segments. A similar adaptation can be made for arc lengths. However, you have to be weary about using certain parameterizations for arc lengths, because the ratio t_location above won't necessarily be linked to the actual distance along the curve. For example, if you have a circle parameterized by ( h, (1 - h^2) / (1 + h^2) ), the value of h corresponding to an arc length of one-quarter of the circle 1/2, but the length is pi/4.

Answer 2

currentSegment = 0;
position = (0,0);
distance = 0;
while(currentSegment < segments.count && distance < desiredDistance){
  if (desiredDistance > (distance + segments[currentSegment].length)){
    distance += segments[currentSegment].length;
    position += segments[currentSegment].positionChange;
    currentSegment++;
  } else {
    position += segments[currentSegment].positionChangeAtDistance(
      desiredDistance - distance);
    distance = desiredDistance;
  }
}
return position;

In my pseudocode, positionChangeAtDistance is a lerp along an arc or line.