001package squidpony.squidmath;
002
003import java.util.LinkedList;
004import java.util.Queue;
005
006/**
007 * Provides a means to generate Bresenham lines in 2D and 3D.
008 *
009 * @author Eben Howard - http://squidpony.com - howard@squidpony.com
010 * @author Lewis Potter
011 */
012public class Bresenham {
013
014    /**
015     * Prevents any instances from being created
016     */
017    private Bresenham() {
018    }
019
020    /**
021     * Generates a 2D Bresenham line between two points.
022     *
023     * @param a the starting point
024     * @param b the ending point
025     * @return
026     */
027    public static Queue<Coord> line2D(Coord a, Coord b) {
028        return line2D(a.x, a.y, b.x, b.y);
029    }
030
031    /**
032     * Generates a 2D Bresenham line between two points.
033     *
034     * @param startX the x coordinate of the starting point
035     * @param startY the y coordinate of the starting point
036     * @param endX the x coordinate of the ending point
037     * @param endY the y coordinate of the ending point
038     * @return
039     */
040    public static Queue<Coord> line2D(int startX, int startY, int endX, int endY) {
041        Queue<Coord> line = new LinkedList<>();
042        Queue<Coord3D> found = line3D(startX, startY, 0, endX, endY, 0);
043                while (!found.isEmpty()) {
044                        final Coord3D c3d = found.poll();
045                        line.offer(/* translate to 2D */ Coord.get(c3d.x, c3d.y));
046                }
047                return line;
048    }
049
050    /**
051     * Generates a 3D Bresenham line between two points.
052     *
053     * @param a Coord to start from. This will be the first element of the list
054     * @param b Coord to end at. This will be the last element of the list.
055     * @return A list of points between a and b.
056     */
057    public static Queue<Coord3D> line3D(Coord3D a, Coord3D b) {
058        return line3D(a.x, a.y, a.z, b.x, b.y, b.z);
059    }
060
061    /**
062     * Generates a 3D Bresenham line between the given coordinates.
063     *
064     * @param startx the x coordinate of the starting point
065     * @param starty the y coordinate of the starting point
066     * @param startz the z coordinate of the starting point
067     * @param endx the x coordinate of the starting point
068     * @param endy the y coordinate of the starting point
069     * @param endz the z coordinate of the starting point
070     * @return
071     */
072    public static Queue<Coord3D> line3D(int startx, int starty, int startz, int endx, int endy, int endz) {
073        Queue<Coord3D> result = new LinkedList<>();
074
075        int dx = endx - startx;
076        int dy = endy - starty;
077        int dz = endz - startz;
078
079        int ax = Math.abs(dx) << 1;
080        int ay = Math.abs(dy) << 1;
081        int az = Math.abs(dz) << 1;
082
083        int signx = (int) Math.signum(dx);
084        int signy = (int) Math.signum(dy);
085        int signz = (int) Math.signum(dz);
086
087        int x = startx;
088        int y = starty;
089        int z = startz;
090
091        int deltax, deltay, deltaz;
092        if (ax >= Math.max(ay, az)) /* x dominant */ {
093            deltay = ay - (ax >> 1);
094            deltaz = az - (ax >> 1);
095            while (true) {
096                result.offer(new Coord3D(x, y, z));
097                if (x == endx) {
098                    return result;
099                }
100
101                if (deltay >= 0) {
102                    y += signy;
103                    deltay -= ax;
104                }
105
106                if (deltaz >= 0) {
107                    z += signz;
108                    deltaz -= ax;
109                }
110
111                x += signx;
112                deltay += ay;
113                deltaz += az;
114            }
115        } else if (ay >= Math.max(ax, az)) /* y dominant */ {
116            deltax = ax - (ay >> 1);
117            deltaz = az - (ay >> 1);
118            while (true) {
119                result.offer(new Coord3D(x, y, z));
120                if (y == endy) {
121                    return result;
122                }
123
124                if (deltax >= 0) {
125                    x += signx;
126                    deltax -= ay;
127                }
128
129                if (deltaz >= 0) {
130                    z += signz;
131                    deltaz -= ay;
132                }
133
134                y += signy;
135                deltax += ax;
136                deltaz += az;
137            }
138        } else if (az >= Math.max(ax, ay)) /* z dominant */ {
139            deltax = ax - (az >> 1);
140            deltay = ay - (az >> 1);
141            while (true) {
142                result.offer(new Coord3D(x, y, z));
143                if (z == endz) {
144                    return result;
145                }
146
147                if (deltax >= 0) {
148                    x += signx;
149                    deltax -= az;
150                }
151
152                if (deltay >= 0) {
153                    y += signy;
154                    deltay -= az;
155                }
156
157                z += signz;
158                deltax += ax;
159                deltay += ay;
160            }
161        }
162        return result;
163    }
164}