001package squidpony.squidmath; 002 003 004import squidpony.annotation.Beta; 005 006import java.io.Serializable; 007import java.util.LinkedList; 008import java.util.List; 009 010/** 011 * Contains methods to draw antialiased lines based on floating point 012 * coordinates. 013 * 014 * Because of the way this line is calculated, endpoints may be swapped and 015 * therefore the list may not be in start-to-end order. 016 * 017 * Based on work by Hugo Elias at 018 * http://freespace.virgin.net/hugo.elias/graphics/x_wuline.htm which is in turn 019 * base on work by Wu. 020 * 021 * @author Eben Howard - http://squidpony.com - howard@squidpony.com 022 */ 023@Beta 024public class Elias implements Serializable { 025 026 private static final long serialVersionUID = 5290834334572814012L; 027 028 private List<Coord> path; 029 private float[][] lightMap; 030 private int width, height; 031 private double threshold = 0.0; 032 033 public Elias() { 034 } 035 036 public synchronized float[][] lightMap(double startx, double starty, double endx, double endy) { 037 line(startx, starty, endx, endy); 038 return lightMap; 039 } 040 041 /** 042 * Gets the line between the two points. 043 * 044 * @param startx 045 * @param starty 046 * @param endx 047 * @param endy 048 * @return 049 */ 050 public synchronized List<Coord> line(double startx, double starty, double endx, double endy) { 051 path = new LinkedList<>(); 052 width = (int) (Math.max(startx, endx) + 1); 053 height = (int) (Math.max(starty, endy) + 1); 054 lightMap = new float[width][height]; 055 runLine(startx, starty, endx, endy); 056 return path; 057 } 058 /** 059 * Gets the line between the two points. 060 * 061 * @param startx 062 * @param starty 063 * @param endx 064 * @param endy 065 * @param brightnessThreshold between 0.0 (default) and 1.0; only Points with higher brightness will be included 066 * @return 067 */ 068 public synchronized List<Coord> line(double startx, double starty, double endx, double endy, 069 double brightnessThreshold) { 070 threshold = brightnessThreshold; 071 path = new LinkedList<>(); 072 width = (int) (Math.max(startx, endx) + 1); 073 height = (int) (Math.max(starty, endy) + 1); 074 lightMap = new float[width][height]; 075 runLine(startx, starty, endx, endy); 076 return path; 077 } 078 public synchronized List<Coord> line(Coord start, Coord end) { 079 return line(start.x, start.y, end.x, end.y); 080 } 081 public synchronized List<Coord> line(Coord start, Coord end, double brightnessThreshold) { 082 return line(start.x, start.y, end.x, end.y, brightnessThreshold); 083 } 084 085 public synchronized List<Coord> getLastPath() 086 { 087 return path; 088 } 089 090 /** 091 * Marks the location as having the visibility given. 092 * 093 * @param x 094 * @param y 095 * @param c 096 */ 097 private void mark(double x, double y, double c) { 098 //check bounds overflow from antialiasing 099 if (x >= 0 && x < width && y >= 0 && y < height && c > threshold) { 100 path.add(Coord.get((int) x, (int) y)); 101 lightMap[(int) x][(int) y] = (float) c; 102 } 103 } 104 105 private double trunc(double x) { 106 if (x < 0) { 107 return Math.ceil(x); 108 } else { 109 return Math.floor(x); 110 } 111 } 112 113 private double frac(double x) { 114 return x - trunc(x); 115 } 116 117 private double invfrac(double x) { 118 return 1 - frac(x); 119 } 120 121 private void runLine(double startx, double starty, double endx, double endy) { 122 double x1 = startx, y1 = starty, x2 = endx, y2 = endy; 123 double grad, xd, yd, xgap, xend, yend, yf, brightness1, brightness2; 124 int x, ix1, ix2, iy1, iy2; 125 boolean shallow = false; 126 127 xd = x2 - x1; 128 yd = y2 - y1; 129 130 if (Math.abs(xd) > Math.abs(yd)) { 131 shallow = true; 132 } 133 134 if (!shallow) { 135 double temp = x1; 136 x1 = y1; 137 y1 = temp; 138 temp = x2; 139 x2 = y2; 140 y2 = temp; 141 xd = x2 - x1; 142 yd = y2 - y1; 143 } 144 if (x1 > x2) { 145 double temp = x1; 146 x1 = x2; 147 x2 = temp; 148 temp = y1; 149 y1 = y2; 150 y2 = temp; 151 xd = x2 - x1; 152 yd = y2 - y1; 153 } 154 155 grad = yd / xd; 156 157 //add the first end point 158 xend = trunc(x1 + .5); 159 yend = y1 + grad * (xend - x1); 160 161 xgap = invfrac(x1 + .5); 162 163 ix1 = (int) xend; 164 iy1 = (int) yend; 165 166 brightness1 = invfrac(yend) * xgap; 167 brightness2 = frac(yend) * xgap; 168 169 if (shallow) { 170 mark(ix1, iy1, brightness1); 171 mark(ix1, iy1 + 1, brightness2); 172 } else { 173 mark(iy1, ix1, brightness1); 174 mark(iy1 + 1, ix1, brightness2); 175 } 176 177 yf = yend + grad; 178 179 //add the second end point 180 xend = trunc(x2 + .5); 181 yend = y2 + grad * (xend - x2); 182 183 xgap = invfrac(x2 - .5); 184 185 ix2 = (int) xend; 186 iy2 = (int) yend; 187 188 brightness1 = invfrac(yend) * xgap; 189 brightness2 = frac(yend) * xgap; 190 191 if (shallow) { 192 mark(ix2, iy2, brightness1); 193 mark(ix2, iy2 + 1, brightness2); 194 } else { 195 mark(iy2, ix2, brightness1); 196 mark(iy2 + 1, ix2, brightness2); 197 } 198 199 //add the in-between points 200 for (x = ix1 + 1; x < ix2; x++) { 201 brightness1 = invfrac(yf); 202 brightness2 = frac(yf); 203 204 if (shallow) { 205 mark(x, (int) yf, brightness1); 206 mark(x, (int) yf + 1, brightness2); 207 } else { 208 mark((int) yf, x, brightness1); 209 mark((int) yf + 1, x, brightness2); 210 } 211 212 yf += grad; 213 } 214 } 215}