# Object placement in O(1)

## Recommended Posts

Today I started implementing Poisson Disc generator, however halfway through the implementation I realized this was not what I was using 5 years ago. First off, while I can implement this with a min and max radius, it doesn't help me fill in the void (so to speak) if I should generate a wrappable array from this data.

So, this is what I need to know the name of:

2. It then creates a power-of-2 sized array

3. It fills the array with radius-values, distanced so that if you access the array at any position modulo the array size, you can use lequal to know if you can place your object.

An example row: [1, 2, 3, 2, 1, 2, 6, 2, 1, 2, ...] <-- if i remembered the specifics I wouldnt be asking

4. This is O(1) because an object can be try_placed with array(wrap(x), wrap(y)) < radius

Anyone know the name of this procedure? Any help would be appreciated.

Edited by Kaptein

##### Share on other sites

If you have a dense 2D array where the values are the distance from the closest object (0 where objects are located) additional data is needed to place another object or prove there's no room left in constant time.

With the simplifying assumption that all objects have the same radius, you could instead maintain a set of all eligible placement positions (not too close to already placed objects).

If stored as a set of empty spans, line by line, placing an object requires choosing a random line with some room left, a random span on that line, and a random point in the span, then accessing nearby lines (inside the object radius) and, in each, creating at most one new span, updating one or two, and removing a number of spans proportional to the object's radius.

This would degrade a little because of binary search over the empty spans of a line, but the number of spans is tightly limited.

Edited by LorenzoGatti

##### Share on other sites

This is for try-placing objects, so no searching is necessary. For each position (x, z) in the world, read a seamless pre-computed array of radius-values and compare lequal against radius of object you're trying to place. This was 5 years ago, but I don't remember the details unfortunately. I ended up finishing the poison-disc generator and now my objects are try-placed properly in O(1), and seamlessly wraps around on the arrays. One (singular) array can't be used with many objects of many sizes, though, but I'll live.

The bottom line here is that I can't use my poisson-disc array to place both big and small objects interchangeably. Instead I would have to create two arrays to support two object sizes, or one array where the one object affects placements of other objects, which is also unwanted.

The primary reason for having something like this is just being able to use the same array to place any kind of size object from a single array shared across all threads.

Edited by Kaptein

## Create an account

Register a new account

1. 1
2. 2
Rutin
20
3. 3
4. 4
frob
13
5. 5

• 9
• 13
• 10
• 9
• 17
• ### Forum Statistics

• Total Topics
632601
• Total Posts
3007358

×