• ### Popular Now

• 9
• 9
• 11
• 12
• 9

#### Archived

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

# tricki path problem

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

## 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 on other sites
It''s not too hard, but not a dumb-ass question at all.

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

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 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 on other sites

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 on other sites
Timkim,

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

##### 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 on other sites
that would be very cool thank you very much

##### 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 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 segmentxi(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