Is there an algorithm for generating random samples in a dispersed distribution, as if they were actively repelling one another?

Question

I am attempting to create a script for generating randomly distributed samples with a dispersed distribution - as if they are actively repelling one another - such as with the example in the linked image.

Example of spatial point patterns

That image pertains to Ripley's K algorithm, which is useful for analysing the nature of an existing sample distribution - but I'm attempting to find an algorithm to actually generate points in a dispersed distribution, and I'm not having any luck.

I attempted to write my own algorithm for this purpose, but it's very ineffective and crudely put together. This algorithm just randomly picks points in space and checks whether said point is within N units of any existing sample, with N gradually reducing over time to avoid circumstances where the code would hang. At high amounts of samples, the distributions generated from this code are no better than random.

    for n in range(numSamples):
        tempIdealDistance = idealDistance #Units of distance we're attempting to separate each sample by
        newPosition = []
        searchingForLocation = True
        while searchingForLocation:
            #Looking for a location that doesn't overlap with any existing samples
            newPosition = [random.randint(lowBounds,highBounds),random.randint(lowBounds,highBounds),random.randint(lowBounds,highBounds)]
            withinRange = False
            for s in samples:
                #Iterate through the existing list of samples, looking for overlaps
                existingSamplePosition = np.array(s.GetPos())
                newSamplePosition = np.array(newPosition)
                if np.linalg.norm(existingSamplePosition - newSamplePosition) < tempIdealDistance:
                    #If we overlap with any existing samples, this is not a valid position
                    withinRange = True
                    break
            if withinRange == False:
                #If no samples are within range of our new one, it fits the regular distribution
                searchingForLocation = False
                samp = Point(newPosition[0],newPosition[1],newPosition[2])
                samp.SetRatio(GetRatio(TiSrB,TiSrA,samp.GetPos(),position),randomNoise)
                samples.append(samp)
            else:
                #To avoid infinite loops, we gradually decrease the search distance
                tempIdealDistance = tempIdealDistance - 1

Could anyone help me find a more appropriate algorithm to what I'm looking for?

Bridson’s algorithm maybe? Check out bost.ocks.org/mike/algorithms — Samwise
– Samwise, Commented Jun 23, 2023 at 4:04
This seems very close to what I need, but it seems like it takes a pre-determined search radius and fills an entire space with an increasing number of samples until there's no space left. I actually need the opposite of that - something that takes a pre-determined number of samples and places them throughout the space with the radius being calculated to compensate for how much space there is between them. Thank you though, I'll see if I can adjust the algorithm to get what I'm looking for. — CookieSteve
– CookieSteve, Commented Jun 23, 2023 at 5:36
Divide the total area by the number of samples and you get the average area per sample. Area of a circle is pi*r^2. — Samwise
– Samwise, Commented Jun 23, 2023 at 5:57

Severin Pappadeux · Accepted Answer · 2023-06-23 12:50:59Z

2

I could think about couple of options:

Poisson disc sampling. See https://www.jasondavies.com/poisson-disc/ for details. Basically samples would be separated by minimum distance.
Quasi-random (e.g. Sobol) sequences. There is a theorem for Sobol sequences which states that minimum distance would be sqrt(d)/2 1/N, where d is problem dimensions, and N is number of samples. See https://en.wikipedia.org/wiki/Sobol_sequence for details

answered Jun 23, 2023 at 12:50

Severin Pappadeux

20.4k4 gold badges45 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

CookieSteve Over a year ago

The Sobol sequences didn't really seem like what I was after, since it seems like the distribution of samples is the same every time and doesn't really have a distribution with a roughly even distance between each sample (some samples are very clumped together while others are spaced far apart). The Poisson Disc sampling on the other hand is exactly what I was after. Thank you!

Collectives™ on Stack Overflow

Is there an algorithm for generating random samples in a dispersed distribution, as if they were actively repelling one another?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related