Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

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.

share|improve this answer
    
that's a really good start, thanks... I was hoping for something less laborious, but if this is the only way, I'll muscle through it, I guess. –  Dr.Dredel May 28 '13 at 22:57
    
Yep. The unfortunate problem is that arc lengths and parameterized segments aren't always compatible, and you need to come up with some kind of formula, and this seems to nearly always be an ugly integral. I'd recommend foregoing the precision of actual arcs, and stick to sufficient numbers of line segments for simplicity. –  Jim Pedid May 28 '13 at 23:04
    
hmm... that would be a pretty ugly mess of line segments (if I understand your suggestion correctly). But I see why it might reduce the complexity of the calculation. –  Dr.Dredel May 28 '13 at 23:06
    
I wouldn't call it a mess, especially since it's really the same thing just stored via indexes. At the very worst, you're missing a small bit of accuracy here and there (which typically is negligible unless you are dealing with large pieces and not enough segments). But doing so provides you the benefit of working with linear objects, which is far more palatable than arbitrary curves. –  Jim Pedid May 28 '13 at 23:10
1  
@JimPedid arcs if guarantied to be circular are not that hard work with: you know the circle has circumference equal to "2*pi*r", and any arc which covers d radians of the circle will have length of exactly "d*r". –  Ali.S May 28 '13 at 23:26
add comment
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.

share|improve this answer
    
I know I should just test this, but can I really grab the length of an arcd segment? –  Dr.Dredel May 28 '13 at 23:00
1  
I am unfamiliar with that type of object. :) But if you know the arc angle in radians and the radius, the arc length is their product. The magic of radians! –  Seth Battin May 28 '13 at 23:02
    
excellent! I knew I should have paid more attention in Trig. –  Dr.Dredel May 28 '13 at 23:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.