Hot to find the closest free points on grid
https://stackoverflow.com/questions/12916082
-
07-07-2021 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Imagine a simple 2D grid; the objects on the grid can occupy more then one cell (but the points are always connected). Consider the following example, where I use letters A and B just to distinguish the objects (it is useful since the objects may be placed near each other):
0 1 2 3 4 5 6 7 8 9 10
1 . . . . . . . . . .
2 . . . . . . . . . .
3 . . . A . . . . . .
4 . . A A A . . B B .
5 . . . A . . . B B .
6 . . . . . . . . . .
I need an algorithm for the insertion of new objects that would position them on the grid and make sure they do not overlap. Thus, if I would like to embed a new object (denoted with C) and the coordinates of any of its cells would already be occupied, the algorithm should find the closest free region (i.e., list of points) to allocate the new object. Lets try to insert the object C at the coordinate (4, 3) which is already occupied by a cell from A:
0 1 2 3 4 5 6 7 8 9 10
1 . . . . . . . . . .
2 . C C . . . . . . .
3 . C C A . . . . . .
4 . . A A A . . B B .
5 . . . A . . . B B .
6 . . . . . . . . . .
As you can see, the object was moved to fit near the object A. I assume that the search should start around the occupied cell with the order (given in directions): N, E, S, W and after this in the middle directions: NE, SE, etc.
How would you suggest to implement this algorithm?
Update: The object position is the upper left point. And the closest point is obtained from the distance that is evaluated between the initial requested position and the surrounding free points.
Solution
You want to iterate over possible displacements (i.e. shifts) in order of increasing distance. As all displacements are integers, the squared displacements need to be sums of two squares. The following python code keeps track of the next possible y displacement for each x displacement. It generates lists of pairs. Each pair denotes displacement coordinates. All elements in a single list have the same distance from the origin, whereas elements from later lists will have greater distance. So it doesn't matter in what order you traverse the inner lists, at least in terms of distances. You might even want to randomize those.
def iter_distance(maxr = 10):
r = 0
d = [0]
while r <= maxr:
m = maxr*maxr + 1
for x, y in enumerate(d):
sq = x*x + y*y
if sq < m:
m = sq
b = []
if sq == m:
b.append((x, y))
for x, y in b:
d[x] = y + 1
if b[-1][0] == r:
r += 1
d.append(0)
yield (b +
[(x, -y) for x, y in b if y] +
[(-x, y) for x, y in b if x] +
[(-x, -y) for x, y in b if x*y])
for lst in iter_distance():
marker = '*'
for x, y in lst:
print("{:5} {:5} {:10} {}".format(x, y, x*x + y*y, marker))
marker = ' '
The first lines of output look like this:
0 0 0 *
0 1 1 *
1 0 1
0 -1 1
-1 0 1
1 1 2 *
1 -1 2
-1 1 2
-1 -1 2
0 2 4 *
2 0 4
0 -2 4
-2 0 4
1 2 5 *
2 1 5
1 -2 5
2 -1 5
-1 2 5
-2 1 5
-1 -2 5
-2 -1 5
2 2 8 *
2 -2 8
-2 2 8
-2 -2 8
0 3 9 *
3 0 9
0 -3 9
-3 0 9
For distances up to 400 (i.e. passing 400 as the maxr argument), you'd get 502,625 lines for 37,556 different distances, so you want to generate these on the fly, not hard-code them into the application. You may however use these numbers to check your implementation, in case one of us made an error.
If you are concerned about performance, you can use a priority queue instead of an array, and write it like this:
#include <queue>
#include <utility>
#include <cmath>
#include <iostream>
#include <iomanip>
class displacement {
private:
int _d;
int _x;
int _y;
public:
displacement() : _d(0), _x(0), _y(0) {}
displacement(int x, int y) : _d(x*x + y*y), _x(x), _y(y) {}
int x() const { return _x; }
int y() const { return _y; }
int sqd() const { return _d; }
bool operator<(const displacement& d) const { return sqd() > d.sqd(); }
};
static void print2(int x, int y, int sqd) {
std::cout << std::setw(10) << x << ' '
<< std::setw(10) << y << ' '
<< std::setw(20) << sqd << ' '
<< std::endl;
}
static void print1(int x, int y, int sqd) {
print2(x, y, sqd);
if (y)
print2(x, -y, sqd);
if (x) {
print2(-x, y, sqd);
if (y)
print2(-x, -y, sqd);
}
}
int main(int argc, char** argv) {
int maxr = 400;
int maxrsq = maxr*maxr;
std::priority_queue<displacement> q;
q.push(displacement(0, 0));
while (q.top().sqd() <= maxrsq) {
const displacement& d = q.top();
int x = d.x();
int y = d.y();
int sqd = d.sqd();
print1(x, y, sqd);
q.pop();
q.push(displacement(x, y + 1));
if (x == y) {
q.push(displacement(x + 1, y + 1));
}
else {
print1(y, x, sqd);
}
}
}
In this case, the queue contains individual displacements, and the result will print individual displacements of the same distance in arbitrary (and probably implementation-defined) order, without collecting them into a list. Only the mirror images of a given displacement will be printed immediately. The code here employs full 8-fold symmetry, so the number of elements stored in the queue at any single time is even less than the maximal distance generated so far, except at the very beginning.
OTHER TIPS
I suppose that you have a method do check object overlap so, I will define an object that encapsulates the hole plane and its already placed objects: Plane with the instance method boolean overlaps(Object2D object, Point position) that returns true if the Object2D - the object you want to place, overlaps any object into the plane when you put it in the position or if it doesn't fit into the plane, like when placing it in the right down edge of the plane when the object is bigger than a single point.
As @MvG pointed out, there are only integer points so there is a limitaded number of possible distances so I would do a lookup table for distances between points to speed-up the process this way (I am assuming Java):
// creates a lookup table with the possible offsets for each possible distance
static Hashtable<Integer, List<Point>> createLookupPointOffsets(int gridWidth, int gridHeight)
{
Hashtable<Integer, List<Point>> l = new Hashtable<Integer, List<Point>>();
for (int i = 0; i <= gridWidth; i++)
{
int i2 = i * i;
for (int j = 0; j <= gridHeight; j++)
{
int sqrDistance = i2 + j * j; // distance^2
List<Point> ps = l.get(sqrDistance);
if (ps == null)
{
ps = new List<Point>();
l.put(sqrDistance, ps);
}
ps.add(new Point(i, j));
}
}
}
this way you will have the 1/4 of the offsets for the possible distances indexed, for the others you just have to reflect the points through the x or y or both axis. To evaluate the closest possible point to place your object using this indexed offsets you add this method in Plane, I assume that the variable mIndexedOffsets is initialized with the result of the last method:
// returns true if placed the object
boolean place(Object2D object, Point position)
{
if (overlaps(object, position))
{
Integer[] distances = new Integer[mIndexedOffsets.keySet().size()];
distances = mIndexedOffsets.keySet().ToArray(distances);
// sort the keys in crescent order
for (int k = 0; k < distances.length - 1; k++)
{
for (int l = k + 1; l < distances.length; l++)
{
if (distances[k] > distances[l])
{
int t = distances[k];
distances[k] = distances[l];
distances[l] = t;
}
}
}
for (int i = 0; i < distances.length; i++)
{
List<Point> ps = mIndexedOffsets.get(distances[i]);
for (int j = 0; j < ps.size(); j++)
{
Point p = ps.get(j);
Point newPoint = (Point) position.clone();
newPoint.x += p.x;
newPoint.y += p.y;
if (!overlaps(object, newPoint)
{
put(object, newPoint);
return true;
}
// test with the reflected points
newPoint = (Point) position.clone();
newPoint.x -= p.x;
newPoint.y += p.y;
if (!overlaps(object, newPoint)
{
put(object, newPoint);
return true;
}
newPoint = (Point) position.clone();
newPoint.x += p.x;
newPoint.y -= p.y;
if (!overlaps(object, newPoint)
{
put(object, newPoint);
return true;
}
newPoint = (Point) position.clone();
newPoint.x -= p.x;
newPoint.y -= p.y;
if (!overlaps(object, newPoint)
{
put(object, newPoint);
return true;
}
}
}
}
else
{
put(object, position); // puts the object in the desired position
return true;
}
return false;
}
hope it helps.
