Source code

001/*
002 * Licensed under the Apache License, Version 2.0 (the "License");
003 * you may not use this file except in compliance with the License.
004 * You may obtain a copy of the License at
005 *
006 *     http://www.apache.org/licenses/LICENSE-2.0
007 *
008 * Unless required by applicable law or agreed to in writing, software
009 * distributed under the License is distributed on an "AS IS" BASIS,
010 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
011 * See the License for the specific language governing permissions and
012 * limitations under the License.
013 */
014package org.gbif.common.parsers.geospatial;
015
016import java.util.HashSet;
017import java.util.List;
018import java.util.Set;
019
020import org.apache.commons.math3.util.Precision;
021import org.slf4j.Logger;
022import org.slf4j.LoggerFactory;
023
024/**
025 * Utilities for dealing with CellId.
026 */
027public class CellIdUtils {
028
029  private static final Logger LOGGER = LoggerFactory.getLogger(CellIdUtils.class);
030
031  private static final int MAX_LATITUDE = 90;
032  private static final int MIN_LATITUDE = -MAX_LATITUDE;
033  private static final int MAX_LONGITUDE = 180;
034  private static final int MIN_LONGITUDE = -MAX_LONGITUDE;
035
036  private CellIdUtils() {
037    throw new UnsupportedOperationException("Can't initialize class");
038  }
039
040  /**
041   * Determines the cell id for the Lat / Long provided.
042   *
043   * @param latitude  Which may be null
044   * @param longitude Which may be null
045   *
046   * @return The cell id for the Lat Long pair
047   *
048   * @throws UnableToGenerateCellIdException
049   *          Should the lat long be null or invalid
050   */
051  public static int toCellId(Double latitude, Double longitude) throws UnableToGenerateCellIdException {
052    LOGGER.debug("Getting cell for [{},{}]", latitude, longitude);
053
054    if (latitude == null || latitude < MIN_LATITUDE || latitude > MAX_LATITUDE || longitude < MIN_LONGITUDE
055        || longitude > MAX_LONGITUDE) {
056      throw new UnableToGenerateCellIdException(
057        "Latitude[" + latitude + "], Longitude[" + longitude + "] cannot be converted to a cell id");
058    } else {
059      int la = getCellIdFor(latitude);
060      int lo = getMod360CellIdFor(longitude);
061      return la + lo;
062    }
063  }
064
065  /**
066   * Get mod 360 cell id.
067   */
068  public static int getMod360CellIdFor(double longitude) {
069    return Double.valueOf(Math.floor(longitude + MAX_LONGITUDE)).intValue();
070  }
071
072  /**
073   * Get cell id.
074   */
075  public static int getCellIdFor(double latitude) {
076    return Double.valueOf(Math.floor(latitude + MAX_LATITUDE)).intValue() * 360;
077  }
078
079  /**
080   * Returns true if the supplied cell id lies in the bounding box demarcated by the min and max cell ids supplied.
081   */
082  public static boolean isCellIdInBoundingBox(int cellId, int minCellId, int maxCellId) throws Exception {
083    return cellId >= minCellId && cellId <= (maxCellId - 361) && (cellId % 360) >= (minCellId % 360)
084           && (cellId % 360) <= ((maxCellId - 361) % 360);
085  }
086
087  /**
088   * Determines the centi cell id for the given values
089   *
090   * @param latitude  Which may be null
091   * @param longitude Which may be null
092   *
093   * @return The centi cell id within the cell for the lat long
094   *
095   * @throws UnableToGenerateCellIdException
096   *          Shoudl the lat long be null or invalid
097   */
098  public static int toCentiCellId(Double latitude, Double longitude) throws UnableToGenerateCellIdException {
099    if (latitude == null || latitude < MIN_LATITUDE || latitude > MAX_LATITUDE || longitude < MIN_LONGITUDE
100        || longitude > MAX_LONGITUDE) {
101      throw new UnableToGenerateCellIdException(
102        "Latitude[" + latitude + "], Longitude[" + longitude + "] cannot be " + "converted to a centi cell id");
103    } else {
104
105      //get decimal value for up to 4 decimal places
106      //17.2-> 172000 -> 2000
107      int la = Math.abs((int) (latitude * 10000) % 10000);
108      if (latitude < 0) la = 10000 - la;
109      la = (la / 1000) % 10;
110      int lo = Math.abs((int) (longitude * 10000) % 10000);
111      if (longitude < 0) lo = 10000 - lo;
112      lo = (lo / 1000) % 10;
113
114      int centiCellId = (la * 10) + lo;
115      return Math.abs(centiCellId);
116    }
117  }
118
119  /**
120   * Returns the box of the given cell This may require some more work to avoid divide rounding errors
121   *
122   * @param cellId To return the lat long box of
123   *
124   * @return The box
125   */
126  public static LatLngBoundingBox toBoundingBox(int cellId) {
127    int longitude = (cellId % 360) - MAX_LONGITUDE;
128    int latitude = MIN_LATITUDE;
129    if (cellId > 0) {
130      latitude = Double.valueOf(Math.floor(cellId / 360)).intValue() - MAX_LATITUDE;
131    }
132    return new LatLngBoundingBox(longitude, latitude, longitude + 1, latitude + 1);
133  }
134
135  /**
136   * Returns the box of the given cell and centi cell An attempt has been made to avoid rounding errors with doubles,
137   * but may need revisited
138   *
139   * @param cellId      To return the lat long box of
140   * @param centiCellId within the box
141   *
142   * @return The box
143   */
144  public static LatLngBoundingBox toBoundingBox(int cellId, int centiCellId) {
145    int longitudeX10 = 10 * ((cellId % 360) - MAX_LONGITUDE);
146    int latitudeX10 = -900;
147    if (cellId > 0) {
148      latitudeX10 = 10 * (Double.valueOf(Math.floor(cellId / 360)).intValue() - MAX_LATITUDE);
149    }
150
151    double longOffset = (centiCellId % 10);
152    double latOffset = 0;
153    if (centiCellId > 0) {
154      latOffset = centiCellId / 10;
155    }
156
157    double minLatitude = (latitudeX10 + latOffset) / 10;
158    double minLongitude = (longitudeX10 + longOffset) / 10;
159    double maxLatitude = (latitudeX10 + latOffset + 1) / 10;
160    double maxLongitude = (longitudeX10 + longOffset + 1) / 10;
161    return new LatLngBoundingBox(minLongitude, minLatitude, maxLongitude, maxLatitude);
162  }
163
164  /**
165   * Gets the list of cells that are enclosed within the bounding box. Cells that are partially enclosed are returned
166   * also
167   * TODO implement this properly, the current version will include cells that are partially included on the bottom and
168   * left, but not the top and right
169   *
170   * @return The cells that are enclosed by the bounding box
171   *
172   * @throws UnableToGenerateCellIdException
173   *          if the lat longs are invalid
174   */
175  public static Set<Integer> getCellsEnclosedBy(double minLat, double maxLat, double minLong, double maxLong)
176    throws UnableToGenerateCellIdException {
177    if (minLat < MIN_LATITUDE) minLat = MIN_LATITUDE;
178    if (maxLat > MAX_LATITUDE) maxLat = MAX_LATITUDE;
179    if (minLong < MIN_LONGITUDE) minLong = MIN_LONGITUDE;
180    if (maxLong > MAX_LONGITUDE) maxLong = MAX_LONGITUDE;
181
182    LOGGER.debug("Establishing cells enclosed by: {}:{}   {}:{}", new Object[] {minLat, maxLat, minLong, maxLong});
183
184    int lower = toCellId(minLat, minLong);
185    int upper = toCellId(maxLat, maxLong);
186
187    LOGGER.debug("Unprocessed cells: {} -> {}", lower, upper);
188
189    // if the BB upper right corner is on a grid, then it needs flagged
190    if (Math.ceil(maxLong) == Math.floor(maxLong)) {
191      LOGGER.debug("Longitude lies on a boundary");
192      upper -= 1;
193    }
194    if (Math.ceil(maxLat) == Math.floor(maxLat)) {
195      LOGGER.debug("Latitude lies on a boundary");
196      upper -= 360;
197    }
198
199    LOGGER.debug("Getting cells contained in {} to {}", lower, upper);
200
201    int omitLeft = lower % 360;
202    int omitRight = upper % 360;
203    if (omitRight == 0) omitRight = 360;
204    Set<Integer> cells = new HashSet<Integer>();
205    for (int i = lower; i <= upper; i++) {
206      if (i % 360 >= omitLeft && i % 360 <= omitRight) {
207        cells.add(i);
208      }
209    }
210    return cells;
211  }
212
213  /**
214   * Return a min cell id and a max cell id for this bounding box.
215   *
216   * @return the minCellId in int[0] and maxCellId in int[1]
217   */
218  public static int[] getMinMaxCellIdsForBoundingBox(double minLongitude, double minLatitude, double maxLongitude,
219    double maxLatitude) throws UnableToGenerateCellIdException {
220
221    int minCellId = toCellId(minLatitude, minLongitude);
222    int maxCellId = toCellId(maxLatitude, maxLongitude);
223
224    if (Math.ceil(maxLatitude) == Math.floor(maxLatitude) && Math.ceil(maxLongitude) == Math.floor(maxLongitude)
225        && maxLongitude != 180f && maxLatitude != 90f && maxCellId > 0) {
226
227      //the maxLongitude,maxLatitude point is on a cell intersection, hence the maxCellId should be
228      // -361 the maxCellId CellIdUtils will give us i.e. the cell that is
229      // 1 below and 1 to the left of the cell id retrieved
230      //unless it is the 64799 cell.
231      maxCellId = maxCellId - 361;
232    }
233
234    return new int[] {minCellId, maxCellId};
235  }
236
237  /**
238   * Creates a bounding box for the list of unordered cell ids.
239   *
240   * @return a LatLngBoundingBox that encapsulates this list of cell ids.
241   */
242  public static LatLngBoundingBox getBoundingBoxForCells(List<Integer> cellIds) {
243    if (cellIds.isEmpty()) return null;
244    //first cell - gives the minLat
245    //double minLatitude = toBoundingBox(cellIds.get(0)).minLat;
246    //last cell - give the maxLat
247    //double maxLatitude = toBoundingBox(cellIds.get(cellIds.size()-1)).maxLat;
248    int minLatitudeCellId = cellIds.get(0);
249    int maxLatitudeCellId = cellIds.get(cellIds.size() - 1);
250
251    int minLongitudeCellId = cellIds.get(0);
252    int maxLongitudeCellId = cellIds.get(cellIds.size() - 1);
253    //the min cell (id % 360) - gives min longitude
254    //the max cell (id % 360) - gives max longitude
255    for (Integer cellId : cellIds) {
256
257      Integer cellIdMod360 = cellId % 360;
258      if (cellIdMod360 < (minLongitudeCellId % 360)) minLongitudeCellId = cellIdMod360;
259      if (cellIdMod360 > (maxLongitudeCellId % 360)) maxLongitudeCellId = cellIdMod360;
260
261      if (cellId < minLatitudeCellId) minLatitudeCellId = cellId;
262      if (cellId > maxLatitudeCellId) maxLatitudeCellId = cellId;
263    }
264    double minLongitude = toBoundingBox(minLongitudeCellId).minLong;
265    double minLatitude = toBoundingBox(minLatitudeCellId).minLat;
266    double maxLongitude = toBoundingBox(maxLongitudeCellId).maxLong;
267    double maxLatitude = toBoundingBox(maxLatitudeCellId).maxLat;
268
269    return new LatLngBoundingBox(minLongitude, minLatitude, maxLongitude, maxLatitude);
270  }
271
272  /**
273   * Returns the cell id and centi cell id for the supplied bounding box, Returning null if the supplied bounding box
274   * doesnt enclose a single cell. If the bounding box encloses a single cell but not a centi cell, a Integer[] of
275   * length 1 is returned with containing the cell id. Otherwise a Integer array of length 2, with Integer[0] being the
276   * cell id, Integer[1] being the centi cell.
277   */
278  public static Integer[] getCentiCellIdForBoundingBox(double minLongitude, double minLatitude, double maxLongitude,
279    double maxLatitude) throws UnableToGenerateCellIdException {
280
281    //int[] maxMinCellIds = getMinMaxCellIdsForBoundingBox(minLongitude, minLatitude, maxLongitude, maxLatitude);
282    //if(maxMinCellIds==null || (maxMinCellIds[0]!=maxMinCellIds[1]))
283    //  return null;
284
285    //Integer cellId = maxMinCellIds[0];
286
287    //int[] maxMinCellIds = getMinMaxCellIdsForBoundingBox(minLongitude, minLatitude, maxLongitude, maxLatitude);
288
289    if (!isBoundingBoxCentiCell(minLongitude, minLatitude, maxLongitude, maxLatitude)) {
290      return null;
291    }
292
293    //ascertain whether bounding box is 0.1 by 0.1
294    //if(isBoundingBoxCentiCell(minLongitude, minLatitude, maxLongitude, maxLatitude)){
295
296    int[] maxMinCellIds = getMinMaxCellIdsForBoundingBox(minLongitude, minLatitude, maxLongitude, maxLatitude);
297    Integer cellId = maxMinCellIds[0];
298
299    int minCentiCell = toCentiCellId(minLatitude, minLongitude);
300    int maxCentiCell = toCentiCellId(maxLatitude, maxLongitude);
301
302    double maxLongitude10 = maxLongitude * 10;
303    double maxLatitude10 = maxLatitude * 10;
304
305    if (Math.ceil(maxLatitude10) == Math.floor(maxLatitude10) && Math.ceil(maxLongitude10) == Math.floor(maxLongitude10)
306        && maxCentiCell > 0) {
307
308      //the maxLongitude,maxLatitude point is on a centi cell intersection, hence the maxCentiCellId should be
309      // maxCentiCellId-11 i.e. the cell that is
310      // 1 below and 1 to the left of the centi cell id retrieved
311      //unless it is the 100 centi cell.
312      if (maxCentiCell > minCentiCell) {
313        maxCentiCell = maxCentiCell - 11;
314      } else {
315        maxCentiCell = maxCentiCell + 9;
316      }
317    }
318
319    //if(maxCentiCell==minCentiCell){
320    return new Integer[] {cellId, minCentiCell};
321    //}
322    //}
323    //return new Integer[]{cellId};
324  }
325
326  private static boolean isBoundingBoxCentiCell(double minLongitude, double minLatitude, double maxLongitude,
327    double maxLatitude) {
328    double width = maxLongitude > minLongitude ? maxLongitude - minLongitude : minLongitude - maxLongitude;
329    double height = maxLatitude > minLatitude ? maxLatitude - minLatitude : minLatitude - maxLatitude;
330    return Precision.round(height, 1) == 0.1f && Precision.round(width, 1) == 0.1f;
331  }
332
333  /**
334   * For ease of conversion
335   *
336   * @param args See usage
337   */
338  public static void main(String[] args) {
339    try {
340      if (args.length == 1) {
341        LatLngBoundingBox llbb = toBoundingBox(Integer.parseInt(args[0]));
342        System.out.println(
343          "CellId " + args[0] + ": minX[" + llbb.getMinLong() + "] minY[" + llbb.getMinLat() + "] maxX[" + llbb
344            .getMaxLong() + "] maxY[" + llbb.getMaxLat() + "]");
345      } else if (args.length == 2) {
346        double lat = Double.parseDouble(args[0]);
347        double lon = Double.parseDouble(args[1]);
348        System.out.println("lat[" + lat + "] long[" + lon + "] = cellId: " + toCellId(lat, lon));
349      } else {
350        System.out.println("Provide either a 'cell id' or 'Lat Long' params!");
351      }
352    } catch (NumberFormatException | UnableToGenerateCellIdException e) {
353      LOGGER.error("Error converting bounding box", e);
354    }
355  }
356}