It does, and there are no boundaries 
I think I can think up some special case solution for negative values (when I come back to this, Iām working on other things now)
If you made each region a rectangle and you could see if the line intersects with the rectangles with
Rectangle r = new Rectangle(x,y,width,height);
ArrayList p = new ArrayList();
then make new instances of the point class and add them to the array and have an enhanced for loop go through the points and see if any Rectangle.containsĀ§
problems with this are you need an arraylist for each line and it probably is very slow compared to something but this is super fast to write.
thatās very slow
For anybody using this code as a reference, I just wanted to share with you that the algorithm in the method ālineā doesnāt work at all, sadly. It skips so many pixels that itās not even remotely close to drawing a line. The other algorithm found in this thread, aptly named āline2ā, however, did the job quite nicely, except that it skips the very first pixel, for which Iāll generously provide a patch 
public static interface Plotter{
public void plot(int x, int y);
}
public static final void plot(int x1, int y1, int x2, int y2, int resX, int resY, Plotter plotter) {
@@ if ((x1 | y1 | x2 | y2) < 0) {
@@ throw new IllegalArgumentException();
@@ }
int dist = Math.max(Math.abs(x2 - x1), Math.abs(y2 - y1));
@@ if (dist == 0) {
@@ /* we must not divide by zero (see below)
@@ or we always plot at ((int)NaN,(int)NaN) -> (0,0) */
@@ plotter.plot(x1, y1);
@@ return;
@@ }
float dx = (float) (x2 - x1) / dist;
float dy = (float) (y2 - y1) / dist;
int lastRegX = (int) (x1 + dx + 0.5f) / resX;
int lastRegY = (int) (y1 + dy + 0.5f) / resY;
@@ /* plot the first coordinate */
@@ plotter.plot(lastRegX, 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 / resX;
if (x < 0) {
regX--;
}
int regY = y / resY;
if (y < 0) {
regY--;
}
if (regX != lastRegX || regY != lastRegY) {
plotter.plot(regX, regY);
}
lastRegX = regX;
lastRegY = regY;
}
}
Thanks for doing the grunt work!
Since I tested the approach quite intensively, I am a bit surprised that you find it ānot even remotely close to drawing a lineāā¦
Are you sure you tested the one from this post:
I tested this one: (with resX=32, resY=32)
private static final void line(int x0, int y0, int x1, int y1, int cellWidth, int cellHeight) {
int col0 = x0 / cellWidth;
int row0 = y0 / cellHeight;
int col1 = x1 / cellWidth;
int row1 = y1 / cellHeight;
float m = x0==x1? Integer.MAX_VALUE:(float) (y0 - y1) / (x0 - x1);
float b = y0 - m * x0;
if (Math.abs(m) > 1) {
int lastCol = col0;
int dir = (y0 < y1) ? 1 : -1;
for (int row = row0; (dir==1? row <= row1:row >= row1); row += dir) {
float y = row * cellHeight;
float x = (y - b) / m;
int col = (int) (x + 0.5f * dir) / cellWidth;
if (col != lastCol) {
y = row * cellHeight - dir;
x = (y - b) / m;
int missedCol = (int) (x + 0.5f * dir) / cellWidth;
if (lastCol != missedCol) {
@@ plotter.plot(...);
}
lastCol = col;
}
}
} else {
int lastRow = row0;
int dir = (x0 < x1) ? 1 : -1;
for (int col = col0; (dir==1? col <= col1:col >= col1); col += dir) {
float x = col * cellWidth;
float y = m * x + b;
int row = (int) (y + 0.5f * dir) / cellHeight;
if (row != lastRow) {
x = col * cellWidth - dir;
y = m * x + b;
int missedRow = (int) (y + 0.5f * dir) / cellHeight;
if (lastRow != missedRow) {
@@ plotter.plot(...);
}
lastRow = row;
}
}
}
}
I now see that there is a g.fillRect I missed from the āoriginal codeā ā why anybody would want to benchmark it without that, is beyond me. Anyway, my fault!
public static interface Plotter {
public void plot(int x, int y);
}
public static final void plot(int x1, int y1, int x2, int y2, int resX, int resY, Plotter plotter) {
if ((x1 | y1 | x2 | y2) < 0) {
throw new IllegalArgumentException();
}
int dist = Math.max(Math.abs(x2 - x1), Math.abs(y2 - y1));
if (dist == 0) {
@@ plotter.plot(x1, y1);
return;
}
float dx = (float) (x2 - x1) / dist;
float dy = (float) (y2 - y1) / dist;
int lastRegX = (int) (x1 + dx + 0.5f) / resX;
int lastRegY = (int) (y1 + dy + 0.5f) / resY;
@@ plotter.plot(lastRegX, 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 / resX;
if (x < 0) {
regX--;
}
int regY = y / resY;
if (y < 0) {
regY--;
}
if (regX != lastRegX || regY != lastRegY) {
@@ plotter.plot(regX, regY);
}
lastRegX = regX;
lastRegY = regY;
}
}
public static final void plot2(int x0, int y0, int x1, int y1, int cellWidth, int cellHeight, Plotter plotter) {
boolean skipMissedCells = false;
int col0 = x0 / cellWidth;
int row0 = y0 / cellHeight;
int col1 = x1 / cellWidth;
int row1 = y1 / cellHeight;
// Shitty workaround to prevent division by 0 on x0==x1...
float m = x0 == x1 ? Integer.MAX_VALUE : (float) (y0 - y1) / (x0 - x1);
float b = y0 - m * x0;
// a "steep" line
if (Math.abs(m) > 1) {
int lastCol = col0;
// does it go up or down?
int dir = (y0 < y1) ? 1 : -1;
for (int row = row0; (dir == 1 ? row <= row1 : row >= row1); row += dir) {
float y = row * cellHeight;
float x = (y - b) / m;
int col = (int) (x + 0.5f * dir) / cellWidth;
@@ plotter.plot(col, row);
if (!skipMissedCells && col != lastCol) {
y = row * cellHeight - dir;
x = (y - b) / m;
int missedCol = (int) (x + 0.5f * dir) / cellWidth;
if (lastCol != missedCol) {
@@ plotter.plot(missedCol, (row - dir));
}
lastCol = col;
}
}
} // a "flat" line
else {
int lastRow = row0;
// does it go right or left?
int dir = (x0 < x1) ? 1 : -1;
for (int col = col0; (dir == 1 ? col <= col1 : col >= col1); col += dir) {
float x = col * cellWidth;
float y = m * x + b;
int row = (int) (y + 0.5f * dir) / cellHeight;
@@ plotter.plot(col, row);
if (!skipMissedCells && row != lastRow) {
x = col * cellWidth - dir;
y = m * x + b;
int missedRow = (int) (y + 0.5f * dir) / cellHeight;
if (lastRow != missedRow) {
@@ plotter.plot(col - dir, missedRow);
}
lastRow = row;
}
}
}
}
This is the output from the original test program with my algo at the left using x/yres 32 and a line from 50,50 to 400,300
Can you post your test parameters to verify?
Here is the code (I did not update the line2 though):
import java.awt.Canvas;
import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics;
import javax.swing.JFrame;
import javax.swing.WindowConstants;
public class LineTest
{
private static final int REGION_X = 32;
private static final int REGION_Y = 32;
private static int alternate = 0;
public static void main(String[] args)
{
JFrame frame = new JFrame("Line Test");
frame.setVisible(true);
final int w = 1024;
final int h = 512;
frame.setSize(w, h);
frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
Canvas canvas = new Canvas()
{
@Override
public void paint(Graphics g)
{
g.setFont(new Font("Times New Roman", Font.PLAIN, 9));
int fH = g.getFontMetrics().getHeight();
for (int x = 0; x < w / REGION_X / 2; x++)
{
for (int y = 0; y < h / REGION_Y; y++)
{
if (x % 2 == 0)
if (y % 2 == 1)
g.setColor(Color.red);
else
g.setColor(Color.black);
else if (y % 2 == 0)
g.setColor(Color.red);
else
g.setColor(Color.black);
g.fillRect(x * REGION_X, y * REGION_Y, REGION_X, REGION_Y);
g.setColor(g.getColor() == Color.black ? Color.red : Color.black);
g.drawString(x + ", " + y, x * REGION_X + 2, y * REGION_Y + fH);
}
}
line(50, 50, 400, 300, REGION_X, REGION_Y, g);
g.setColor(Color.white);
g.fillRect(w / 2 - 1, 0, 2, h);
for (int x = w / REGION_X / 2; x < w / REGION_X; x++)
{
for (int y = 0; y < h / REGION_Y; y++)
{
if (x % 2 == 0)
if (y % 2 == 1)
g.setColor(Color.red);
else
g.setColor(Color.black);
else if (y % 2 == 0)
g.setColor(Color.red);
else
g.setColor(Color.black);
g.fillRect(x * REGION_X, y * REGION_Y, REGION_X, REGION_Y);
g.setColor(g.getColor() == Color.black ? Color.red : Color.black);
g.drawString(x + ", " + y, x * REGION_X + 2, y * REGION_Y + fH);
}
}
line2(50 + w / 2, 50, 400 + w / 2, 300, REGION_X, REGION_Y, g);
}
};
canvas.setSize(frame.getSize());
frame.add(canvas);
}
private static final void line(int x0, int y0, int x1, int y1, int cellWidth, int cellHeight, Graphics g) {
// flag to get back the old slightly faster but inaccurate version
boolean skipMissedCells = false;
int alternate = 0;
int col0 = x0 / cellWidth;
int row0 = y0 / cellHeight;
int col1 = x1 / cellWidth;
int row1 = y1 / cellHeight;
// Shitty workaround to prevent division by 0 on x0==x1...
float m = x0==x1? Integer.MAX_VALUE:(float) (y0 - y1) / (x0 - x1);
float b = y0 - m * x0;
// a "steep" line
if (Math.abs(m) > 1) {
int lastCol = col0;
// does it go up or down?
int dir = (y0 < y1) ? 1 : -1;
for (int row = row0; (dir==1? row <= row1:row >= row1); row += dir) {
float y = row * cellHeight;
float x = (y - b) / m;
int col = (int) (x + 0.5f * dir) / cellWidth;
g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
g.fillRect(col * cellWidth, row * cellHeight, cellWidth, cellHeight);
// when the sampled column changes, there might be another missed cell
if (!skipMissedCells && col != lastCol) {
// sample again - slightly before the row boundary
y = row * cellHeight - dir;
x = (y - b) / m;
int missedCol = (int) (x + 0.5f * dir) / cellWidth;
// really missed that one?
if (lastCol != missedCol) {
g.setColor(new Color(127, 127, 0));
// must be (row-dir), since the missed cell belongs to the last sampled row
g.fillRect(missedCol * cellWidth, (row - dir) * cellHeight, cellWidth, cellHeight);
}
lastCol = col;
}
}
} // a "flat" line
else {
int lastRow = row0;
// does it go right or left?
int dir = (x0 < x1) ? 1 : -1;
for (int col = col0; (dir==1? col <= col1:col >= col1); col += dir) {
float x = col * cellWidth;
float y = m * x + b;
int row = (int) (y + 0.5f * dir) / cellHeight;
g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
g.fillRect(col * cellWidth, row * cellHeight, cellWidth, cellHeight);
// when the sampled column changes, there might be another missed cell
if (!skipMissedCells && row != lastRow) {
// sample again - slightly before the column boundary
x = col * cellWidth - dir;
y = m * x + b;
int missedRow = (int) (y + 0.5f * dir) / cellHeight;
// really missed that one?
if (lastRow != missedRow) {
g.setColor(new Color(127, 127, 0));
// must be (col-dir), since the missed cell belongs to the last sampled column
g.fillRect((col - dir) * cellWidth, missedRow * cellHeight, cellWidth, cellHeight);
}
lastRow = row;
}
}
}
g.setColor(Color.pink);
g.drawLine(x0, y0, x1, y1);
}
private static final void line2(int x0, int y0, int x1, int y1, int regionXSize, int regionYSize, Graphics g)
{
boolean steep = Math.abs(y1 - y0) > Math.abs(x1 - x0);
if (steep)
{
int tmp = x0;
x0 = y0;
y0 = tmp;
tmp = x1;
x1 = y1;
y1 = tmp;
}
if (x0 > x1)
{
int tmp = x0;
x0 = x1;
x1 = tmp;
tmp = y0;
y0 = y1;
y1 = tmp;
}
int deltax = x1 - x0;
int deltay = Math.abs(y1 - y0);
int error = deltax / 2;
int ystep = -1;
int y = y0;
if (y0 < y1)
ystep = 1;
for (int x = x0; x <= x1; x++)
{
int absX;
int absY;
if (steep)
{
absX = y;
absY = x;
}
else
{
absX = x;
absY = y;
}
int regX = absX / regionXSize;
int regY = absY / regionYSize;
if (absX < 0)
regX--;
if (absY < 0)
regY--;
g.setColor(alternate++ % 2 == 0 ? Color.green : new Color(0, 127, 0));
g.fillRect(regX * REGION_X, regY * REGION_Y, REGION_X, REGION_Y);
int dX;
int dY;
if (steep)
{
dX = regionYSize - (absY - (regionYSize * regY));
dY = absX - (regionXSize * regX);
}
else
{
dX = regionXSize - (absX - (regionXSize * regX));
dY = absY - (regionYSize * regY);
}
int ceil = x + dX;
for (; x < ceil; x++)
{
error -= deltay;
if (error < 0)
{
y += ystep;
error += deltax;
dY += ystep;
if (dY < 0 || dY > (steep ? regionXSize : regionYSize))
break;
}
}
}
g.setColor(Color.pink);
g.drawLine(x0, y0, x1, y1);
}
}
Actually I hackily switched the test program to your Plotter interface, but still looks good (this time the right green one is mine):
So you might have hit a corner case?
The code:
import javax.swing.*;
import java.awt.*;
public class PlotTest
{
public static interface Plotter {
public void plot(int x, int y);
};
private static int alternate = 0;
public static void main(String[] args)
{
JFrame frame = new JFrame("Line Test");
frame.setVisible(true);
final int xRes = 32;
final int yRes = 32;
final int w = xRes*32;
final int h = yRes*16;
@@ final int x1 = 32;
@@ final int y1 = 64;
@@ final int x2 = 480;
@@ final int y2 = 257;
frame.setSize(w, h);
frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
Canvas canvas = new Canvas()
{
@Override
public void paint(Graphics g1)
{
final Graphics2D g=(Graphics2D)g1;
g.setFont(new Font("Times New Roman", Font.PLAIN, 9));
int fH = g.getFontMetrics().getHeight();
for (int x = 0; x < w / xRes / 2; x++)
{
for (int y = 0; y < h / yRes; y++)
{
if (x % 2 == 0)
if (y % 2 == 1)
g.setColor(Color.red);
else
g.setColor(Color.black);
else if (y % 2 == 0)
g.setColor(Color.red);
else
g.setColor(Color.black);
g.fillRect(x * xRes, y * yRes, xRes, yRes);
g.setColor(g.getColor() == Color.black ? Color.red : Color.black);
g.drawString(x + ", " + y, x * xRes + 2, y * yRes + fH);
}
}
g.setColor(Color.white);
g.fillRect(w / 2 - 1, 0, 2, h);
for (int x = w / xRes / 2; x < w / xRes; x++)
{
for (int y = 0; y < h / yRes; y++)
{
if (x % 2 == 0)
if (y % 2 == 1)
g.setColor(Color.red);
else
g.setColor(Color.black);
else if (y % 2 == 0)
g.setColor(Color.red);
else
g.setColor(Color.black);
g.fillRect(x * xRes, y * yRes, xRes, yRes);
g.setColor(g.getColor() == Color.black ? Color.red : Color.black);
g.drawString(x + ", " + y, x * xRes + 2, y * yRes + fH);
}
}
g.setStroke(new BasicStroke(2.5f));
Plotter plotter1=new Plotter()
{
@Override
public void plot(int x, int y)
{
g.setColor(Color.CYAN);
g.drawRect(x * xRes, y * yRes, xRes, yRes);
}
};
Plotter plotter2=new Plotter()
{
@Override
public void plot(int x, int y)
{
g.setColor(Color.green);
g.drawRect(x * xRes, y * yRes, xRes, yRes);
}
};
@@ PlotTest.plot(x1, y1, x2, y2, xRes, yRes, plotter1);
@@ PlotTest.plot2(x1 + w / 2, y1, x2 + w / 2, y2, xRes, yRes, plotter2);
g.setColor(Color.pink);
g.drawLine(x1, y1, x2, y2);
g.drawLine(x1 + w / 2, y1, x2 + w / 2, y2);
}
};
canvas.setSize(frame.getSize());
frame.add(canvas);
}
public static final void plot(int x1, int y1, int x2, int y2, int resX, int resY, Plotter plotter) {
if ((x1 | y1 | x2 | y2) < 0) {
throw new IllegalArgumentException();
}
int dist = Math.max(Math.abs(x2 - x1), Math.abs(y2 - y1));
if (dist == 0) {
@@ plotter.plot(x1, y1);
return;
}
float dx = (float) (x2 - x1) / dist;
float dy = (float) (y2 - y1) / dist;
int lastRegX = (int) (x1 + dx + 0.5f) / resX;
int lastRegY = (int) (y1 + dy + 0.5f) / resY;
@@ plotter.plot(lastRegX, 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 / resX;
if (x < 0) {
regX--;
}
int regY = y / resY;
if (y < 0) {
regY--;
}
if (regX != lastRegX || regY != lastRegY) {
@@ plotter.plot(regX, regY);
}
lastRegX = regX;
lastRegY = regY;
}
}
public static final void plot2(int x0, int y0, int x1, int y1, int cellWidth, int cellHeight, Plotter plotter) {
boolean skipMissedCells = false;
int col0 = x0 / cellWidth;
int row0 = y0 / cellHeight;
int col1 = x1 / cellWidth;
int row1 = y1 / cellHeight;
// Shitty workaround to prevent division by 0 on x0==x1...
float m = x0 == x1 ? Integer.MAX_VALUE : (float) (y0 - y1) / (x0 - x1);
float b = y0 - m * x0;
// a "steep" line
if (Math.abs(m) > 1) {
int lastCol = col0;
// does it go up or down?
int dir = (y0 < y1) ? 1 : -1;
for (int row = row0; (dir == 1 ? row <= row1 : row >= row1); row += dir) {
float y = row * cellHeight;
float x = (y - b) / m;
int col = (int) (x + 0.5f * dir) / cellWidth;
@@ plotter.plot(col, row);
if (!skipMissedCells && col != lastCol) {
y = row * cellHeight - dir;
x = (y - b) / m;
int missedCol = (int) (x + 0.5f * dir) / cellWidth;
if (lastCol != missedCol) {
@@ plotter.plot(missedCol, (row - dir));
}
lastCol = col;
}
}
} // a "flat" line
else {
int lastRow = row0;
// does it go right or left?
int dir = (x0 < x1) ? 1 : -1;
for (int col = col0; (dir == 1 ? col <= col1 : col >= col1); col += dir) {
float x = col * cellWidth;
float y = m * x + b;
int row = (int) (y + 0.5f * dir) / cellHeight;
@@ plotter.plot(col, row);
if (!skipMissedCells && row != lastRow) {
x = col * cellWidth - dir;
y = m * x + b;
int missedRow = (int) (y + 0.5f * dir) / cellHeight;
if (lastRow != missedRow) {
@@ plotter.plot(col - dir, missedRow);
}
lastRow = row;
}
}
}
}
}
Ofcourse I make my tests interactive, so I can test more than a handful of hardcoded examples.
In about 80% of the cases your code provides the correct path.
If youāre looking for an antialiased line, thereās always Wuās algorithm, or Hugo Eliasās take on it:
Here is a plotter that supports negative values and doesnāt have faulty edge cases.
Using your last code, these (and many more) result in incorrect plotting:
(55,46) -> (120,140) (195,404) -> (81,498) (218,557) -> (67,427) (218,557) -> (100,423) (60,403) -> (77,355) (299,551) -> (203,487)
Ah, ok - I occasionally āattachā the missed grid cells at the wrong side of the found one. I probably wonāt put any effort into fixing this, since I doubt it will beat your implementation.