Straight in a hexagonal raster

    This study does not pretend to be original, I believe that I’m actually inventing a bicycle, but I could not find any details from it during (I admit, quite superficial) Internet research.

    After observing a variety of toys, the characters in which are moving 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 task of optimal movement of a character from hexagon A to hexagon B (I mean that there are no obstacles on the plane, I mean optimal movement so that it occurs through the least number of hexagons) can be solved in a bunch of different ways, the route is far from unique, just as as, however, on a plane covered with squares. But I would like the route to be close to the line segment, as the image constructed according to the Bresenham algorithm is close to the line segment, and at the same time, the implementation should be fairly transparent and simple.

    Using calculations in the field of real numbers, the following approach will be most transparent: suppose there are coordinates of the centers of the beginning and the end. Suppose a part of a straight line has already been built (for example, an initial hexagonal “pixel” has been set). From the last constructed pixel, you need to select in its vicinity (in which there are 6 other hexagons) that hexagon, the sum of the distances (in the sense of the usual geometry) from the center of which to the beginning and end of the segment under construction is minimal (in fact, it is enough to consider two cases - or 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 starters, it turns out to be convenient to choose a coordinate system that uniquely identifies each “pixel” of the raster. After several options considered, I settled on the simplest.



    Each of the hexagons contains coordinates - x and y - which for convenience I will call “raster” to distinguish from the coordinates of points that are conveniently called “geometric”.

    In the process of solving the problem, it was divided into two cases, the condition for the separation of which I received in the process of solving. Below it will become clear why this happens, 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 indicate the capture of the whole part. These conditions divide the mosaic into two unequal sections, the border of which passes 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 application of the Bresenham algorithm "in the forehead" 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 switching from an even line to an odd, the simultaneous growth of x and y will lead to a break. For example, if we increase both coordinates in the hexagon (2, 2) by one, we get the hexagon (3, 3), which, as can be seen in the figures above, has the first common borders. But if from (2, 2) we go to the point (2, 3), and then to (3, 3), there will be no gaps. Mosaic can be deformed as follows:



    And also temporarily change the coordinates:



    The last picture shows that the dividing segment exactly passes along the octet boundary for the Bresenham algorithm, therefore, in this situation, the algorithm becomes already applicable. Moreover, each next point during iteration in the algorithm is adjacent to the previous one in the original mosaic. Thus, it is enough to apply the Bresenham algorithm in a deformed mosaic with changed coordinates, and then return everything to its original place, and you get a straight line in the hexagonal raster. In the pictures below 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. Square brackets are all the same taking the whole part. Geometrically, this is the number of horizontal points plus the number by switching from even lines to odd (the top line is number 0, therefore it is even).

    Second case: x <[y / 2]

    In the second case, it is obvious that the line length should not exceed y + 1. Unlike the classical Bresenham algorithm, this case is not symmetrical to the first, however, the procedure is similar - to perform the deformation described above and draw a line, 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 {
        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 iterator() {
            return dx > dy ? new LineIterator1() : new LineIterator2();
        }
        private final class LineIterator1 implements Iterator {
            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 {
            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 an invention of the bicycle, and I apologize for the time taken in this case.

    Also popular now: