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}