CODEWITHSUNDEEP
algorithmmath
calben
calben

Reputation: 1358

Algorithm to Produce an Evenly Spaced Grid

I'm looking for a general algorithm for creating an evenly spaced grid, and I've been surprised how difficult it is to find! Is this a well solved problem whose name I don't know? Or is this an unsolved problem that is best done by self organising map?

More specifically, I'm attempting to make a grid on a 2D Cartesian plane in which the Euclidean distance between each point and 4 bounding lines (or "walls" to make a bounding box) are equal or nearly equal. For a square number, this is as simple as making a grid with sqrt(n) rows and sqrt(n) columns with equal spacing positioned in the center of the bounding box. For 5 points, the pattern would presumably either be circular or 4 points with a point in the middle.

I didn't find a very good solution, so I've sadly left the problem alone and settled with a quick function that produces the following grid: enter image description here

Upvotes: 1

Views: 2940

Answers (2)

strubbly
strubbly

Reputation: 3477

Unfortunately your problem is still not very clearly specified. You say you want the points to be "equidistant" yet in your example, some pairs of points are far apart (eg top left and bottom right) and the points are all different distances from the walls.

Perhaps you want the points to have equal minimum distance? In which case a simple solution is to draw a cross shape, with one point in the centre and the remainder forming a vertical and horizontal crossed line. The gap between the walls and the points, and the points in the lines can all be equal and this can work with any number of points.

Upvotes: 0

Frank Puffer
Frank Puffer

Reputation: 8215

There is no simple general solution to this problem. A self-organizing map is probably one of the best choices.

Another way to approach this problem is to imagine the points as particles that repel each others and that are also repelled by the walls. As an initial arrangement, you could already evenly distribute the points up to the next smaller square number - for this you already have a solution. Then randomly add the remaining points.

Iteratively modify the locations to minimize the energy function based on the total force between the particles and walls. The result will of course depend on the force law, i.e. how the force depends on the distance.

To solve this, you can use numerical methods like FEM.

A simplified and less efficient method that is based on the same principle is to first set up an estimated minimal distance, based on the square number case which you can calculate. Then iterate through all points a number of times and for each one calculate the distance to its closest neighbor. If this is smaller than the estimated distance, move your point into the opposite direction by a certain fraction of the difference.

This method will generally not lead to a stable minimum but should find an acceptable solution after a number ot iterations. You will have to experiment with the stepsize and the number of iterations.

To summarize, you have three options:

  • FEM method: Efficient but difficult to implement

  • Self organizing map: Slightly less efficient, medium complexity of implementation.

  • Iteration described in last section: Less efficient but easy to implement.

Upvotes: 1

Related Questions