001package algs13;
002import stdlib.*;
003import algs12.Point2D;
004/* ***********************************************************************
005 *  Compilation:  javac Grid.java
006 *  Execution:    java Grid N d
007 *  Dependencies: Queue.java
008 *
009 *  Generate N random Euclidean points in unit box (coorinates
010 *  between 0 and 1) and print out all pairs that are at
011 *  distance <= d.
012 *
013 *************************************************************************/
014
015public class XGrid {
016
017        public static void main(String[] args) {
018                int N    = Integer.parseInt(args[0]);
019                double d = Double.parseDouble(args[1]);
020
021                int G = (int) (Math.ceil(1.0 / d));    // rows and columns in grid
022
023                // initialize data structure
024                @SuppressWarnings("unchecked")
025                final
026                Queue<Point2D>[][] grid = new Queue[G+2][G+2];
027                for (int i = 0; i <= G+1; i++)
028                        for (int j = 0; j <= G+1; j++)
029                                grid[i][j] = new Queue<>();
030
031                // generate random points and check if any previous point <= d
032                for (int n = 0; n < N; n++) {
033                        double x = Math.random();
034                        double y = Math.random();
035                        Point2D p  = new Point2D(x, y);
036                        int row = 1 + (int) (x * G);
037                        int col = 1 + (int) (y * G);
038                        for (int i = row-1; i <= row+1; i++) {
039                                for (int j = col-1; j <= row+1; j++) {
040                                        for (Point2D q : grid[i][j])
041                                                if (p.distanceTo(q) <= d)
042                                                        StdOut.println(p + " <--> " + q);
043                                }
044                        }
045                        grid[row][col].enqueue(p);
046                }
047        }
048}
049