Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #144448 > unrolled thread

Random direction using space partitioning?

Back to article view | Back to comp.lang.c

Contents

  Random direction using space partitioning? luser droog <luser.droog@gmail.com> - 2019-06-04 19:35 -0700
    Re: Random direction using space partitioning? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-06-05 04:25 +0100
      Re: Random direction using space partitioning? Clifford Heath <no.spam@please.net> - 2019-06-05 13:30 +1000
    Re: Random direction using space partitioning? John Forkosh <forkosh@panix.com> - 2019-06-05 04:36 +0000
      Re: Random direction using space partitioning? Richard Damon <Richard@Damon-Family.org> - 2019-06-05 07:04 -0400
        Re: Random direction using space partitioning? "F. Russell" <frussell@random.info> - 2019-06-05 12:55 +0000

#144448 — Random direction using space partitioning?

I had an idea about an algorithm for generating random
unit vectors. Instead of mapping 2 or 3 random numbers
to coordinates and then constraints and whatnot, ...
what I we set up a 1D->3D mapping straight from a single
number? In essence, the idea is to do something like a
Hilbert Space Curve that does the same form of mapping,
https://en.wikipedia.org/wiki/Hilbert_curve, but using
a curve that is by definition constrained to the surface
we want.

So, not to try to *do* it. My first thought is to sum
up the six natural vectors along the three axes,

   ( bit_0 ? (1 0 0) : (-1 0 0) )
 + ( bit_1 ? (0 1 0) : (0 -1 0) )
 + ( bit_2 ? (0 0 1) : (0 0 -1) )
 + ( bit_3 ? ...

... but then what? Some kind of weird, weighted things
that I can't quite think of? This leads me to conclude
that addition is not the right choice for the outer 
operator.

So starting over, suppose we start with one vector and
then compose rotations with smaller and smaller ranges
of movement?

   ( bit_0 ? (1 0 0) : (-1 0 0) )
 * ( rotz( -90 + bit_1 * 180 ) )
 * ( rotx( -90 + bit_2 * 180 ) )
 * ( roty( -45 + bit_3 * 90 ) )
 * ( rotz( -45 + bit_4 * 90 ) )
 * ...

That seems better, but maybe by the second rotation we
already don't want to be moving 180 degrees. And I still
don't know how to extend it deeper into the space.

So for a third start, what if at each step we take two bits,
the first determines whether to do the rotation or not, and
the second determines the direction?

   ( bit_0 ? (1 0 0) : (-1 0 0) )
 * ( bit_1 ? rotz( -90 + bit_2 * 180 ) : identity )
 * ( bit_3 ? rotx( -90 + bit_4 * 180 ) : identity )

And that's as far as I got. Pretty rough, I know. 
But space curves are cool, so it's gotta work right?

[toc] | [next] | [standalone]

#144451

luser droog <luser.droog@gmail.com> writes:

> I had an idea about an algorithm for generating random
> unit vectors. Instead of mapping 2 or 3 random numbers
> to coordinates and then constraints and whatnot, ...
> what I we set up a 1D->3D mapping straight from a single
> number? In essence, the idea is to do something like a
> Hilbert Space Curve that does the same form of mapping,
> https://en.wikipedia.org/wiki/Hilbert_curve, but using
> a curve that is by definition constrained to the surface
> we want.

I feel sure that can work, but I am not si sure that it will be at all
easy and the problem is not really intrinsically hard.

Mind you, as you say,

> space [filling] curves are cool

so I'd like to see such a solution.

However, I'm having trouble coming up with a space filling curve that is
(a) constrained to the unit sphere, (b) uniformly dense on it and (c)
has a form that allows a point to be readily computed.  (Other than
mapping a normal one onto an equal area projection of the sphere.)

I have a feeling this will be an entertaining but futile avenue.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#144452

On 5/6/19 1:25 pm, Ben Bacarisse wrote:
> luser droog <luser.droog@gmail.com> writes:
> 
>> I had an idea about an algorithm for generating random
>> unit vectors. Instead of mapping 2 or 3 random numbers
>> to coordinates and then constraints and whatnot, ...
>> what I we set up a 1D->3D mapping straight from a single
>> number? In essence, the idea is to do something like a
>> Hilbert Space Curve that does the same form of mapping,
>> https://en.wikipedia.org/wiki/Hilbert_curve, but using
>> a curve that is by definition constrained to the surface
>> we want.
> 
> I feel sure that can work, but I am not si sure that it will be at all
> easy and the problem is not really intrinsically hard.
> 
> Mind you, as you say,
> 
>> space [filling] curves are cool
> 
> so I'd like to see such a solution.
> 
> However, I'm having trouble coming up with a space filling curve that is
> (a) constrained to the unit sphere, (b) uniformly dense on it and (c)
> has a form that allows a point to be readily computed.  (Other than
> mapping a normal one onto an equal area projection of the sphere.)
> 
> I have a feeling this will be an entertaining but futile avenue.
> 

Interesting idea here, but I don't know how to follow it up:
<https://en.wikipedia.org/wiki/Space-filling_curve#Kleinian_groups>

Clifford Heath.

[toc] | [prev] | [next] | [standalone]

#144457

luser droog <luser.droog@gmail.com> wrote:
> I had an idea about an algorithm for generating random
> unit vectors. Instead of mapping 2 or 3 random numbers
> to coordinates and then constraints and whatnot, ...
> what I we set up a 1D->3D mapping straight from a single
> number? In essence, the idea is to do something like a
> Hilbert Space Curve that does the same form of mapping,
> https://en.wikipedia.org/wiki/Hilbert_curve, but using
> a curve that is by definition constrained to the surface
> we want.
> 
> So, not to try to *do* it. My first thought is to sum
> up the six natural vectors along the three axes,
> 
>   ( bit_0 ? (1 0 0) : (-1 0 0) )
> + ( bit_1 ? (0 1 0) : (0 -1 0) )
> + ( bit_2 ? (0 0 1) : (0 0 -1) )
> + ( bit_3 ? ...
> 
> ... but then what? Some kind of weird, weighted things
> that I can't quite think of? This leads me to conclude
> that addition is not the right choice for the outer 
> operator.
> 
> So starting over, suppose we start with one vector and
> then compose rotations with smaller and smaller ranges
> of movement?
> 
>   ( bit_0 ? (1 0 0) : (-1 0 0) )
> * ( rotz( -90 + bit_1 * 180 ) )
> * ( rotx( -90 + bit_2 * 180 ) )
> * ( roty( -45 + bit_3 * 90 ) )
> * ( rotz( -45 + bit_4 * 90 ) )
> * ...
> 
> That seems better, but maybe by the second rotation we
> already don't want to be moving 180 degrees. And I still
> don't know how to extend it deeper into the space.
> 
> So for a third start, what if at each step we take two bits,
> the first determines whether to do the rotation or not, and
> the second determines the direction?
> 
>   ( bit_0 ? (1 0 0) : (-1 0 0) )
> * ( bit_1 ? rotz( -90 + bit_2 * 180 ) : identity )
> * ( bit_3 ? rotx( -90 + bit_4 * 180 ) : identity )
> 
> And that's as far as I got. Pretty rough, I know. 
> But space curves are cool, so it's gotta work right?

The idea that had occurred to me was as follows...
Place a sphere of any radius r (which can just be 1) at the origin.
Choose any great circle on that sphere, say the one in the xy-plane.
Its circumference is 2pi*r, so choose a random number c, 0<=c<2pi*r.
From any point on the chosen great circle, say x=r,y=0, move in
either direction (say positive-theta in the usual polar coords sense)
a distance c along the circumference. So that pretty clearly selects
a random point that solves the 2d problem.
   For 3d I'm not 100% sure about the following step. At the point
you selected above, construct the great circle that passes through
it and that's in a plane perpendicular to your original plane.
And now just do that random 0<=c<2pi*r thing again.
-- 
John Forkosh  ( mailto:  j@f.com  where j=john and f=forkosh )

[toc] | [prev] | [next] | [standalone]

#144468

On 6/5/19 12:36 AM, John Forkosh wrote:
> luser droog <luser.droog@gmail.com> wrote:
>> I had an idea about an algorithm for generating random
>> unit vectors. Instead of mapping 2 or 3 random numbers
>> to coordinates and then constraints and whatnot, ...
>> what I we set up a 1D->3D mapping straight from a single
>> number? In essence, the idea is to do something like a
>> Hilbert Space Curve that does the same form of mapping,
>> https://en.wikipedia.org/wiki/Hilbert_curve, but using
>> a curve that is by definition constrained to the surface
>> we want.
>>
>> So, not to try to *do* it. My first thought is to sum
>> up the six natural vectors along the three axes,
>>
>>   ( bit_0 ? (1 0 0) : (-1 0 0) )
>> + ( bit_1 ? (0 1 0) : (0 -1 0) )
>> + ( bit_2 ? (0 0 1) : (0 0 -1) )
>> + ( bit_3 ? ...
>>
>> ... but then what? Some kind of weird, weighted things
>> that I can't quite think of? This leads me to conclude
>> that addition is not the right choice for the outer 
>> operator.
>>
>> So starting over, suppose we start with one vector and
>> then compose rotations with smaller and smaller ranges
>> of movement?
>>
>>   ( bit_0 ? (1 0 0) : (-1 0 0) )
>> * ( rotz( -90 + bit_1 * 180 ) )
>> * ( rotx( -90 + bit_2 * 180 ) )
>> * ( roty( -45 + bit_3 * 90 ) )
>> * ( rotz( -45 + bit_4 * 90 ) )
>> * ...
>>
>> That seems better, but maybe by the second rotation we
>> already don't want to be moving 180 degrees. And I still
>> don't know how to extend it deeper into the space.
>>
>> So for a third start, what if at each step we take two bits,
>> the first determines whether to do the rotation or not, and
>> the second determines the direction?
>>
>>   ( bit_0 ? (1 0 0) : (-1 0 0) )
>> * ( bit_1 ? rotz( -90 + bit_2 * 180 ) : identity )
>> * ( bit_3 ? rotx( -90 + bit_4 * 180 ) : identity )
>>
>> And that's as far as I got. Pretty rough, I know. 
>> But space curves are cool, so it's gotta work right?
> 
> The idea that had occurred to me was as follows...
> Place a sphere of any radius r (which can just be 1) at the origin.
> Choose any great circle on that sphere, say the one in the xy-plane.
> Its circumference is 2pi*r, so choose a random number c, 0<=c<2pi*r.
> From any point on the chosen great circle, say x=r,y=0, move in
> either direction (say positive-theta in the usual polar coords sense)
> a distance c along the circumference. So that pretty clearly selects
> a random point that solves the 2d problem.
>    For 3d I'm not 100% sure about the following step. At the point
> you selected above, construct the great circle that passes through
> it and that's in a plane perpendicular to your original plane.
> And now just do that random 0<=c<2pi*r thing again.
> 

Although we are getting points in 3-space to represent a 'random
direction' they are constrained to be on the surface of the unit sphere,
so we really only have 2 degrees of freedom, so we really only need two
random numbers (which is why we can express the vector with just two
parameters in polar space, with the defined length of 1).

Yes, there are ways to convert a 1 dimensional random number into a two
dimenension pair, just as we can show that the number of points on a
line can be directly mapped to the number of points on a plane, but if
you want to maintain uniformness, you need to be very careful how you do
the transform, especially since the space we are going to is curved.

My guess is that most methods that achieve this will be somehow
equivalent to mapping a line to a 2d flat plane, and then mapping that
plane to the sphere with an equal area transformation.

[toc] | [prev] | [next] | [standalone]

#144470

On Wed, 05 Jun 2019 07:04:56 -0400, Richard Damon vomited this verbiage
that I considered to be worthy of my attention for one of a variety of
possible reasons:

> 
>  but if
> you want to maintain uniformness, you need to be very careful how you do
> the transform
>

That's what the Jacobian is for.

The determinant of the Jacobian of the spherical transform will define
the PDF of the desired distribution.  Then the Inverse CDF Method is used
to relate a uniform distribution to the that PDF.

Now see if you can solve this one:

Instead of uniformly sampling points on a spherical surface, uniformly
sample points inside the spherical ball centered on the origin.  In this
case we have 3 degrees of freedom and 2 areas of clustering.

The Jacobian determinant is R^2 * sin(phi)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web