Usage:
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:
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;
}
plotting 1048576 lines in 256x256 grid (array) took: 485ms
plotting 1048576 lines in 256x256 grid (ref.impl) took: 10348ms