gdx/src/com/badlogic/gdx/math/Bresenham2.java

   1 package com.badlogic.gdx.math;
   2
   3 import com.badlogic.gdx.utils.Array;
   4 import com.badlogic.gdx.utils.Pool;
   5
   6 /**
   7  * Returns a list of points at integer coordinates for
   8  * a line on a 2D grid, using the Bresenham algorithm.<p>
   9  *
  10  * Instances of this class own the returned array of points and the points
  11  * themselves to avoid garbage collection as much as possible. Calling
  12  * any of the methods will result in the reuse of the previously returned array and vectors, expect
  13  * @author badlogic
  14  *
  15  */
  16 public class Bresenham2 {
  17         private final Array<GridPoint2> points = new Array<GridPoint2>();
  18         private final Pool<GridPoint2> pool = new Pool<GridPoint2>() {
  19                 @Override
  20                 protected GridPoint2 newObject () {
  21                         return new GridPoint2();
  22                 }
  23         };
  24
  25         /**
  26          * Returns a list of {@link GridPoint2} instances along the given line, at integer coordinates.
  27          * @param start the start of the line
  28          * @param end the end of the line
  29          * @return the list of points on the line at integer coordinates
  30          */
  31         public Array<GridPoint2> line(GridPoint2 start, GridPoint2 end) {
  32                 return line(start.x, start.y, end.y, end.y);
  33         }
  34
  35         /**
  36          * Returns a list of {@link GridPoint2} instances along the given line, at integer coordinates.
  37          * @param startX the start x coordinate of the line
  38          * @param startY the start y coordinate of the line
  39          * @param endX the end x coordinate of the line
  40          * @param endY the end y coordinate of the line
  41          * @return the list of points on the line at integer coordinates
  42          */
  43         public Array<GridPoint2> line(int startX, int startY, int endX, int endY) {
  44                 pool.freeAll(points);
  45                 points.clear();
  46                 return line(startX, startY, endX, endY, pool, points);
  47         }
  48
  49         /**
  50          * Returns a list of {@link GridPoint2} instances along the given line, at integer coordinates.
  51          * @param startX the start x coordinate of the line
  52          * @param startY the start y coordinate of the line
  53          * @param endX the end x coordinate of the line
  54          * @param endY the end y coordinate of the line
  55          * @param pool the pool from which GridPoint2 instances are fetched
  56          * @param output the output array, will be cleared in this method
  57          * @return the list of points on the line at integer coordinates
  58          */
  59         public Array<GridPoint2> line(int startX, int startY, int endX, int endY, Pool<GridPoint2> pool, Array<GridPoint2> output) {
  60
  61                 int w = endX - startX;
  62                 int h = endY - startY;
  63                 int dx1 = 0, dy1 = 0, dx2 = 0, dy2 = 0;
  64                 if(w < 0) {
  65                         dx1 = -1;
  66                         dx2 = -1;
  67                 } else if(w > 0) {
  68                         dx1 = 1;
  69                         dx2 = 1;
  70                 }
  71                 if(h < 0) dy1 = -1; else if(h > 0) dy1 = 1;
  72                 int longest = Math.abs(w);
  73                 int shortest = Math.abs(h);
  74                 if(longest <= shortest) {
  75                         longest = Math.abs(h);
  76                         shortest = Math.abs(w);
  77                         if(h < 0) dy2 = -1; else if(h > 0) dy2 = 1;
  78                         dx2 = 0;
  79                 }
  80                 int numerator = longest >> 1;
  81                 for(int i = 0; i <= longest; i++) {
  82                         GridPoint2 point = pool.obtain();
  83                         point.set(startX, startY);
  84                         output.add(point);
  85                         numerator += shortest;
  86                         if(numerator > longest) {
  87                                 numerator -= longest;
  88                                 startX += dx1;
  89                                 startY += dy1;
  90                         } else {
  91                                 startX += dx2;
  92                                 startY += dy2;
  93                         }
  94                 }
  95                 return output;
  96         }
  97 }