001package squidpony.squidmath;
002
003import java.util.ArrayDeque;
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 * @author Tommy Ettinger
012 * @author smelC
013 */
014public class Bresenham {
015
016    /**
017     * Prevents any instances from being created
018     */
019    private Bresenham() {
020    }
021
022    /**
023     * Generates a 2D Bresenham line between two points. If you don't need
024     * the {@link Queue} interface for the returned reference, consider
025     * using {@link #line2D_(Coord, Coord)} to save some memory.
026     *
027     * @param a the starting point
028     * @param b the ending point
029     * @return The path between {@code a} and {@code b}.
030     */
031    public static Queue<Coord> line2D(Coord a, Coord b) {
032        return line2D(a.x, a.y, b.x, b.y);
033    }
034
035    /**
036     * Generates a 2D Bresenham line between two points.
037     *
038     * @param a the starting point
039     * @param b the ending point
040     * @return The path between {@code a} and {@code b}.
041     */
042    public static Coord[] line2D_(Coord a, Coord b) {
043        return line2D_(a.x, a.y, b.x, b.y);
044    }
045
046    /**
047     * Generates a 3D Bresenham line between two points.
048     *
049     * @param a Coord to start from. This will be the first element of the list
050     * @param b Coord to end at. This will be the last element of the list.
051     * @return A list of points between a and b.
052     */
053    public static Queue<Coord3D> line3D(Coord3D a, Coord3D b) {
054        return line3D(a.x, a.y, a.z, b.x, b.y, b.z);
055    }
056
057    /**
058     * Generates a 3D Bresenham line between the given coordinates.
059     * Uses a Coord3D for each point; keep in mind Coord3D values are not
060     * pooled like ordinary 2D Coord values, and this may cause more work
061     * for the garbage collector, especially on Android, if many Coord3D
062     * values are produced.
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 a Queue (internally, an ArrayDeque) of Coord3D points along the line
071     */
072    public static Queue<Coord3D> line3D(int startx, int starty, int startz, int endx, int endy, int endz) {
073        int dx = endx - startx;
074        int dy = endy - starty;
075        int dz = endz - startz;
076
077        int ax = Math.abs(dx);
078        int ay = Math.abs(dy);
079        int az = Math.abs(dz);
080        Queue<Coord3D> result = new ArrayDeque<>(Math.max(Math.max(ax, ay), az));
081
082        ax <<= 1;
083        ay <<= 1;
084        az <<= 1;
085        
086        int signx = (dx >> 31 | -dx >>> 31); // project nayuki signum
087        int signy = (dy >> 31 | -dy >>> 31); // project nayuki signum
088        int signz = (dz >> 31 | -dz >>> 31); // project nayuki signum
089
090        int x = startx;
091        int y = starty;
092        int z = startz;
093
094        int deltax, deltay, deltaz;
095        if (ax >= Math.max(ay, az)) /* x dominant */ {
096            deltay = ay - (ax >> 1);
097            deltaz = az - (ax >> 1);
098            while (true) {
099                result.offer(new Coord3D(x, y, z));
100                if (x == endx) {
101                    return result;
102                }
103
104                if (deltay >= 0) {
105                    y += signy;
106                    deltay -= ax;
107                }
108
109                if (deltaz >= 0) {
110                    z += signz;
111                    deltaz -= ax;
112                }
113
114                x += signx;
115                deltay += ay;
116                deltaz += az;
117            }
118        } else if (ay >= Math.max(ax, az)) /* y dominant */ {
119            deltax = ax - (ay >> 1);
120            deltaz = az - (ay >> 1);
121            while (true) {
122                result.offer(new Coord3D(x, y, z));
123                if (y == endy) {
124                    return result;
125                }
126
127                if (deltax >= 0) {
128                    x += signx;
129                    deltax -= ay;
130                }
131
132                if (deltaz >= 0) {
133                    z += signz;
134                    deltaz -= ay;
135                }
136
137                y += signy;
138                deltax += ax;
139                deltaz += az;
140            }
141        } else {
142            deltax = ax - (az >> 1);
143            deltay = ay - (az >> 1);
144            while (true) {
145                result.offer(new Coord3D(x, y, z));
146                if (z == endz) {
147                    return result;
148                }
149
150                if (deltax >= 0) {
151                    x += signx;
152                    deltax -= az;
153                }
154
155                if (deltay >= 0) {
156                    y += signy;
157                    deltay -= az;
158                }
159
160                z += signz;
161                deltax += ax;
162                deltay += ay;
163            }
164        }
165    }
166
167    /**
168     * Generates a 2D Bresenham line between two points. If you don't need
169     * the {@link Queue} interface for the returned reference, consider
170     * using {@link #line2D_(int, int, int, int)} to save some memory.
171     * <br>
172     * Uses ordinary Coord values for points, and these can be pooled
173     * if they aren't beyond what the current pool allows (it starts,
174     * by default, pooling Coords with x and y between -3 and 255,
175     * inclusive). If the Coords are pool-able, it can significantly
176     * reduce the work the garbage collector needs to do, especially
177     * on Android.
178     *
179     * @param startx the x coordinate of the starting point
180     * @param starty the y coordinate of the starting point
181     * @param endx the x coordinate of the starting point
182     * @param endy the y coordinate of the starting point
183     * @return a Queue (internally, an ArrayDeque) of Coord points along the line
184     */
185    public static Queue<Coord> line2D(int startx, int starty, int endx, int endy) {
186        // largest positive int for maxLength; a Queue cannot actually be given that many elements on the JVM
187        return line2D(startx, starty, endx, endy, 0x7fffffff);
188    }
189
190    /**
191     * Generates a 2D Bresenham line between two points, stopping early if
192     * the number of Coords returned reaches maxLength. If you don't need
193     * the {@link Queue} interface for the returned reference, consider
194     * using {@link #line2D_(int, int, int, int, int)} to save some memory.
195     * <br>
196     * Uses ordinary Coord values for points, and these can be pooled
197     * if they aren't beyond what the current pool allows (it starts,
198     * by default, pooling Coords with x and y between -3 and 255,
199     * inclusive). If the Coords are pool-able, it can significantly
200     * reduce the work the garbage collector needs to do, especially
201     * on Android.
202     *
203     * @param startx the x coordinate of the starting point
204     * @param starty the y coordinate of the starting point
205     * @param endx the x coordinate of the starting point
206     * @param endy the y coordinate of the starting point
207     * @param maxLength the largest count of Coord points this can return; will stop early if reached
208     * @return a Queue (internally, a ArrayDeque) of Coord points along the line
209     */
210    public static Queue<Coord> line2D(int startx, int starty, int endx, int endy, int maxLength) {
211        int dx = endx - startx;
212        int dy = endy - starty;
213
214        int ax = Math.abs(dx);
215        int ay = Math.abs(dy);
216
217        Queue<Coord> result = new ArrayDeque<>(Math.max(ax, ay));
218
219        ax <<= 1;
220        ay <<= 1;
221        
222        int signx = (dx >> 31 | -dx >>> 31); // project nayuki signum
223        int signy = (dy >> 31 | -dy >>> 31); // project nayuki signum
224
225        int x = startx;
226        int y = starty;
227
228        int deltax, deltay;
229        if (ax >= ay) /* x dominant */ {
230            deltay = ay - (ax >> 1);
231            while (result.size() < maxLength) {
232                result.offer(Coord.get(x, y));
233                if (x == endx) {
234                    return result;
235                }
236
237                if (deltay >= 0) {
238                    y += signy;
239                    deltay -= ax;
240                }
241
242                x += signx;
243                deltay += ay;
244            }
245        } else /* y dominant */ {
246            deltax = ax - (ay >> 1);
247            while (result.size() < maxLength) {
248                result.offer(Coord.get(x, y));
249                if (y == endy) {
250                    return result;
251                }
252
253                if (deltax >= 0) {
254                    x += signx;
255                    deltax -= ay;
256                }
257
258
259                y += signy;
260                deltax += ax;
261            }
262        }
263        return result;
264    }
265
266
267    /**
268     * Generates a 2D Bresenham line between two points. Returns an array
269     * of Coord instead of a Queue.
270     * <br>
271     * Uses ordinary Coord values for points, and these can be pooled
272     * if they aren't beyond what the current pool allows (it starts,
273     * by default, pooling Coords with x and y between -3 and 255,
274     * inclusive). If the Coords are pool-able, it can significantly
275     * reduce the work the garbage collector needs to do, especially
276     * on Android.
277     *
278     * @param startx the x coordinate of the starting point
279     * @param starty the y coordinate of the starting point
280     * @param endx the x coordinate of the starting point
281     * @param endy the y coordinate of the starting point
282     * @return an array of Coord points along the line
283     */
284    public static Coord[] line2D_(int startx, int starty, int endx, int endy) {
285        // largest positive int for maxLength; it is extremely unlikely that this could be reached
286        return line2D_(startx, starty, endx, endy, 0x7fffffff);
287    }
288
289
290    /**
291     * Generates a 2D Bresenham line between two points, stopping early if
292     * the number of Coords returned reaches maxLength.. Returns an array
293     * of Coord instead of a Queue.
294     * <br>
295     * Uses ordinary Coord values for points, and these can be pooled
296     * if they aren't beyond what the current pool allows (it starts,
297     * by default, pooling Coords with x and y between -3 and 255,
298     * inclusive). If the Coords are pool-able, it can significantly
299     * reduce the work the garbage collector needs to do, especially
300     * on Android.
301     *
302     * @param startx the x coordinate of the starting point
303     * @param starty the y coordinate of the starting point
304     * @param endx the x coordinate of the starting point
305     * @param endy the y coordinate of the starting point
306     * @param maxLength the largest count of Coord points this can return; will stop early if reached
307     * @return an array of Coord points along the line
308     */
309    public static Coord[] line2D_(int startx, int starty, int endx, int endy, int maxLength) {
310        int dx = endx - startx;
311        int dy = endy - starty;
312
313        int signx = (dx >> 31 | -dx >>> 31); // project nayuki signum
314        int signy = (dy >> 31 | -dy >>> 31); // project nayuki signum
315
316        int ax = (dx = Math.abs(dx)) << 1;
317        int ay = (dy = Math.abs(dy)) << 1;
318
319        int x = startx;
320        int y = starty;
321
322        int deltax, deltay;
323        if (ax >= ay) /* x dominant */ {
324            deltay = ay - (ax >> 1);
325            Coord[] result = new Coord[Math.min(maxLength, dx+1)];
326            for (int i = 0; i <= dx && i < maxLength; i++) {
327                result[i] = Coord.get(x, y);
328
329                if (deltay >= 0) {
330                    y += signy;
331                    deltay -= ax;
332                }
333
334                x += signx;
335                deltay += ay;
336            }
337            return result;
338        } else /* y dominant */ {
339            deltax = ax - (ay >> 1);
340            Coord[] result = new Coord[Math.min(maxLength, dy+1)];
341            for (int i = 0; i <= dy && i < maxLength; i++) {
342                result[i] = Coord.get(x, y);
343
344                if (deltax >= 0) {
345                    x += signx;
346                    deltax -= ay;
347                }
348
349
350                y += signy;
351                deltax += ax;
352            }
353            return result;
354        }
355    }
356
357}