@Test public void getLineGridIntersectionVerify() throws Exception { for (int j = 0; j < 1000000; j++) { if (j % 1000 == 0) { System.out.println(":: " + j); } Random rand = new Random(j); float xf1 = rand.nextInt(512) - 0.5f; float yf1 = rand.nextInt(512) - 0.5f; float xf2 = rand.nextInt(512) - 0.5f; float yf2 = rand.nextInt(512) - 0.5f; int[][] result = G2DUtil.getLineGridIntersection( (int) (xf1 + 0.5f), (int) (yf1 + 0.5f), (int) (xf2 + 0.5f), (int) (yf2 + 0.5f) ); Arrays.sort(result, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { int sign = o1[0] - o2[0]; if (sign != 0) { return sign; } else { return o1[1] - o2[1]; } } }); ArrayList<int[]> saveResult = new ArrayList<int[]>(); for (float x = Math.min(xf1,xf2) - 1; x <= Math.max(xf1,xf2); x++) { for (float y = Math.min(yf1,yf2) - 1; y <= Math.max(yf1,yf2); y++) { if (intersects(xf1, yf1, xf2, yf2, x, y)) { saveResult.add(new int[]{(int) (x + 0.5f), (int) (y + 0.5f)}); } } } int[][] saveResultArray = new int[saveResult.size()][2]; saveResult.toArray(saveResultArray); Arrays.sort(saveResultArray, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { int sign = o1[0] - o2[0]; if (sign != 0) { return sign; } else { return o1[1] - o2[1]; } } }); assert result.length == saveResultArray.length; for (int i = 0; i < result.length; i++) { assert result[i][0] == saveResultArray[i][0]; assert result[i][1] == saveResultArray[i][1]; } } }
public static int[][] getLineGridIntersection(int x1, int y1, int x2, int y2) { if (y1 == y2 && x1 == x2) { int[][] result = new int[4][2]; result[0][0] = x1; result[0][1] = y1; result[1][0] = x1 - 1; result[1][1] = y1; result[2][0] = x1; result[2][1] = y1 - 1; result[3][0] = x1 - 1; result[3][1] = y1 - 1; return result; } if (y1 == y2) { int[][] result = new int[Math.abs(x2-x1)*2][2]; int i = 0; for (int x = Math.min(x1,x2), max = Math.max(x1, x2); x < max; x++) { result[i][0] = x; result[i++][1] = y1; result[i][0] = x; result[i++][1] = y1 - 1; } return result; } if (x1 == x2) { int[][] result = new int[Math.abs(y2-y1)*2][2]; int i = 0; for (int y = Math.min(y1,y2), max = Math.max(y1, y2); y < max; y++) { result[i][0] = x1; result[i++][1] = y; result[i][0] = x1 - 1; result[i++][1] = y; } return result; } ArrayList<int[]> result = new ArrayList<int[]>(); int stepX = (x2 > x1) ? 1 : -1; int stepY = (y2 > y1) ? 1 : -1; int x = x1 + (stepX == 1 ? 0 : -1); int y = y1 + (stepY == 1 ? 0 : -1); int stopX = x2 + (stepX == 1 ? -1 : 0); int stopY = y2 + (stepY == 1 ? -1 : 0); double val = Math.abs((y2 - y1) / (double)(x2 - x1)); int tMaxX = 1; int tMaxY = 1; result.add(new int[] {x, y}); while ( ((stepX == 1 && x < stopX) || (stepX == -1 && x > stopX)) || ((stepY == 1 && y < stopY) || (stepY == -1 && y > stopY)) ) { double cTMaxX = val * tMaxX - tMaxY; if (Math.abs(cTMaxX) < 0.0000000001) { tMaxX++; tMaxY++; x = x + stepX; y = y + stepY; } else if (cTMaxX < 0) { tMaxX++; x = x + stepX; } else { tMaxY++; y = y + stepY; } result.add(new int[] {x, y}); } int[][] resultArray = new int[result.size()][2]; result.toArray(resultArray); return resultArray; }
G2DUtil { public static int[][] getLineGridIntersection(int x1, int y1, int x2, int y2) { if (y1 == y2 && x1 == x2) { int[][] result = new int[4][2]; result[0][0] = x1; result[0][1] = y1; result[1][0] = x1 - 1; result[1][1] = y1; result[2][0] = x1; result[2][1] = y1 - 1; result[3][0] = x1 - 1; result[3][1] = y1 - 1; return result; } if (y1 == y2) { int[][] result = new int[Math.abs(x2-x1)*2][2]; int i = 0; for (int x = Math.min(x1,x2), max = Math.max(x1, x2); x < max; x++) { result[i][0] = x; result[i++][1] = y1; result[i][0] = x; result[i++][1] = y1 - 1; } return result; } if (x1 == x2) { int[][] result = new int[Math.abs(y2-y1)*2][2]; int i = 0; for (int y = Math.min(y1,y2), max = Math.max(y1, y2); y < max; y++) { result[i][0] = x1; result[i++][1] = y; result[i][0] = x1 - 1; result[i++][1] = y; } return result; } ArrayList<int[]> result = new ArrayList<int[]>(); int stepX = (x2 > x1) ? 1 : -1; int stepY = (y2 > y1) ? 1 : -1; int x = x1 + (stepX == 1 ? 0 : -1); int y = y1 + (stepY == 1 ? 0 : -1); int stopX = x2 + (stepX == 1 ? -1 : 0); int stopY = y2 + (stepY == 1 ? -1 : 0); double val = Math.abs((y2 - y1) / (double)(x2 - x1)); int tMaxX = 1; int tMaxY = 1; result.add(new int[] {x, y}); while ( ((stepX == 1 && x < stopX) || (stepX == -1 && x > stopX)) || ((stepY == 1 && y < stopY) || (stepY == -1 && y > stopY)) ) { double cTMaxX = val * tMaxX - tMaxY; if (Math.abs(cTMaxX) < 0.0000000001) { tMaxX++; tMaxY++; x = x + stepX; y = y + stepY; } else if (cTMaxX < 0) { tMaxX++; x = x + stepX; } else { tMaxY++; y = y + stepY; } result.add(new int[] {x, y}); } int[][] resultArray = new int[result.size()][2]; result.toArray(resultArray); return resultArray; } }
G2DUtil { public static int[][] getLineGridIntersection(int x1, int y1, int x2, int y2) { if (y1 == y2 && x1 == x2) { int[][] result = new int[4][2]; result[0][0] = x1; result[0][1] = y1; result[1][0] = x1 - 1; result[1][1] = y1; result[2][0] = x1; result[2][1] = y1 - 1; result[3][0] = x1 - 1; result[3][1] = y1 - 1; return result; } if (y1 == y2) { int[][] result = new int[Math.abs(x2-x1)*2][2]; int i = 0; for (int x = Math.min(x1,x2), max = Math.max(x1, x2); x < max; x++) { result[i][0] = x; result[i++][1] = y1; result[i][0] = x; result[i++][1] = y1 - 1; } return result; } if (x1 == x2) { int[][] result = new int[Math.abs(y2-y1)*2][2]; int i = 0; for (int y = Math.min(y1,y2), max = Math.max(y1, y2); y < max; y++) { result[i][0] = x1; result[i++][1] = y; result[i][0] = x1 - 1; result[i++][1] = y; } return result; } ArrayList<int[]> result = new ArrayList<int[]>(); int stepX = (x2 > x1) ? 1 : -1; int stepY = (y2 > y1) ? 1 : -1; int x = x1 + (stepX == 1 ? 0 : -1); int y = y1 + (stepY == 1 ? 0 : -1); int stopX = x2 + (stepX == 1 ? -1 : 0); int stopY = y2 + (stepY == 1 ? -1 : 0); double val = Math.abs((y2 - y1) / (double)(x2 - x1)); int tMaxX = 1; int tMaxY = 1; result.add(new int[] {x, y}); while ( ((stepX == 1 && x < stopX) || (stepX == -1 && x > stopX)) || ((stepY == 1 && y < stopY) || (stepY == -1 && y > stopY)) ) { double cTMaxX = val * tMaxX - tMaxY; if (Math.abs(cTMaxX) < 0.0000000001) { tMaxX++; tMaxY++; x = x + stepX; y = y + stepY; } else if (cTMaxX < 0) { tMaxX++; x = x + stepX; } else { tMaxY++; y = y + stepY; } result.add(new int[] {x, y}); } int[][] resultArray = new int[result.size()][2]; result.toArray(resultArray); return resultArray; }  }
G2DUtil { public static int[][] getLineGridIntersection(int x1, int y1, int x2, int y2) { if (y1 == y2 && x1 == x2) { int[][] result = new int[4][2]; result[0][0] = x1; result[0][1] = y1; result[1][0] = x1 - 1; result[1][1] = y1; result[2][0] = x1; result[2][1] = y1 - 1; result[3][0] = x1 - 1; result[3][1] = y1 - 1; return result; } if (y1 == y2) { int[][] result = new int[Math.abs(x2-x1)*2][2]; int i = 0; for (int x = Math.min(x1,x2), max = Math.max(x1, x2); x < max; x++) { result[i][0] = x; result[i++][1] = y1; result[i][0] = x; result[i++][1] = y1 - 1; } return result; } if (x1 == x2) { int[][] result = new int[Math.abs(y2-y1)*2][2]; int i = 0; for (int y = Math.min(y1,y2), max = Math.max(y1, y2); y < max; y++) { result[i][0] = x1; result[i++][1] = y; result[i][0] = x1 - 1; result[i++][1] = y; } return result; } ArrayList<int[]> result = new ArrayList<int[]>(); int stepX = (x2 > x1) ? 1 : -1; int stepY = (y2 > y1) ? 1 : -1; int x = x1 + (stepX == 1 ? 0 : -1); int y = y1 + (stepY == 1 ? 0 : -1); int stopX = x2 + (stepX == 1 ? -1 : 0); int stopY = y2 + (stepY == 1 ? -1 : 0); double val = Math.abs((y2 - y1) / (double)(x2 - x1)); int tMaxX = 1; int tMaxY = 1; result.add(new int[] {x, y}); while ( ((stepX == 1 && x < stopX) || (stepX == -1 && x > stopX)) || ((stepY == 1 && y < stopY) || (stepY == -1 && y > stopY)) ) { double cTMaxX = val * tMaxX - tMaxY; if (Math.abs(cTMaxX) < 0.0000000001) { tMaxX++; tMaxY++; x = x + stepX; y = y + stepY; } else if (cTMaxX < 0) { tMaxX++; x = x + stepX; } else { tMaxY++; y = y + stepY; } result.add(new int[] {x, y}); } int[][] resultArray = new int[result.size()][2]; result.toArray(resultArray); return resultArray; }  static void drawPoint(SimpleVector point,
                                 Graphics2D ig, Color innerColor, Color outerColor,
                                 float radius, float borderSize); static void drawLine(SimpleVector p1, SimpleVector p2,
                                Graphics2D ig, Color innerColor, Color outerColor,
                                float size); static float[] lineIntersection(
            float x1, float y1, float x2, float y2,
            float x3, float y3, float x4, float y4,
            boolean includeEndPoints
    ); static float[] lineIntersection(
            int x1, int y1, int x2, int y2,
            int x3, int y3, int x4, int y4,
            boolean includeEndPoints
    ); static boolean onLine(double ax, double ay, double bx, double by, double cx, double cy); static boolean parallel(float x1, float y1, float x2, float y2,
                                   float x3, float y3, float x4, float y4); static boolean inTriangle(float px, float py,
                                          float p0x, float p0y, float p1x, float p1y, float p2x, float p2y); static int[][] getLineGridIntersection(int x1, int y1, int x2, int y2); static int[][] getTriangleGridIntersection(int x1, int y1, int x2, int y2, int x3, int y3); static int[][] getLineGridIntersection(double x1, double y1, double x2, double y2); static int[][] getTriangleGridIntersection(double x1, double y1, double x2, double y2, double x3, double y3); }
G2DUtil { public static int[][] getLineGridIntersection(int x1, int y1, int x2, int y2) { if (y1 == y2 && x1 == x2) { int[][] result = new int[4][2]; result[0][0] = x1; result[0][1] = y1; result[1][0] = x1 - 1; result[1][1] = y1; result[2][0] = x1; result[2][1] = y1 - 1; result[3][0] = x1 - 1; result[3][1] = y1 - 1; return result; } if (y1 == y2) { int[][] result = new int[Math.abs(x2-x1)*2][2]; int i = 0; for (int x = Math.min(x1,x2), max = Math.max(x1, x2); x < max; x++) { result[i][0] = x; result[i++][1] = y1; result[i][0] = x; result[i++][1] = y1 - 1; } return result; } if (x1 == x2) { int[][] result = new int[Math.abs(y2-y1)*2][2]; int i = 0; for (int y = Math.min(y1,y2), max = Math.max(y1, y2); y < max; y++) { result[i][0] = x1; result[i++][1] = y; result[i][0] = x1 - 1; result[i++][1] = y; } return result; } ArrayList<int[]> result = new ArrayList<int[]>(); int stepX = (x2 > x1) ? 1 : -1; int stepY = (y2 > y1) ? 1 : -1; int x = x1 + (stepX == 1 ? 0 : -1); int y = y1 + (stepY == 1 ? 0 : -1); int stopX = x2 + (stepX == 1 ? -1 : 0); int stopY = y2 + (stepY == 1 ? -1 : 0); double val = Math.abs((y2 - y1) / (double)(x2 - x1)); int tMaxX = 1; int tMaxY = 1; result.add(new int[] {x, y}); while ( ((stepX == 1 && x < stopX) || (stepX == -1 && x > stopX)) || ((stepY == 1 && y < stopY) || (stepY == -1 && y > stopY)) ) { double cTMaxX = val * tMaxX - tMaxY; if (Math.abs(cTMaxX) < 0.0000000001) { tMaxX++; tMaxY++; x = x + stepX; y = y + stepY; } else if (cTMaxX < 0) { tMaxX++; x = x + stepX; } else { tMaxY++; y = y + stepY; } result.add(new int[] {x, y}); } int[][] resultArray = new int[result.size()][2]; result.toArray(resultArray); return resultArray; }  static void drawPoint(SimpleVector point,
                                 Graphics2D ig, Color innerColor, Color outerColor,
                                 float radius, float borderSize); static void drawLine(SimpleVector p1, SimpleVector p2,
                                Graphics2D ig, Color innerColor, Color outerColor,
                                float size); static float[] lineIntersection(
            float x1, float y1, float x2, float y2,
            float x3, float y3, float x4, float y4,
            boolean includeEndPoints
    ); static float[] lineIntersection(
            int x1, int y1, int x2, int y2,
            int x3, int y3, int x4, int y4,
            boolean includeEndPoints
    ); static boolean onLine(double ax, double ay, double bx, double by, double cx, double cy); static boolean parallel(float x1, float y1, float x2, float y2,
                                   float x3, float y3, float x4, float y4); static boolean inTriangle(float px, float py,
                                          float p0x, float p0y, float p1x, float p1y, float p2x, float p2y); static int[][] getLineGridIntersection(int x1, int y1, int x2, int y2); static int[][] getTriangleGridIntersection(int x1, int y1, int x2, int y2, int x3, int y3); static int[][] getLineGridIntersection(double x1, double y1, double x2, double y2); static int[][] getTriangleGridIntersection(double x1, double y1, double x2, double y2, double x3, double y3);  }