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