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

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

## 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 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 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.

• 10
• 16
• 9
• 13
• 41