Sign in to follow this  
Magnusart

Connecting a new node to a graph and decide if neighbours are to the left or right.

Recommended Posts

Hello Let me first say that this is my first post. So if I'm in the wrong forum please direct me to the right one. I have a system of interconnected nodes. Each node has a left/right property that points to the next node. The nodes represent a path around an obstacle in a 3D world. Whenever I want to walk around an obstacle I get the two closest unblocked (by the obstacle) nodes. I now need to know if they are to the right or to the left of my start node. This is where I get my problem. If I have a circular path with nodes like this NODE3-R--><--L-NODE1-R--><--L-NODE2-R--><--L-NODE3-R--><--L-NODE1 I then want to the node STARTNODE in the middle NODE3-R--><--L-NODE1-R--><--L-NODE2-R--><--L-STARTNODE-R--><--L-NODE3-R--><--L-NODE1 To know which node is to the right or left I use the crossproduct between the vector(x,y,z=0) between the positions of STARTNODE->NODE2 x NODE2->NODE3. If it is on the right side i get a positive z value and a negative value (normal) otherwise. Base on this I can flip my right and left pointers in STARTNODE if my first guess is wrong. This is true for all situations except where I have a concave shape. I have an illustration for this: My question is if there is a better way of doing this? My best idea is to somehow test to see if the start position is within this circular path and then invert my test for the z-direction. If that is a good solution, how would I go about to do that in an efficient way? If this is unclear, please state where I am unclear and I will elaborate. Thanks /Magnus

Share this post


Link to post
Share on other sites
As you've noticed, "right side/left side" isn't a perfect isomorphism to what you really want to represent, "clockwise around obstacle / counterclockwise around obstacle". I suggest that you store that instead.

Share this post


Link to post
Share on other sites
Thank you for your input, I really appreciate it.

I think you are probably on to something here. Or rather: I think I am beginning to see what you mean.

I have problems with my code right now since depending on what side of my obstacle I am standing I get different results. On one side it's fine but on the other side things get inverted and my path gets reversed (and thus the travel cost becomes infinity/a dead end). This messes up my algorithm, described more in detail here: http://www.magnusart.com/temp/path_finder.svg it has been altered a bit since this picture but that is my basic implementation.

Off the top of my head, I'm not sure how to apply clockwise and counter clockwise to my problem. Since my nodes are built with right and left pointers. But maybe I just need to think a little more about it. Maybe even make another picture. That really seems to help my reasoning.

I will mull over this and get back to this thread. Thank you, I think you pointed me in the right direction.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this