Jump to content

  • Log In with Google      Sign In   
  • Create Account


Generate random perpendicular unit vector


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 Krzysztof Narkowicz   Members   -  Reputation: 1048

Like
0Likes
Like

Posted 26 January 2013 - 04:33 PM

Hi,

 

I have a unit vector v1 and would like to generate a random perpendicular unit vector v2 with uniform or close to uniform distribution.

 

Potential solution is to generate a random unit vector and cross it with v1 to get v2. Now this has two issues - non uniform distribution and for some inputs it generates degenerate vectors, so it requires running in a loop until a valid vector is returned.

 

My current solution is to generate a random angle. Build a rotation matrix M using v1 and two perpendicular vectors. Those vectors are generated by crossing v1 with axis of it's smallest component and by crossing result with v1. Finally transform vector [ cos(randomAngle), sin(randomAngle), 0 ] using rotation matrix M.

 

It works, but I feel that I'm doing excessive amount of calculations and there is a much simpler way to solve it.


blog | twitter | "Don't have any friends? Still a virgin? Programming is for you!"


Sponsor:

#2 C0lumbo   Crossbones+   -  Reputation: 2093

Like
0Likes
Like

Posted 26 January 2013 - 04:43 PM

My current solution is to generate a random angle. Build a rotation matrix M using v1 and two perpendicular vectors. Those vectors are generated by crossing v1 with axis of it's smallest component and by crossing result with v1. Finally transform vector [ cos(randomAngle), sin(randomAngle), 0 ] using rotation matrix M.

If you call your two perpendicular vectors v2 and v3, isn't it equivalent to just do: (v2 * cos(randomAngle)) + (v3 * sin(randomAngle)); ?

Not much less work I suppose, but a little quicker.

Edited by C0lumbo, 27 January 2013 - 02:05 AM.


#3 swiftcoder   Senior Moderators   -  Reputation: 9506

Like
0Likes
Like

Posted 26 January 2013 - 05:09 PM

There is a fair amount of discussion on the topic in an older thread.


Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#4 EWClay   Members   -  Reputation: 655

Like
0Likes
Like

Posted 27 January 2013 - 05:59 AM

You can avoid sin and cos by generating two random numbers x and y in the range -1 to +1, rejecting if the two are outside the unit circle or both zero, then normalising and multiplying by the perpendicular vectors.

#5 Bacterius   Crossbones+   -  Reputation: 7969

Like
0Likes
Like

Posted 27 January 2013 - 06:07 AM

You can avoid sin and cos by generating two random numbers x and y in the range -1 to +1, rejecting if the two are outside the unit circle or both zero, then normalising and multiplying by the perpendicular vectors.

 

Rejection sampling will cause you to reject (4 - pi) / 4 = 21% of samples taken, and will thus introduce branching in the computation (as well as an extra normalization). It is probably more efficient to just use sin and cos, depending on your platform.


The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#6 Kepakiano   Members   -  Reputation: 138

Like
1Likes
Like

Posted 27 January 2013 - 08:17 AM

This is what I would do:
http://pastebin.com/fr4aU0cw (needs C++11)

1. Generate a random unit vector
2. Make it orthogonal to your given vector by using the Gram-Schmidt Process (http://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process)

Edit: The snippet does not check, whether v and random u are linearly independent.

Edited by Kepakiano, 27 January 2013 - 08:22 AM.


#7 EWClay   Members   -  Reputation: 655

Like
0Likes
Like

Posted 27 January 2013 - 09:19 AM

You can avoid sin and cos by generating two random numbers x and y in the range -1 to +1, rejecting if the two are outside the unit circle or both zero, then normalising and multiplying by the perpendicular vectors.

 
Rejection sampling will cause you to reject (4 - pi) / 4 = 21% of samples taken, and will thus introduce branching in the computation (as well as an extra normalization). It is probably more efficient to just use sin and cos, depending on your platform.
No doubt it could be made branchless, if running in a loop. If not in a loop, it's unlikely to be a hotspot.

Really, I was just pointing out that it can be done without trig functions. The OP never mentioned a performance issue.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS