Straight lines in a hexagonal raster
This study does not pretend to originality, I believe that I’m actually reinventing the bicycle, but I couldn’t find any details of it in (I admit, quite superficially) studying the Internet.
After watching a variety of toys, the movement of characters in which is made on a plane paved with regular hexagons, I was hooked by the question - what should the line look like on such a plane. Actually, the problem of optimal movement of a character from hexagon A to hexagon B (I mean that there are no obstacles on the plane, by optimal movement I mean such that it happens through the least number of hexagons) can be solved in a bunch of different ways, the route is far from unique, as, by the way, on a plane covered with squares. But I would like the route to be close to the straight line segment, as close to the straight image segment, constructed according to the Brezenham algorithm , and at the same time, the implementation should be fairly transparent and simple.
With the use of calculations in the field of real numbers, the following approach will be the most transparent: suppose there are coordinates of the beginning and end centers. Suppose a part of a straight line has already been built (for example, an initial hexagonal “pixel” has been set). From the last built pixel, you need to choose in its neighborhood (in which there are 6 other hexagons) that hexagon, the sum of the distances (in the sense of ordinary geometry) from the center of which to the beginning and end of the segment under construction is minimal (in fact, it suffices to consider two cases — either two lower , or lower right and right, depending on some condition, which will be described below). The algorithm itself requires calculations in the field of real numbers, calculations of square roots, which I do not really want to do.
For a start, it is convenient to choose a coordinate system that uniquely identifies each “pixel” of the raster. After a few options considered, I stopped at the simplest.
')
In each of the hexagons, the coordinates — x and y — are written, which, for convenience, I will call “raster” to distinguish it from the coordinates of points, which are conveniently called “geometric”.
In the process of solving the problem was divided into two cases, the condition for the separation of which I received in the process of solving. Below it will be clear why this is happening, but for now I will give a condition. If we take the coordinates of the beginning of the segment as (0, 0), and the end as (x, y), then the first case is obtained when the condition x ≥ [y / 2] and, accordingly, x <[y / 2], where the square brackets denote taking the whole part. These conditions divide the mosaic into two unequal areas, the boundary of which is as follows:
First, I will give a solution for the first case, it is perhaps the most obvious. It is striking that the use of the algorithm Brezenhema "head" will not give the desired effect. The fact is that in it, x grows at each iteration, and y when the error value overflows. But when moving from an even line to an odd simultaneous growth of x and y, it will break. For example, if in the hexagon (2, 2) we increase both coordinates by one, we get a hexagon (3, 3), which does not have, as can be seen in the figures above, with the first common borders. But if from (2, 2) to go to point (2, 3), and then to (3, 3), there will be no discontinuities. Mosaic can be deformed as follows:
And also temporarily change the coordinates:
In the last picture, it is clear that the dividing segment exactly passes along the boundary of the octet for the Brezenham algorithm, therefore, in this situation, the algorithm becomes already applicable. Moreover, each next point at iteration in the algorithm is adjacent to the previous one in the initial mosaic. Thus, it suffices to apply the Brezenham algorithm in a deformed mosaic with modified coordinates, after which everything is returned to its original place, and a straight line in a hexagonal raster will be obtained. The pictures below are a couple of illustrations of the algorithm.
The length of the line (the number of hexagons involved in the construction) is x + [(y + 1) / 2] + 1. The square brackets are all the same taking the whole part. Geometrically, this is the number of points horizontally plus the number of transitions from even to odd lines (the top line has the number 0, because it is even).
In the second case, it is obvious that the length of the line should not exceed y + 1. Unlike the classical Bresenham algorithm, this case is not symmetrical to the first one, but the technique is similar - to make the above deformation and draw a segment, but according to the rules of another octet, where the main changes occur along the y axis.
I repeat once again - I admit that this is a bicycle invention, and I apologize for the time taken in this case.
After watching a variety of toys, the movement of characters in which is made on a plane paved with regular hexagons, I was hooked by the question - what should the line look like on such a plane. Actually, the problem of optimal movement of a character from hexagon A to hexagon B (I mean that there are no obstacles on the plane, by optimal movement I mean such that it happens through the least number of hexagons) can be solved in a bunch of different ways, the route is far from unique, as, by the way, on a plane covered with squares. But I would like the route to be close to the straight line segment, as close to the straight image segment, constructed according to the Brezenham algorithm , and at the same time, the implementation should be fairly transparent and simple.
With the use of calculations in the field of real numbers, the following approach will be the most transparent: suppose there are coordinates of the beginning and end centers. Suppose a part of a straight line has already been built (for example, an initial hexagonal “pixel” has been set). From the last built pixel, you need to choose in its neighborhood (in which there are 6 other hexagons) that hexagon, the sum of the distances (in the sense of ordinary geometry) from the center of which to the beginning and end of the segment under construction is minimal (in fact, it suffices to consider two cases — either two lower , or lower right and right, depending on some condition, which will be described below). The algorithm itself requires calculations in the field of real numbers, calculations of square roots, which I do not really want to do.
For a start, it is convenient to choose a coordinate system that uniquely identifies each “pixel” of the raster. After a few options considered, I stopped at the simplest.
')
In each of the hexagons, the coordinates — x and y — are written, which, for convenience, I will call “raster” to distinguish it from the coordinates of points, which are conveniently called “geometric”.
In the process of solving the problem was divided into two cases, the condition for the separation of which I received in the process of solving. Below it will be clear why this is happening, but for now I will give a condition. If we take the coordinates of the beginning of the segment as (0, 0), and the end as (x, y), then the first case is obtained when the condition x ≥ [y / 2] and, accordingly, x <[y / 2], where the square brackets denote taking the whole part. These conditions divide the mosaic into two unequal areas, the boundary of which is as follows:
First case: x ≥ [y / 2]
First, I will give a solution for the first case, it is perhaps the most obvious. It is striking that the use of the algorithm Brezenhema "head" will not give the desired effect. The fact is that in it, x grows at each iteration, and y when the error value overflows. But when moving from an even line to an odd simultaneous growth of x and y, it will break. For example, if in the hexagon (2, 2) we increase both coordinates by one, we get a hexagon (3, 3), which does not have, as can be seen in the figures above, with the first common borders. But if from (2, 2) to go to point (2, 3), and then to (3, 3), there will be no discontinuities. Mosaic can be deformed as follows:
And also temporarily change the coordinates:
In the last picture, it is clear that the dividing segment exactly passes along the boundary of the octet for the Brezenham algorithm, therefore, in this situation, the algorithm becomes already applicable. Moreover, each next point at iteration in the algorithm is adjacent to the previous one in the initial mosaic. Thus, it suffices to apply the Brezenham algorithm in a deformed mosaic with modified coordinates, after which everything is returned to its original place, and a straight line in a hexagonal raster will be obtained. The pictures below are a couple of illustrations of the algorithm.
The length of the line (the number of hexagons involved in the construction) is x + [(y + 1) / 2] + 1. The square brackets are all the same taking the whole part. Geometrically, this is the number of points horizontally plus the number of transitions from even to odd lines (the top line has the number 0, because it is even).
Second case: x <[y / 2]
In the second case, it is obvious that the length of the line should not exceed y + 1. Unlike the classical Bresenham algorithm, this case is not symmetrical to the first one, but the technique is similar - to make the above deformation and draw a segment, but according to the rules of another octet, where the main changes occur along the y axis.
Java code
public final class Line implements Iterable<Point> { private final Point begin; private final int dx; private final int dy; private final int sx; private final int sy; public Line(final Point begin, final Point end) { this.begin = begin; int dx = end.x - begin.x; int dy = end.y - begin.y; if (dx < 0) { dx = -dx; sx = -1; } else { sx = 1; } if (dy < 0) { dy = -dy; sy = -1; } else { sy = 1; } this.dx = dx + (dy + 1) / 2; this.dy = dy; } @Override public Iterator<Point> iterator() { return dx > dy ? new LineIterator1() : new LineIterator2(); } private final class LineIterator1 implements Iterator<Point> { private int x = 0; private int y = 0; private int error = 0; @Override public boolean hasNext() { return x <= dx; } @Override public Point next() { if (x > dx) return null; Point point = new Point(begin.x + (x - (y + 1) / 2) * sx, begin.y + y * sy); x++; if (x <= dx) { error += dy; if (2 * error >= dx) { y++; error -= dx; } } return point; } @Override public void remove() { throw new UnsupportedOperationException(); } } private final class LineIterator2 implements Iterator<Point> { private int x = 0; private int y = 0; private int error = 0; @Override public boolean hasNext() { return y <= dy; } @Override public Point next() { if (y > dy) return null; Point point = new Point(begin.x + (x - (y + 1) / 2) * sx, begin.y + y * sy); y++; if (y <= dy) { error = error + dx; if (2 * error >= dy) { error -= dy; x++; } } return point; } @Override public void remove() { throw new UnsupportedOperationException(); } } } Point class
public final class Point { public final int x; public final int y; public Point(final int x, final int y) { this.x = x; this.y = y; } } I repeat once again - I admit that this is a bicycle invention, and I apologize for the time taken in this case.
Source: https://habr.com/ru/post/193668/
All Articles