CODEWITHSUNDEEP
algorithmpoisson
user6451264
user6451264

Reputation:

Implement poisson disk sampling in linear time

I’m trying to implement the noise generator (Poisson disk noise) demonstrated here and described here, but I don’t know how to make it run in linear time due to the requirement that a random active sample (the red dots in the example) be popped from the active sample queue. As far as I can tell, this step itself has linear complexity since the sample isn’t popped from the end or dequeued from the beginning of the queue, making the whole algorithm quadratic.

How do I make the noise generator truly linear in time? As far as I can tell, this requires a sequence that a random element can be removed from in constant time.

Upvotes: 0

Views: 392

Answers (1)

mcdowella
mcdowella

Reputation: 19621

As far as I can see, the only operations you need to perform on this queue are to select and remove a random element, and to add new elements. In particular, you don't need to preserve order.

To implement this I would use a class supporting a variable length array, such as std::vector or java.util.ArrayList. To add an element, just add one on the end with push_back() or add(). To remove a random element, pick a random element within the array, save it, copy the element at the end of the array over element that you have just saved, and then reduce the size of the array by one. Something like

index = rng.nex()tInt(arr.size());

toReturn = arr.get(index);

arr.set(index, arr.get(arr.size() - 1));

arr.resize(arr.size() - 1);

return toReturn;

Upvotes: 0

Related Questions