public static List<Integer> mapToGridCellsOnWay(float lon1,float lat1,float lon2,float lat2){
  int x1=(int)Math.floor((Math.abs(LON_WEST) - Math.abs(lon1)) / DELTA_LON);
  int y1=(int)Math.floor((LAT_NORTH - lat1) / DELTA_LAT);
  int x2=(int)Math.floor((Math.abs(LON_WEST) - Math.abs(lon2)) / DELTA_LON);
  int y2=(int)Math.floor((LAT_NORTH - lat2) / DELTA_LAT);
  int startX, startY, endX, endY;
  if (x1 <= x2) {
    startX=x1;
    startY=y1;
    endX=x2;
    endY=y2;
  }
 else {
    startX=x2;
    startY=y2;
    endX=x1;
    endY=y1;
  }
  double slope=(endY - startY) / ((endX - startX) + 0.00000001);
  int curX=startX;
  int curY=startY;
  ArrayList<Integer> cellIds=new ArrayList<>(64);
  cellIds.add(curX + (curY * NUMBER_OF_GRID_X));
  while (curX < endX || curY != endY) {
    if (slope > 0) {
      double y=(curX - startX + 0.5) * slope + startY - 0.5;
      if (y > curY - 0.05 && y < curY + 0.05) {
        curX++;
        curY++;
      }
 else       if (y < curY) {
        curX++;
      }
 else {
        curY++;
      }
    }
 else {
      double y=(curX - startX + 0.5) * slope + startY + 0.5;
      if (y > curY - 0.05 && y < curY + 0.05) {
        curX++;
        curY--;
      }
      if (y > curY) {
        curX++;
      }
 else {
        curY--;
      }
    }
    cellIds.add(curX + (curY * NUMBER_OF_GRID_X));
  }
  return cellIds;
}

public static List < Integer > mapToGridCellsOnWay ( float lon1 , float lat1 , float lon2 , float lat2 ) { int x1 = ( int ) Math . floor ( ( Math . abs ( LON_WEST ) - Math . abs ( lon1 ) ) / DELTA_LON ) ; int y1 = ( int ) Math . floor ( ( LAT_NORTH - lat1 ) / DELTA_LAT ) ; int x2 = ( int ) Math . floor ( ( Math . abs ( LON_WEST ) - Math . abs ( lon2 ) ) / DELTA_LON ) ; int y2 = ( int ) Math . floor ( ( LAT_NORTH - lat2 ) / DELTA_LAT ) ; int startX , startY , endX , endY ; if ( x1 <= x2 ) { startX = x1 ; startY = y1 ; endX = x2 ; endY = y2 ; } else { startX = x2 ; startY = y2 ; endX = x1 ; endY = y1 ; } double slope = ( endY - startY ) / ( ( endX - startX ) + 0.00000001 ) ; int curX = startX ; int curY = startY ; ArrayList < Integer > cellIds = new ArrayList < > ( 64 ) ; cellIds . add ( curX + ( curY * NUMBER_OF_GRID_X ) ) ; while ( curX < endX || curY != endY ) { if ( slope > 0 ) { double y = ( curX - startX + 0.5 ) * slope + startY - 0.5 ; if ( y > curY - 0.05 && y < curY + 0.05 ) { curX ++ ; curY ++ ; } else if ( y < curY ) { curX ++ ; } else { curY ++ ; } } else { double y = ( curX - startX + 0.5 ) * slope + startY + 0.5 ; if ( y > curY - 0.05 && y < curY + 0.05 ) { curX ++ ; curY -- ; } if ( y > curY ) { curX ++ ; } else { curY -- ; } } cellIds . add ( curX + ( curY * NUMBER_OF_GRID_X ) ) ; } return cellIds ; }
maps the direct path between two locations specified by longitude and latitude to a list of cells of a grid covering the area of nyc . the grid cells are roughly 100 x 100 m and sequentially number from north - west to south - east starting by zero .
