Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to generate uniformly random points on n-spheres and in n-balls

extremelearning.com.au

Post reply on HN
Print view View original

41–50 of 87 posts

Re: How to generate uniformly random points on n-spheres and in n-balls

#41

Post by pugworthy »

2-ball (disk) distribution is kind of interesting in gaming when simulating gun projectile hit locations.

If the circle represents the area in which a simulated projectile will hit, you probably don't want a truly random distribution of points but instead have a bias towards the middle of the circle. A real gun shot multiple times at a fixed target will probably (assuming perfect aim but some variation on every shot) have more shots hit the middle of the pattern than the edges.

Some early Valve shot code actually had a purely random distribution, but at some point an alternate version got written and shared at https://developer.valvesoftware.com/wiki/CShotManipulator

Ironically the biased version is based on a pretty simple method that in fact people sometimes get wrong when they want a truly random point distribution in a circle. Just doing a random radius and theta will lead to a biased distribution. Wolfram Mathworld has a good writeup on it at https://mathworld.wolfram.com/DiskPointPicking.html

Re: How to generate uniformly random points on n-spheres and in n-balls

#42

Post by xanderlewis »

pugworthy wrote: post #41

2-ball (disk) distribution is kind of interesting in gaming when simulating gun projectile hit locations. If the circle represents the area in which a simulated projectile will hit, you probably don't want a truly random distribution of points but instead have a bias towards the middle of the circle. A real gun shot multiple times at a fixed target will probably (assuming perfect aim but some variation on every shot)…

> truly random distribution

> purely random distribution

Nitpick: you don’t mean random; you mean uniform.

Re: How to generate uniformly random points on n-spheres and in n-balls

#43

Post by travisjungroth »

wodenokoto wrote: post #9
JadoJodo wrote: post #2

I'm definitely not at all qualified to talk about this, but... aren't "uniform" and "random" antonyms?

No. I would go so far as to say, if it’s not uniformly random, it isn’t random. My reasoning is, if you are counting cards in a game, you are giving yourself an advantage. But what really happens is that from your point of view cards will be drawn less and less uniformly randomly. Or put in another way, if you know the distribution is normal, you can bet on the the result being near the center and come out on top, bu…

> Or put in another way, if you know the distribution is normal, you can bet on the the result being near the center and come out on top, but if it’s uniformly random distribution all hopes are out.

That’s just because the payout distribution and real distribution are different, and there’s a place the payout is at a loss.

If you bet on a uniform distribution of 2 through 12 that payed out according to a normal distribution, you’d make a killing betting on 2 or 12 (the “outliers”). If you roll 2d6 (normalish) and get paid according to a uniform distribution, you’ll make a killing betting on 7.

Re: How to generate uniformly random points on n-spheres and in n-balls

#44

Post by richrichie »

hinkley wrote: post #19
olliej wrote: post #7

I was always surprised at how easily you get biased sampling when generating random points despite all input - something I often saw students do was essentially normalize({2 rand() - 1, 2 rand() - 1, 2 rand() - 1}) or variations of that (where rand() is "good" not the literal rand(3)), and there are numerous other ways that are more subtly wrong. IIRC the nominally correct way for a sphere specifically is something l…

I used to think “normal distributions are everywhere” but the more math and science I watch on YouTube the more the central limit theorem pops up. It’s the CLT that’s everywhere, it just brings normal distribution as it’s +1.

Indeed. The fundamental insight behind CLT i.e. sample average is normally distributed even when population distribution is not normal is intuitive, yet the the theorem is magical.

Re: How to generate uniformly random points on n-spheres and in n-balls

#45

Post by ianferrel »

contravariant wrote: post #38
bee_rider wrote: post #18

Earlier quoted context omitted.

The rejection method smells pretty good to me, in the sense that it should be pretty obvious to anybody with, like, middle school level math I think (right?). It might fail for higher dimensions, but lots of programs only run on a 3D sphere of a planet, haha!

Fail is an understatement, the ratio between the two volumes is basically (n/2)!(4/pi)^(n/2). Which is also the expected number of tries you'll need. The time doesn't merely grow exponentially it grows faster than exponential. I don't actually know of any useful algorithms with worse asymptomatic behaviour.

Sure, but for the most-used real-world geometry, n = 2 or 3. So how fast it grows really doesn't matter.

Most maps are 2-dimensional and this is fine.

Re: How to generate uniformly random points on n-spheres and in n-balls

#46

Post by zeroonetwothree »

contravariant wrote: post #38
bee_rider wrote: post #18

Earlier quoted context omitted.

The rejection method smells pretty good to me, in the sense that it should be pretty obvious to anybody with, like, middle school level math I think (right?). It might fail for higher dimensions, but lots of programs only run on a 3D sphere of a planet, haha!

Fail is an understatement, the ratio between the two volumes is basically (n/2)!(4/pi)^(n/2). Which is also the expected number of tries you'll need. The time doesn't merely grow exponentially it grows faster than exponential. I don't actually know of any useful algorithms with worse asymptomatic behaviour.

I doubt that the number of dimensions is the parameter that grows. It’s going to be constant for 99.99% of cases.

Re: How to generate uniformly random points on n-spheres and in n-balls

#47

Post by ls612 »

ianferrel wrote: post #45
contravariant wrote: post #38

Earlier quoted context omitted.

Fail is an understatement, the ratio between the two volumes is basically (n/2)!(4/pi)^(n/2). Which is also the expected number of tries you'll need. The time doesn't merely grow exponentially it grows faster than exponential. I don't actually know of any useful algorithms with worse asymptomatic behaviour.

Sure, but for the most-used real-world geometry, n = 2 or 3. So how fast it grows really doesn't matter. Most maps are 2-dimensional and this is fine.

Maybe n=4 if you have a timestamp as another dimension.

Re: How to generate uniformly random points on n-spheres and in n-balls

#48

Post by nick7376182 »

chpatrick wrote: post #28
frankfrank13 wrote: post #6

I actually needed this at work once! We needed to fuzz peoples address in a mapped view for analytics, without revealing PII. It ended up never being shipped, but we needed to fuzz geographic data and the thinking was like: 1. Truncate your lat longs to some arbitrary decimal place (this is very very stupid, you end up with grid lines [1]) 2. The above method ^^ but everyone tries basically doing like random angle +…

What if someone lives in a really remote location so they're the only ones in the heat map cell?

Assign everyone a random offset, that doesn't change, that is large enough to obscure the address with some reasonable radius but small enough to not drastically skew the heat map at a lower zoom level

Re: How to generate uniformly random points on n-spheres and in n-balls

#49

Post by eli_gottlieb »

xanderlewis wrote: post #34
dmd wrote: post #31

As an RA, before starting grad school, I hacked together some code to choose a random point on a sphere, for some psychophysics experiment I was doing. Fortunately, I never used it for anything, because I made the classic naive mistake of simply choosing a random theta in 0,2pi and phi in -pi,pi, which ends up with points biased towards the poles. Somehow *12 years later* my subconscious flagged it up and I woke up i…

> simply choosing a random theta in 0,2pi and phi in -pi,pi, which ends up with points biased towards the poles. Am I right in thinking that it’s because circles of constant theta on the sphere contain the same ‘expected’ number of points (since phi is uniformly distributed), and these circles get smaller (and in the limit, shrink to a point) as one travels towards the poles — hence, higher density of points…? …makes…

> whilst the mapping (theta, phi) —> (x, y, z) is continuous, it isn’t uniformly so… or something like that.

The term is "measure preserving". The mapping is continuous but it doesn't preserve the length of intervals projected through it.

Re: How to generate uniformly random points on n-spheres and in n-balls

#50

Post by hinkley »

richrichie wrote: post #44
hinkley wrote: post #19

Earlier quoted context omitted.

I used to think “normal distributions are everywhere” but the more math and science I watch on YouTube the more the central limit theorem pops up. It’s the CLT that’s everywhere, it just brings normal distribution as it’s +1.

Indeed. The fundamental insight behind CLT i.e. sample average is normally distributed even when population distribution is not normal is intuitive, yet the the theorem is magical.

When you have more than one variable, the outcomes get clumpy.
Post reply on HN