@Test public void getTriangleGridIntersectionMass() throws Exception { Random rand = new Random(); for (int i = 0; i < 100000; i++) { if (i%1000 == 0) { System.out.println(":: " + i); } 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; float xf3 = rand.nextInt(512) - 0.5f; float yf3 = rand.nextInt(512) - 0.5f; G2DUtil.getTriangleGridIntersection( (int) (xf1 + 0.5f), (int) (yf1 + 0.5f), (int) (xf2 + 0.5f), (int) (yf2 + 0.5f), (int) (xf3 + 0.5f), (int) (yf3 + 0.5f) ); } }
public static int[][] getTriangleGridIntersection(int x1, int y1, int x2, int y2, int x3, int y3) { int minX = Math.min(Math.min(x1, x2), x3); int maxX = Math.max(Math.max(x1, x2), x3); int minY = Math.min(Math.min(y1, y2), y3); int maxY = Math.max(Math.max(y1, y2), y3); int[][] range = new int[maxY - minY][2]; for (int i = 0; i < range.length; i++) { range[i][0] = Integer.MAX_VALUE; range[i][1] = Integer.MIN_VALUE; } int[][] p1 = getLineGridIntersection(x1, y1, x2, y2); int[][] p2 = getLineGridIntersection(x1, y1, x3, y3); int[][] p3 = getLineGridIntersection(x2, y2, x3, y3); for (int[] p : p1) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } for (int[] p : p2) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } for (int[] p : p3) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } ArrayList<int[]> result = new ArrayList<int[]>(); for (int i = 0; i < range.length; i++) { int[] row = range[i]; for (int x = Math.max(minX, row[0]), lenX = Math.min(row[1] + 1, maxX); x < lenX; x++) { result.add(new int[] { x, i + minY }); } } int[][] resultArray = new int[result.size()][2]; result.toArray(resultArray); return resultArray; }
G2DUtil { public static int[][] getTriangleGridIntersection(int x1, int y1, int x2, int y2, int x3, int y3) { int minX = Math.min(Math.min(x1, x2), x3); int maxX = Math.max(Math.max(x1, x2), x3); int minY = Math.min(Math.min(y1, y2), y3); int maxY = Math.max(Math.max(y1, y2), y3); int[][] range = new int[maxY - minY][2]; for (int i = 0; i < range.length; i++) { range[i][0] = Integer.MAX_VALUE; range[i][1] = Integer.MIN_VALUE; } int[][] p1 = getLineGridIntersection(x1, y1, x2, y2); int[][] p2 = getLineGridIntersection(x1, y1, x3, y3); int[][] p3 = getLineGridIntersection(x2, y2, x3, y3); for (int[] p : p1) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } for (int[] p : p2) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } for (int[] p : p3) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } ArrayList<int[]> result = new ArrayList<int[]>(); for (int i = 0; i < range.length; i++) { int[] row = range[i]; for (int x = Math.max(minX, row[0]), lenX = Math.min(row[1] + 1, maxX); x < lenX; x++) { result.add(new int[] { x, i + minY }); } } int[][] resultArray = new int[result.size()][2]; result.toArray(resultArray); return resultArray; } }
G2DUtil { public static int[][] getTriangleGridIntersection(int x1, int y1, int x2, int y2, int x3, int y3) { int minX = Math.min(Math.min(x1, x2), x3); int maxX = Math.max(Math.max(x1, x2), x3); int minY = Math.min(Math.min(y1, y2), y3); int maxY = Math.max(Math.max(y1, y2), y3); int[][] range = new int[maxY - minY][2]; for (int i = 0; i < range.length; i++) { range[i][0] = Integer.MAX_VALUE; range[i][1] = Integer.MIN_VALUE; } int[][] p1 = getLineGridIntersection(x1, y1, x2, y2); int[][] p2 = getLineGridIntersection(x1, y1, x3, y3); int[][] p3 = getLineGridIntersection(x2, y2, x3, y3); for (int[] p : p1) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } for (int[] p : p2) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } for (int[] p : p3) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } ArrayList<int[]> result = new ArrayList<int[]>(); for (int i = 0; i < range.length; i++) { int[] row = range[i]; for (int x = Math.max(minX, row[0]), lenX = Math.min(row[1] + 1, maxX); x < lenX; x++) { result.add(new int[] { x, i + minY }); } } int[][] resultArray = new int[result.size()][2]; result.toArray(resultArray); return resultArray; }  }
G2DUtil { public static int[][] getTriangleGridIntersection(int x1, int y1, int x2, int y2, int x3, int y3) { int minX = Math.min(Math.min(x1, x2), x3); int maxX = Math.max(Math.max(x1, x2), x3); int minY = Math.min(Math.min(y1, y2), y3); int maxY = Math.max(Math.max(y1, y2), y3); int[][] range = new int[maxY - minY][2]; for (int i = 0; i < range.length; i++) { range[i][0] = Integer.MAX_VALUE; range[i][1] = Integer.MIN_VALUE; } int[][] p1 = getLineGridIntersection(x1, y1, x2, y2); int[][] p2 = getLineGridIntersection(x1, y1, x3, y3); int[][] p3 = getLineGridIntersection(x2, y2, x3, y3); for (int[] p : p1) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } for (int[] p : p2) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } for (int[] p : p3) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } ArrayList<int[]> result = new ArrayList<int[]>(); for (int i = 0; i < range.length; i++) { int[] row = range[i]; for (int x = Math.max(minX, row[0]), lenX = Math.min(row[1] + 1, maxX); x < lenX; x++) { result.add(new int[] { x, i + minY }); } } 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[][] getTriangleGridIntersection(int x1, int y1, int x2, int y2, int x3, int y3) { int minX = Math.min(Math.min(x1, x2), x3); int maxX = Math.max(Math.max(x1, x2), x3); int minY = Math.min(Math.min(y1, y2), y3); int maxY = Math.max(Math.max(y1, y2), y3); int[][] range = new int[maxY - minY][2]; for (int i = 0; i < range.length; i++) { range[i][0] = Integer.MAX_VALUE; range[i][1] = Integer.MIN_VALUE; } int[][] p1 = getLineGridIntersection(x1, y1, x2, y2); int[][] p2 = getLineGridIntersection(x1, y1, x3, y3); int[][] p3 = getLineGridIntersection(x2, y2, x3, y3); for (int[] p : p1) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } for (int[] p : p2) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } for (int[] p : p3) { int val = p[1]-minY; if (val > -1 && val < range.length) { int[] rangeEntry = range[val]; rangeEntry[0] = Math.min(rangeEntry[0], p[0]); rangeEntry[1] = Math.max(rangeEntry[1], p[0]); } } ArrayList<int[]> result = new ArrayList<int[]>(); for (int i = 0; i < range.length; i++) { int[] row = range[i]; for (int x = Math.max(minX, row[0]), lenX = Math.min(row[1] + 1, maxX); x < lenX; x++) { result.add(new int[] { x, i + minY }); } } 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);  }