Line Logic

counterp · August 9, 2011, 8:43pm

Is there anyway to get it wholly accurate.

Consider the arguments: line(45, 45, 300, 12, REGION_X, REGION_Y, g);

It is just barely in region (8, 1) but the method doesn’t flag this region.

Or will it never happen because of using floats?

I fixed the accuracy problem with my version

    private static final void line(int x0, int y0, int x1, int y1, int regionXSize, int regionYSize, Graphics g) {
    	int alternate = 0;
    	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);
            System.out.println(regX + " " + regY);
            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 - 1;
            for (; x < ceil; x++) {
                error -= deltay;
                if (error < 0) {
                    y += ystep;
                    error += deltax;
                    dY += ystep;
                    if (dY <= -1 || dY >= (steep ? regionXSize : regionYSize))
                        break;
                }
            }
        }
    }

cylab · August 9, 2011, 9:30pm

Yeah, the float to int casting always rounds down, while the drawLine() rounds more accurate. I simply added a 0.5f bias before casting - that should do the trick. I also fixed an error where the missed cells don’t get detected correctly on negative direction:


    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;
          
        // fill start and end cell
        g.setColor(new Color(0, 127,127));
        g.fillRect(col0 * cellWidth, row0 * cellHeight, cellWidth, cellHeight);
        g.fillRect(col1 * cellWidth, row1 * cellHeight, cellWidth, cellHeight);
        
        float m=(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; 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; 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);
    }

counterp · August 9, 2011, 9:41pm

line(0, 0, 400, 390, REGION_X, REGION_Y, g);

cuts off the last box after changing rows (15, 15)

I wish I knew how your code worked so I could do these changes myself but I could never quite wrap my head around this kind of geometry :\

well thanks for your help so far

cylab · August 9, 2011, 9:54pm

btw. did some benchmarking:


Tested line1 (cylab), 3000000 iterations. Took 869ms
Tested line2 (counterp), 3000000 iterations. Took 3185ms

Edit: Just found some infinite loop with my implementation on some values, so needs more work.

cylab · August 9, 2011, 9:58pm

That’s because the missing match check is not done for the endpoint (since it is calculated beforehand and not in the loop)

counterp · August 10, 2011, 12:58am

Ahh well it was an easy enough fix.

Is the infinite loop in the current version you posted? If so, when does it occur?

namrog84 · August 10, 2011, 1:21pm

arghh cylab!

hate you! :cranky:
I was thinking last night this morning, it finally came to me to use a slope with a xSpacingStepping or for y and do it that way. I am all excited coming into work, and then boom. You come out of no where and present exactly what I had been all excited to write!
;D arghhh! ???

counterp · August 10, 2011, 3:39pm

well his still has an infinite loop glitch and still doesn’t work with negatives if you want to give it a shot

cylab · August 10, 2011, 8:51pm

fixed infinite loop
fixed last missed cell
work accurate with x0 > x1, x0 < x1, y0 > y1, y0 < y1
won’t explode on x0==x1 (quickfix - should be an own special case)


  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);
  }

benchmarked with


    int iter=3000000;
    {
      long start=System.nanoTime();
      for(int i=0; i<iter; i++)
      {
        int x0 = (int) (Math.random()*1000);
        int y0 = (int) (Math.random()*1000);
        int x1 = (int) (Math.random()*1000);
        int y1 = (int) (Math.random()*1000);
        line1(x0, y0, x1, y1, REGION_X, REGION_Y);
      }
      long end=System.nanoTime();
      System.out.println("Tested line1 (cylab), "+iter+" iterations. Took "+(end-start)/1000000+"ms");
    }
    {
      long start=System.nanoTime();
      for(int i=0; i<iter; i++)
      {
        int x0 = (int) (Math.random()*1000);
        int y0 = (int) (Math.random()*1000);
        int x1 = (int) (Math.random()*1000);
        int y1 = (int) (Math.random()*1000);
        line2(x0, y0, x1, y1, REGION_X, REGION_Y);
      }
      long end=System.nanoTime();
      System.out.println("Tested line2 (counterp), "+iter+" iterations. Took "+(end-start)/1000000+"ms");
    }

(removed all graphics for benchmarking)

Result


Tested line1 (cylab), 3000000 iterations. Took 637ms
Tested line2 (counterp), 3000000 iterations. Took 8127ms

counterp · August 11, 2011, 5:41pm

EDIT: must fix bug

cylab · August 11, 2011, 5:53pm

Looks nice, but:


Tested line1 (cylab), 3000000 iterations. Took 619ms
Tested line2 (counterp), 3000000 iterations. Took 7857ms
Tested line3 (counterp), 3000000 iterations. Took 25071ms (!)

counterp · August 11, 2011, 6:06pm

Sorry there was a bug with it. here’s updated one:

	private static final void line2(int x1, int y1, int x2, int y2, int resX, int resY) {
		int dist = Math.max(Math.abs(x2-x1),Math.abs(y2-y1));
		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;
		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) {
				
			}
			lastRegX = regX;
			lastRegY = regY;
		}
	}

I honestly have no idea what caused it to be insanely slow. Compare the above with this in a benchmark:

	private static final void line2(int x1, int y1, int x2, int y2, int resX, int resY) {
		int dist = Math.max(Math.abs(x2-x1),Math.abs(y2-y1));
		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;
		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) {
				lastRegX = regX;
				lastRegY = regY;
			}
		}
	}

isn’t that crazy weird, or am I missing something?

namrog84 · August 11, 2011, 6:08pm

Tested most recent cylab and counterp

Tested line1 (cylab), 3000000 iterations. Took 2449ms
Tested line2 (counterp), 3000000 iterations. Took 11980ms

However, because I personally feel that they should be checking against the same x0,x0,x1,y1 because if you are doing a speed test, you need to check against SAME numbers, at least in my opinion. So giving different random numbers to each is a bad idea in my opinion. arghh wordy

anyways
I extracted the randomness


for(int i=0;i<iter;i++){
    x0[i] = (int) (Math.random()*1000);
    y0[i] = (int) (Math.random()*1000);
    x1[i] = (int) (Math.random()*1000);
    y1[i] = (int) (Math.random()*1000);
}

Then I ran the tests using the exact same numbers
Tested line1 (cylab), 3000000 iterations. Took 1925ms
Tested line2 (counterp), 3000000 iterations. Took 11438ms

saw a 500ms increase
so in my opinion these are more accurate speed of the tests, because in real world you should already have existing numbers not generate numbers for the sake of the test

edit: snipped

edit2x: counterp sometimes your code gives me a divide by zero error (It only occurs when the line is a dot i.e. 885 125 885 125) so I think its a non issue personally.

Work computer is: Intel core i7 860 2.8ghz with 8gb of ram on 64 bit OS
I don’t know how your guys numbers are so much lower than mine. I do have a lot of things open but minimal background cpu usage

counterp · August 11, 2011, 6:11pm

really? I’m getting that mine is faster :\

and you have to cast it or else it will end up dividing integers which will give an integer


public class Benchmark {

	public static void main(String[] args) {
		long start, end;
		double trials = 10000000;
		int[][] lines = new int[4][(int) trials];
		for (int n = 0; n < 4; n++)
			for (int i = 0; i < lines.length; i++) {
				lines[n][i] = (int) (Math.random() * 1000);
			}

		start = System.nanoTime();
		for (int i = 0; i < trials; i++)
			line(lines[0][i], lines[1][i], lines[2][i], lines[3][i], 25, 25);
		end = System.nanoTime();
		System.out.println("Test 1: " + ((end - start) / 1000000D));

		start = System.nanoTime();
		for (int i = 0; i < trials; i++)
			line2(lines[0][i], lines[1][i], lines[2][i], lines[3][i], 25, 25);
		end = System.nanoTime();
		System.out.println("Test 2: " + ((end - start) / 1000000D));
	}

	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) {
					}
					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) {
					}
					lastRow = row;
				}
			}
		}
	}

	private static final void line2(int x1, int y1, int x2, int y2, int resX, int resY) {
		int dist = Math.max(Math.abs(x2-x1),Math.abs(y2-y1));
		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;
		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) {
			}
			lastRegX = regX;
			lastRegY = regY;
		}
	}

}

is there something wrong with this benchmark? and can any one else test it to see if they got same results?

namrog84 · August 11, 2011, 6:19pm

counterp: what is the purpose of the if in your “updated” code? if in your old code I understand, but not newer


if (regX != lastRegX || regY != lastRegY) {
             
}
lastRegX = regX;
lastRegY = regY;


if (regX != lastRegX || regY != lastRegY) {
     lastRegX = regX;
     lastRegY = regY;
}

snipped/ question resolved

edit:
counter in your above posted code
Test 1: 246.949836
Test 2: 1400.469944

counterp · August 11, 2011, 6:23pm

That’s where the region code is supposed to go (removed for the benchmark, just left the if-statement because that should be part of the benchmark:


if (regX != lastRegX || regY != lastRegY) {
     Region.register(regX, regY);
}
lastRegX = regX;
lastRegY = regY;


if (regX != lastRegX || regY != lastRegY) {
     Region.register(regX, regY);
     lastRegX = regX;
     lastRegY = regY;
}

but for some odd reason the second one is extremely slow on my computer as compared to the first one??? I am befuddled… Can you run my benchmark and give me your results?

EDIT: ok what can be wrong with my JVM -.- why is it telling me second one is faster

namrog84 · August 11, 2011, 6:31pm

counterp

for me to make your test faster I must change this:


float lastRegX = (x1 + dx + 0.5f) / resX;
float lastRegY = (y1 + dy + 0.5f) / resY;

from this:


int lastRegX = (int) (x1 + dx + 0.5f) / resX;
int lastRegY = (int) (y1 + dy + 0.5f) / resY;

I removed the int and int cast.
Can you not cast the int? or use another way of doing it, because that (int) cast is the major bottleneck.

(cylab?) Test 1: 243.20876
(counterp?) Test 2: 129.626574

(cylab?) Test 1: 254.693393
(counterp?) Test 2: 1398.737626 [ this is with the (int) cast ]

cylab · August 11, 2011, 6:33pm

I think we have to store the actual values, not that the benchmark is flawed by the jvm removing “unneccessary” calculations.

counterp · August 11, 2011, 7:07pm

you know what, I don’t even care

if this region thing becomes a problem later on, I’ll fix it then :yawn:

all that’s left to do now is figured out how to make your method work with negative values :\

cylab · August 12, 2011, 8:04am

Does it really have to? If so I could think of offsetting coords like


x = x+maxNegativeCols*cellWidth;
y = y+maxNegativeRows*cellHeight;

and substract that from the result


col-=maxNegativeCols;
row-=maxNegativeRows;