Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

map showing points equidistant(ish) from each other

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

share|improve this question
4  
Can't be both random and same distance, by enforcing a distance requirement you remove the randomness. –  Patrick Hughes Jul 21 '12 at 19:07
    
Its random, but in a different domain. IE, if you want random points within a radius, you will still have random points restricted to the circle. In my case, the first point will be restricted to land, but the remaining points will be restricted to land and also their peers. Perhaps i'm wrong and should have described the problem in other terms, but you get the idea. –  Gabriel A. Zorrilla Jul 21 '12 at 19:20
    
But random points within a circle don't need to be equidistant. Making them equidistant is what makes them non-random, constraining them to land would not. –  Byte56 Jul 21 '12 at 19:26
2  
They can't all be the same distance to each other. You can't have more than 3 points which all gave equal distance to both other points (in a 2d plane). In your example: The lowest and the topmost point are much farther away. So you have to specify: Should a point only be the right distance to one other point, or to two? Should it rather be a minimum distance? –  s3rius Jul 21 '12 at 19:30
    
Here's the equidistant part of the question: "same distance between each other." Basically I think that the original question needs to be thought through much more thoroughly, this one deleted and the new question stated because the original can't be solved. –  Patrick Hughes Jul 21 '12 at 20:21
add comment

2 Answers

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.

enter image description here

share|improve this answer
    
+1, I would go with this :) –  Gustavo Maciel Feb 10 '13 at 14:29
add comment

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.

share|improve this answer
    
+1 I was halfway through typing a response until I realized I was just repeating your answer. –  David Lively Jul 21 '12 at 20:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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