Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualBacterius

Posted 26 September 2012 - 07:31 AM

A Poisson disc would be perfect for your needs, as it specifically focuses on keeping a minimal distance between sample points. You'll still need to check intersection with the hull in case a point happens to fall outside it by chance.

Otherwise, if Poisson disc does not apply in your case for some reason or you are just looking for a more ghetto (or intuitive, depending on your perspective) solution, read on:

If you do not need perfect correctness (i.e. some points may be closer together and others may be further away, or in other words, the variance of the distance should be nonzero but not too large), then another probabilistic way to do it is to generate a regular point lattice with distance equal to your mean minimum distance, and displace each point in every dimension using a Gaussian distribution with your required variance? Like this:

Let be the mean distance between each point, and be the required variance.
1. Generate a regular lattice spaced by in every dimension.
2. For each point in the lattice:
- choose a random angle (or two, if you are in three dimensions) to displace the point in some direction in space
- generate a random variable following a Gaussian distribution* with your variance but with mean 0
- displace the point by units in the direction determined by the angle chosen above
- if the point falls outside or too close to your convex hull, try again until it works (this is biased, but I think it's acceptable given that considering the shape of the hull would likely be intractable)

* see Box-Muller transform to get that from uniform variables


Some examples rendered with a throwaway program, with a mean and a progressively higher variance (from 0 to 0.0003) - remember to square root the variance if you need the standard deviation:

Posted Image

Obviously, as variance increases, the distribution tends to perfect uniformity (assuming an infinite lattice - if it is finite, the algorithm will degenerate).

The 3D situation is exactly the same, your lattice is now 3D and you are displacing the points according to two angles (spherical coordinates i.e. azimuth and elevation instead of just rotation in 2D), but you still only need one Gaussian distribution sample.

#4Bacterius

Posted 26 September 2012 - 07:30 AM

A Poisson disc would be perfect for your needs, as it specifically focuses on keeping a minimal distance between sample points. You'll still need to check intersection with the hull in case a point happens to fall outside it by chance.

Otherwise, if Poisson disc does not apply in your case for some reason or you are just looking for a more ghetto (or intuitive, depending on your perspective) solution, read on:

If you do not need perfect correctness (i.e. some points may be closer together and others may be further away, or in other words, the variance of the distance should be nonzero but not too large), then another probabilistic way to do it is to generate a regular point lattice with distance equal to your mean minimum distance, and displace each point in every dimension using a Gaussian distribution with your required variance? Like this:

Let be the mean distance between each point, and be the required variance.
1. Generate a regular lattice spaced by in every dimension.
2. For each point in the lattice:
- choose a random angle (or two, if you are in three dimensions) to displace the point in some direction in space
- generate a random variable following a Gaussian distribution* with your variance but with mean 0
- scale to your required variance as (not mean, since your points are already distance apart)
- displace the point by units in the direction determined by the angle chosen above
- if the point falls outside or too close to your convex hull, try again until it works (this is biased, but I think it's acceptable given that considering the shape of the hull would likely be intractable)

* see Box-Muller transform to get that from uniform variables


Some examples rendered with a throwaway program, with a mean and a progressively higher variance (from 0 to 0.0003) - remember to square root the variance if you need the standard deviation:

Posted Image

Obviously, as variance increases, the distribution tends to perfect uniformity (assuming an infinite lattice - if it is finite, the algorithm will degenerate).

The 3D situation is exactly the same, your lattice is now 3D and you are displacing the points according to two angles (spherical coordinates i.e. azimuth and elevation instead of just rotation in 2D), but you still only need one Gaussian distribution sample.

#3Bacterius

Posted 26 September 2012 - 07:30 AM

A Poisson disc would be perfect for your needs, as it specifically focuses on keeping a minimal distance between sample points. You'll still need to check intersection with the hull in case a point happens to fall outside it by chance.

Otherwise, if Poisson disc does not apply in your case for some reason or you are just looking for a more ghetto (or intuitive, depending how you look at it) solution, read on:

If you do not need perfect correctness (i.e. some points may be closer together and others may be further away, or in other words, the variance of the distance should be nonzero but not too large), then another probabilistic way to do it is to generate a regular point lattice with distance equal to your mean minimum distance, and displace each point in every dimension using a Gaussian distribution with your required variance? Like this:

Let be the mean distance between each point, and be the required variance.
1. Generate a regular lattice spaced by in every dimension.
2. For each point in the lattice:
- choose a random angle (or two, if you are in three dimensions) to displace the point in some direction in space
- generate a random variable following a Gaussian distribution* with your variance but with mean 0
- scale to your required variance as (not mean, since your points are already distance apart)
- displace the point by units in the direction determined by the angle chosen above
- if the point falls outside or too close to your convex hull, try again until it works (this is biased, but I think it's acceptable given that considering the shape of the hull would likely be intractable)

* see Box-Muller transform to get that from uniform variables


Some examples rendered with a throwaway program, with a mean and a progressively higher variance (from 0 to 0.0003) - remember to square root the variance if you need the standard deviation:

Posted Image

Obviously, as variance increases, the distribution tends to perfect uniformity (assuming an infinite lattice - if it is finite, the algorithm will degenerate).

The 3D situation is exactly the same, your lattice is now 3D and you are displacing the points according to two angles (spherical coordinates i.e. azimuth and elevation instead of just rotation in 2D), but you still only need one Gaussian distribution sample.

#2Bacterius

Posted 26 September 2012 - 07:17 AM

A Poisson disc would be perfect for your needs, as it specifically focuses on keeping a minimal distance between sample points. You'll still need to check intersection with the hull in case a point happens to fall outside it by chance.

If you do not need perfect correctness (i.e. some points may be closer together and others may be further away, or in other words, the variance of the distance should be nonzero but not too large), then another probabilistic way to do it is to generate a regular point lattice with distance equal to your mean minimum distance, and displace each point in every dimension using a Gaussian distribution with your required variance? Like this:

Let be the mean distance between each point, and be the required variance.
1. Generate a regular lattice spaced by in every dimension.
2. For each point in the lattice:
- choose a random angle (or two, if you are in three dimensions) to displace the point in some direction in space
- generate a random variable following a Gaussian distribution* with your variance but with mean 0
- scale to your required variance as (not mean, since your points are already distance apart)
- displace the point by units in the direction determined by the angle chosen above
- if the point falls outside or too close to your convex hull, try again until it works (this is biased, but I think it's acceptable given that considering the shape of the hull would likely be intractable)

* see Box-Muller transform to get that from uniform variables


Some examples rendered with a throwaway program, with a mean and a progressively higher variance (from 0 to 0.0003) - remember to square root the variance if you need the standard deviation:

Posted Image

Obviously, as variance increases, the distribution tends to perfect uniformity (assuming an infinite lattice - if it is finite, the algorithm will degenerate).

The 3D situation is exactly the same, your lattice is now 3D and you are displacing the points according to two angles (spherical coordinates i.e. azimuth and elevation instead of just rotation in 2D), but you still only need one Gaussian distribution sample.

#1Bacterius

Posted 26 September 2012 - 07:14 AM

If you do not need perfect correctness (i.e. some points may be closer together and others may be further away, or in other words, the variance of the distance should be nonzero but not too large), then a probabilistic way to do it is to generate a regular point lattice with distance equal to your mean minimum distance, and displace each point in every dimension using a Gaussian distribution with your required variance? Like this:

Let be the mean distance between each point, and be the required variance.
1. Generate a regular lattice spaced by in every dimension.
2. For each point in the lattice:
- choose a random angle (or two, if you are in three dimensions) to displace the point in some direction in space
- generate a random variable following a Gaussian distribution* with your variance but with mean 0
- scale to your required variance as (not mean, since your points are already distance apart)
- displace the point by units in the direction determined by the angle chosen above
- if the point falls outside or too close to your convex hull, try again until it works (this is biased, but I think it's acceptable given that considering the shape of the hull would likely be intractable)

* see Box-Muller transform to get that from uniform variables


Some examples rendered with a throwaway program, with a mean and a progressively higher variance (from 0 to 0.0003) - remember to square root the variance if you need the standard deviation:

Posted Image

Obviously, as variance increases, the distribution tends to perfect uniformity (assuming an infinite lattice - if it is finite, the algorithm will degenerate). In 3D, it's exactly the same, your lattice is now 3D and you are displacing the points according to two angles (azimuth and elevation instead of just rotation in 2D)), but you still only need one Gaussian distribution sample.

PARTNERS