1
$\begingroup$

I have a random point generator which takes a distance $d$ and fills an area with points such that distance between any two points is no less that $d$:

enter image description here

I need to control the number of points in the area, but how to choose $d$? What is needed is just a rough guess since the best $d$ is found using a binary search algorithm.

The point generation is time consuming so the better the initial guess, the faster the heuristic search will be.

Any ideas on how to guess $d$?

$\endgroup$
0
$\begingroup$

Assume the points can be reordered in a square grid. Then increasing distance between points will grow the squares of the grid. Therefore the number of points will be inversely proportional to $d^2$.

Since area is known for some units (pixels in my case), we can tell the number of points $n_{max}$ for the distance $d_{min}=1$ pixel, which is simply the number of pixels in the area.

The estimated number of points then becomes

$$n=n_{max}\cdot(\frac{d_{min}}{d})^2=\frac{n_{max}}{d^2}$$

and

$$d=(\frac{n_{max}}{n})^{\frac{1}{2}}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.