Generate random starting points at same distance between them

Question

Is there an algorithm to generate random 2D points that are at the same distance between each other? Useful for starting points. Check map:

Don't be picky, I know in the image points are not at the same distance, lol, but you get the idea.

Answer 1

It's tough to be really "random" but this is how I would simulate it. Create a grid of equilateral triangles. The initial position and rotation of this grid can be random. Then overlay this grid onto your land mass. Now pick vertex points from that grid that fall on land.

Answer 2

I think the only way to get a set of points that are exactly equidistant from their neighbours is to place them on the vertices of an equilateral polygon, such as a square, pentagon, hexagon, octagon, equilateral triangle, etc.

Note that you can't guarantee that all points are equidistant from each other in 2 dimensions unless you limit yourself to 3 points on an equilateral triangle. (In 3 dimensions you can do it with a tetrahedron, and so on.)

If you're happy to have some points closer than others providing they have a uniform distance to whichever point is nearest (e.g. as in your example) then you can use any of the shapes listed at the top, plus any tessellated combination of those shapes (which excludes pentagons and octagons, etc).

Your image would not be possible to implement because the point in the middle would be nearer to all the others than the others are to their neighbours. But if you added another point you could have 6 equilateral triangles in a circle.

If we assume you don't need points to be at exactly the same distance, then you can try and generate positions through an iterative method. First, pick completely random positions. Then for each point, if it is closer to any other point than the ideal distance you're searching for, move it away from that point by a distance proportional to how far it would have to move to fix the problem entirely (e.g. 10%). If it's too far, do the opposite. Once you have done this for all points, keep repeating until either each point is a suitable distance from the others, or none of the points have moved much this iteration. At that point, you can decide whether the generated positions are good enough or not, and try again if not. This works well for an arbitrary number of points but won't necessarily guarantee a very regular shape.

Alternatively, if shape is important and you know how many points you need to place, generate the basic layout first (e.g. by tessellating some equilateral triangles) and then try to translate and rotate that to fit in your map. It's probably easiest to place the centroid of the layout over the centroid of the map and then just try a bunch of possible rotation values to see if any fit.