• Advertisement

Archived

This topic is now archived and is closed to further replies.

tricki path problem

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

simple problem. i've a linelist wich consits of 10 points (1-10) now i wan't to calculate a second path wich follows the linelist on the right in a fixed distance (points a-j) so how do i calculate the a-j points? i know its a dumb ass question but i would be really appreciated for your help thx very much ps. excuse bad english
      			
			
                                   ------j
                                  ---10                                          \                                           \  i
                                        9  |
                                        |  |			                                |  |
   1--------------2                     8  |
  /                \		       /   h
 /  a-----------b   \           6-----7   /
/  /             \   3---4     /         /
  /		  \       \   /  f-----g
		   c---d   \ /  /
		        \   5  /
		     	 \    /
		     	  \  /
     			    e
    
[edited by - katanasi on May 30, 2002 5:28:20 PM]

Share this post


Link to post
Share on other sites
Advertisement
It''s not too hard, but not a dumb-ass question at all.

You''re looking to solve a constraint based problem.

Your constraints are:

Maintain the same gradient as the line segment you are parallel to (this means keeping track of what segment you are parallel to)

Maintain a constant distance from the current line segment AND the next line segment. (This latter constraint is what will cause you to move toward the next line segment. Simply make movement occur until you have satisfied this constraint... and keep satisfying the first constraint while satisfying this one)

When your movement halts (because you are at the point equidistant from the current and next line segments, simply increment the line segments... so the next segment becomes the current segment and the next+1 segment becomes the next segment.

Make sense?

Good luck and please let me know how it turns out.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Seems like the points you are after would be the intersection of the line parallel and the bisector of the angles.

Share this post


Link to post
Share on other sites
thank you for your answers.

but i don't really understand so pseudo code would be really really appreciated. (especially formula for calculating a-j points, how is this done?)

thx very much.

[edited by - katanasi on May 31, 2002 2:50:06 AM]

Share this post


Link to post
Share on other sites
Timkim,

That was an absolutely genius answer. Somewhat similar to how an ellipse is formed?

Share this post


Link to post
Share on other sites
quote:
Original post by Ronin Magus
Timkim,

That was an absolutely genius answer. Somewhat similar to how an ellipse is formed?


Thanks Ronin! I'm glad someone else can appreciate the beauty in the solution... I was quite proud of it myself! I guess all those years of mathematics are finally paying off!

katanasi... unfortunately I don't have time today to write code for the above algorithm. I'll try getting to it in a day or so...

Cheers,

Timkin






[edited by - Timkin on June 1, 2002 1:28:24 AM]

Share this post


Link to post
Share on other sites
Try this: Calculate a normal for each line segment. Then generate "vertex normals" - the average of the normals of the two segments that share that vertex. Once you have vertex normals for all your initial verteces, simply add each vertex''s normal to its position to create the new path. I can''t guarantee that this will work, but it sounds reasonable.

Share this post


Link to post
Share on other sites
It''s fairly trivial to generate the points a->j offline, if you have the points 1->10. The only reason I proposed the constraint satisfaction solution was that it seemed really cool... and allowed you to generate your path on the fly!

If you just want the points, then solve the following...

Each wall segment can be represented by two parametric equations:

(for the i th segment)


xi(t) = xi(0) + t(xi(1)-xi(0))
yi(t) = yi(0) + t(yi(1)-yi(0))


where:

xi(0): x value at start of line segment
xi(1): x value at end of line segment

and similarly for the y values.

Furthermore, the i th wall segment has gradient:


y(1)-y(0)
mi = ----------
x(1)-x(0)


Hence, the path segment you want to follow has the same gradient and is a constant distance r from the current line segment.

Assume that the parametric equations of this path segment have the same form as those for the wall (which they do) but are denoted by x''i and y''i. Thus, r is given by


r = sqrt( (xi(t)-x''i(t))2 + (yi(t)-y''i(t))2 )


You also have the equality

mi = m''i

and so the appropriate substituations relate x(0),x(1),y(0) & y(1) with x''(0),x''(1),y''(0) & y''(1).

you can solve this system of equations for the values of x''(0),x''(1),y''(0) & y''(1). You can then do the same for the next segment and THEN solve for the intersection of these two lines semgents!

See why I suggested that constraint based solution?!!!

In writing the psuedo-code for my wall following algorithm I have found a slightly tough nut to crack... it occurs when the gradient of the next line is less than that of the current line (ie, you have to travel a concave path). It''s not to do with the shape of the path, or the time... thats fine... it has to do with the distance to the point of intersection of the two wall segments... its different than if the wall shape is convex. I''ll solve it today or tomorrow hopefully and put up the code soon.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
I may not be understanding this all so is he just try to move the line segements?

Share this post


Link to post
Share on other sites
quote:
Original post by Puzzler183
I may not be understanding this all so is he just try to move the line segements?


Sort of. He wants an object to follow a path that runs parallel to the wall segments.

Timkin

Share this post


Link to post
Share on other sites
Well, here's the psuedocode for Timkin's wall following algorithm !!!

I've made a subtle change to my original idea which makes it code up slightly easier. The algorithm provides a circular path for convex corners and a sharp turn for concave corners. It should always stay a distance r from the wall... the only condition on this is the errors introduced by the linear interpolation function (LERP) which you can write yourself or get from online. If your frame rate is high enough, you should never notice this error. You'll need to provide your own frame rate estimation routine as well. I hope everything is self explanatory. If it's not, please let me know and I'll explain as best I can.

Known values (set all these to appropriate values)

x(0),x(1),y(0),y(1): endpoints for all line segments
x'(0),y'(0): starting coordinates of object
r: computed from known starting coordinates and equation of line.
V: speed of moving object



for i=1 to NumberOfLineSegments
{
FPS = GetCurrentFramesPerSecond()
Li = sqrt( (xi(1)-xi(0))2 + (yi(1)-yi(0))2 )
stotal = Li/V
ds = 1/(stotal*FPS)

if (mi < mi+1)
{
theta=atan(mi)
s = 0
while(theta!=atan(mi+1))
{

ri+1 = sqrt( (xi(1)-x_curr)2 + (yi(1)-y_curr)2 )
if (ri+1==r)
m = LERP(m,mi+1,ds)
else
m = mi


Vx = sqrt(V2/(1+m2))
Vy = sqrt(m2V2/(1+m2))
x_curr = x_curr+ds*Vx
y_curr = y_curr+ds*Vy
s = s + ds

theta = atan(m)
}
}
else
{
ri+1 = sqrt((xi(1)-x_curr)2 + (yi(1)-y_curr)2 )
phi = atan(mi+1)-atan(mi)
r' = r/cos(phi/2)
m = mi
while (ri+1!=r')
{
Vx = sqrt(V2/(1+m2))
Vy = sqrt(m2V2/(1+m2))
x_curr = x_curr+ds*Vx
y_curr = y_curr+ds*Vy
ri+1 = sqrt((xi(1)-x_curr)2 + (yi(1)-y_curr)2 )
}
}
}


This code has only been tested on paper. It should work on your computer!!! Good luck and let me know how it goes please.

Cheers,

Timkin

[edited by - Timkin on June 4, 2002 1:38:51 AM]

Share this post


Link to post
Share on other sites

  • Advertisement