Line -> Grid intersection code (all plotted cells directly connected)

Usage:

1
2
3
4
5
6
7

int[] xy = new int[...];
int len = LineGridIntersection.plot(xSrc, ySrc, xDest, yDest, TILE_SIZE, TILE_SIZE, xy];
for(int i=0; i<len; i++) {
   int x = xy[i*2+0];
   int y = xy[i*2+1];
   // ...
}

Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

   public static int plot(int x1, int y1, int x2, int y2, int wCell, int hCell, int[] xy) {
      // support negative input values
      int xOffset = (-Math.min(0, Math.min(x1, x2)) + wCell - 1) / -wCell;
      int yOffset = (-Math.min(0, Math.min(y1, y2)) + hCell - 1) / -hCell;
      x1 -= xOffset * wCell;
      y1 -= yOffset * hCell;
      x2 -= xOffset * wCell;
      y2 -= yOffset * hCell;
      assert (x1 | y1 | x2 | y2) >= 0;

      // ensure x1 <= x2
      if (x1 > x2) {
         int t;

         t = x1;
         x1 = x2;
         x2 = t;

         t = y1;
         y1 = y2;
         y2 = t;
      }

      int p = 0;

      int xCell1 = (int) ((x1 + 0.5f) / wCell);
      int yCell1 = (int) ((y1 + 0.5f) / hCell);
      int xCell2 = (int) ((x2 + 0.5f) / wCell);
      int yCell2 = (int) ((y2 + 0.5f) / hCell);

      int yMin = Math.min(y1, y2);
      int yMax = Math.max(y1, y2);
      int yCellMin = Math.min(yCell1, yCell2);
      int yCellMax = Math.max(yCell1, yCell2);

      if (xCell1 == xCell2) {
         // handle vertical line
         for (int yCell = yCellMin; yCell <= yCellMax; yCell++) {
            xy[p++] = xOffset + xCell1;
            xy[p++] = yOffset + yCell;
         }
      } else if (yCell1 == yCell2) {
         // handle horizontal line
         for (int xCell = xCell1; xCell <= xCell2; xCell++) {
            xy[p++] = xOffset + xCell;
            xy[p++] = yOffset + yCell1;
         }
      } else {
         // handle diagonal line
         int xCell = xCell1;
         int yCell = yCell1;

         // calculate normal of path
         double nx, ny;
         {
            double dx = x2 - x1;
            double dy = y2 - y1;
            double dist = Math.sqrt(dx * dx + dy * dy);
            nx = dx / dist;
            ny = dy / dist;
         }

         final double advancePerCell = wCell / nx;

         double firstStepRatio = (((xCell + 1) * wCell) - (double) x1) / wCell;
         double x = x1 + nx * advancePerCell * firstStepRatio;
         double y = y1 + ny * advancePerCell * firstStepRatio;

         while (true) {
            // handle cases where adjecent cells are also touched
            //  - this happens when we advanced a cell and the Y-cell doesn't have the expected value 
            if (ny > 0.0f) {
               for (int yEnd = Math.min((int) y / hCell - 1, yCell2); yCell <= yEnd; yCell++) {
                  xy[p++] = xOffset + xCell;
                  xy[p++] = yOffset + yCell;
               }
            } else {
               for (int yOff = Math.max((int) y / hCell - 0, yCell2); yCell > yOff; yCell--) {
                  xy[p++] = xOffset + xCell;
                  xy[p++] = yOffset + yCell;
               }
            }

            if (x >= x2 || y <= yMin || y >= yMax) {
               break;
            }

            // advance with 1 cell
            x += nx * advancePerCell;
            y += ny * advancePerCell;

            xy[p++] = xOffset + xCell++;
            xy[p++] = yOffset + yCell;
         }

         // handle last cell
         if (p == 0 || xy[p - 2] != xOffset + xCell2 || xy[p - 1] != yOffset + yCell2) {
            xy[p++] = xOffset + xCell2;
            xy[p++] = yOffset + yCell2;
         }
      }

      return p >> 1;
   }

   public static final int plotReferenceImpl(int x1, int y1, int x2, int y2, int wCell, int hCell, int[] xy) {
      // support negative input values
      int xOffset = (-Math.min(0, Math.min(x1, x2)) + wCell - 1) / -wCell;
      int yOffset = (-Math.min(0, Math.min(y1, y2)) + hCell - 1) / -hCell;
      x1 -= xOffset * wCell;
      y1 -= yOffset * hCell;
      x2 -= xOffset * wCell;
      y2 -= yOffset * hCell;
      assert (x1 | y1 | x2 | y2) >= 0;

      int p = 0;

      int dist = Math.max(Math.abs(x2 - x1), Math.abs(y2 - y1));
      if (dist == 0) {
         xy[p++] = xOffset + x1;
         xy[p++] = yOffset + x2;
      } else {
         float dx = (float) (x2 - x1) / dist;
         float dy = (float) (y2 - y1) / dist;
         int lastRegX = (int) (x1 + dx + 0.5f) / wCell;
         int lastRegY = (int) (y1 + dy + 0.5f) / hCell;

         xy[p++] = xOffset + lastRegX;
         xy[p++] = yOffset + lastRegY;

         for (int d = 2; d <= dist; d++) {
            int x = (int) (x1 + 0.5f + dx * d);
            int y = (int) (y1 + 0.5f + dy * d);
            int regX = x / wCell;
            int regY = y / hCell;
            if (regX != lastRegX || regY != lastRegY) {
               xy[p++] = xOffset + regX;
               xy[p++] = yOffset + regY;
            }
            lastRegX = regX;
            lastRegY = regY;
         }
      }

      return p >> 1;
   }

1 2	plotting 1048576 lines in 256x256 grid (array) took: 485ms plotting 1048576 lines in 256x256 grid (ref.impl) took: 10348ms