I'm working on a game prototype that is going to involve generating a map from Delaunay triangles created from a very large list of points (easily in the hundred thousand range, as it's going to be a small planet), however to get to that I'm going to need a nice distribution of points in a large circle.
The reason I'm specifically using Delaunay triangles is because it will be fairly easy to enforce a maximum size for triangles by limiting side length. With Voronoi cells I would have to look at the area the cell occupies which is considerably more intensive, and I'm not really aware of other nice methods of generating polygons from points.
I know how to uniformly place random points so outer layers contain more in proportion to their area, however I need to then smooth the points to ensure there's no large gaps or dense clusters of points for the Delaunay set. A good example of what I need is Lloyd's Algorithm, however I would prefer a method that runs as fast as possible to achieve a roughly uniform distribution, as it should churn through all the points in no more than a couple of minutes on an average low-end CPU (let's say 2GHz single-core).
A good baseline in my opinion for determining it to be roughly uniform is by examining every point and looking at the distance to the nearest neighbour. If the smallest minimum distance for a point is at least twice as small as the largest, it's not uniform.
If required, I can modify my point distribution function to create a roughly even distribution with quadrants if the smoothing requires a reasonable starting point, or you can supply your own. However, this will only apply if it saves considerable amounts of time compared to not doing it (which I'd expect to be the case as it reduces worst-case scenarios).
Finally, an answer which conforms the smoothing to a set radii is worth more than one which requires altering the result, and an answer that can conform to a given radial height-map (via function calls to an angle) is worth even more as I plan on creating a radial height-map already (flat planets are boring). Also, code examples in Java are inherently more useful as I'll be making my game in that, but other code examples are fine.
Any suggestions on how I should tackle the problem of smoothing points in a circle with maximum efficiency?
Start from a uniform distribution (randomly picked from a static set of uniform distribution).
For each point add a random gaussian noise of small amplitude.
End.