Algorithm for picking N random uniformly distributed samples, in irregular polygon?

Question

Say want to pick a fixed number of samples from a large 2D dataset, such that they relatively evenly distributed over the whole sample area. Imagine places in a country - so the border of the data is a irregular polygon.

Aware of poisson-disk based sampling, but that has a minimum distance as input, which dont know. The number of points want is the input variable.

Can just divide the area into a grid (as long as sample size is easily divisible), but it tends to favour the edges, parts of the grid with little coverage.

As an exaggerated example, picking 16 samples from a circle, tends to have a lot of samples around the edges, because will still pick one from each square. (the circle is just to demonstrate a kinda of worse case, but the 'grid' will never exactly match the polygon)

Best idea is at the moment, is to take the samples and perform something like https://en.wikipedia.org/wiki/Lloyd%27s_algorithm so the points 'relax' to be spread out over a rectangle. Then can just pick the points from the regular grid. ... but its never going to be very effient, as will have to do multiple rounds of Lloyds over a large dataset.

Feels like there is algorithm for this, but don't actually know what to look for!

Edit: actully here is a better demo, using real data, of issue with picking points from a grid. Getting lots of points around the coast, as have lots of Ireland that overlaps bits of squares.

Answer 1

Well, found an answer. Farthest-first traversal

https://en.wikipedia.org/wiki/Farthest-first_traversal

Embarrassingly it was linked in 'See Also' on wikipedia page for Lloyd's Algorithm. It was only when trying to implement Lloyd's that left the wikipedia page open, and read it again today.

While it is still favouring points along the edge (as furthest from other points) - it is picking them with good distribution.

... you just Traverse until have N points.

--- Edit to add:

And to further close the loop, found a way to avoid favouring coastal points. First add a selection of 'offshore' points, around the edge, so the selected points are kept away from edge (but will still approach the edges)

The points, actully follow the territorial sea, which is the line plotted on OSM map used in this demo. Its what gave me the idea. If not working with geographical data (where the area polygon, is not a know country) could perhaps just use Concave Hull + Buffer operation to get a 'offshore boundary'.

Although still need to find a nice way of selecting a uniform distribution of points along that boundary. Maybe Further-First Traversal of the points from the boundary would work!