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}