[GitHub] [carbondata] MarvinLitt commented on a change in pull request #3481: [CARBONDATA-3548]Geospatial Support： add hash id create，query condition analyze and generate hash id list

[GitBox]

MarvinLitt commented on a change in pull request #3481: [CARBONDATA-3548]Geospatial Support： add hash id create，query condition analyze and generate hash id list
URL: https://github.com/apache/carbondata/pull/3481#discussion_r357045555
 
 

 ##########
 File path: geo/src/main/java/org/apache/carbondata/geo/QuadTreeCls.java
 ##########
 @@ -0,0 +1,904 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.carbondata.geo;
+
+import java.awt.geom.Point2D;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+import org.apache.carbondata.common.logging.LogServiceFactory;
+
+import org.apache.log4j.Logger;
+
+import org.locationtech.jts.geom.Coordinate;
+import org.locationtech.jts.geom.Geometry;
+import org.locationtech.jts.geom.GeometryFactory;
+import org.locationtech.jts.geom.Point;
+import org.locationtech.jts.geom.Polygon;
+
+
+
+/**
+ * Spatial region function processing related classes
+ */
+class GeometryOperation {
+  private static final GeometryFactory geoFactory = new GeometryFactory();
+
+  /**
+   * Convert point object to polygon object in Geo
+   *
+   * @param polygon Area coordinates stored as a list
+   * @return JTS Polygon objects
+   */
+  public static Polygon getPolygonByPointList(List<Point2D.Double> polygon) {
+    int size = polygon.size();
+    if (size < 3) {
+      return null;
+    } else {
+      Coordinate[] rect = new Coordinate[size + 1];
+      for (int i = 0; i < size; i++) {
+        rect[i] = new Coordinate(polygon.get(i).x, polygon.get(i).y);
+      }
+      rect[size] = new Coordinate(polygon.get(0).x, polygon.get(0).y);
+      return geoFactory.createPolygon(rect);
+    }
+  }
+
+  /**
+   * Convert point object to polygon object in Geo
+   * @param polygon Area coordinates stored as a list
+   * @return JTS Polygon objects
+   */
+  public static Polygon getPolygonByDoubleList(List<double[]> polygon) {
+    int size = polygon.size();
+    if (size < 3) {
+      return null;
+    } else {
+      Coordinate[] rect = new Coordinate[size + 1];
+      for (int i = 0; i < size; i++) {
+        rect[i] = new Coordinate(polygon.get(i)[0], polygon.get(i)[1]);
+      }
+      double x = polygon.get(0)[0];
+      double y = polygon.get(0)[1];
+      rect[size] = new Coordinate(x, y);
+      return geoFactory.createPolygon(rect);
+    }
+  }
+
+  /**
+   * Converting point objects to point objects in Geo
+   * @param pointB Point2D Point object
+   * @return JTS Point object
+   */
+  public static Point getPointByPoint2D(Point2D.Double pointB) {
+    Coordinate point = new Coordinate(pointB.x, pointB.y);
+    return geoFactory.createPoint(point);
+  }
+
+
+  /**
+   * Apart a and B do not intersect, a and B are polygons
+   * @param polygonA polygon
+   * @param polygonB polygon
+   * @return true Polygons apart，false Polygons are inseparable
+   */
+  public static boolean disjoint(Geometry polygonA, List<Point2D.Double> polygonB) {
+    Polygon polyB = getPolygonByPointList(polygonB);
+    boolean result  = polygonA.disjoint(polyB);
+    return result;
+  }
+
+  /**
+   * A and B do not intersect each other, A is a polygon, B is a point
+   * @param polygonA polygon
+   * @param pointB point
+   * @return true Point away from polygon，false Points are inseparable from polygons
+   */
+  public static boolean disjoint(Geometry polygonA, Point2D.Double pointB) {
+    Point pointGeo = getPointByPoint2D(pointB);
+    boolean result = polygonA.disjoint(pointGeo);
+    return result;
+  }
+
+  /**
+   * contains - A contains B Compare polygon a with polygon B
+   * @param polygonA  polygon
+   * @param polygonB  polygon
+   * @return 0 Polygon a contains polygon B (a = B or a > b),
+   *        -1 Polygon a does not contain polygon B
+   */
+  public static boolean contains(Geometry polygonA, List<Point2D.Double> polygonB) {
+    Polygon polyB = getPolygonByPointList(polygonB);
+    return polygonA.contains(polyB);
+  }
+
+
+  /**
+   * contains - A contains B Compare whether polygon a contains B
+   * @param polygonA  polygon
+   * @param pointB   point
+   * @return true Polygon a contains point B (B in a), false Polygon a does not contain point B
+   */
+  public static boolean contains(Geometry polygonA, Point2D.Double pointB) {
+    Point pointGeo = getPointByPoint2D(pointB);
+    boolean result = polygonA.contains(pointGeo);
+    return result;
+  }
+
+  /**
+   * intersect - A intersects B Indicates that polygon a intersects polygon B
+   * @param polygonA polygon
+   * @param polygonB polygon
+   * @return true Polygon a intersects polygon B,false Polygon a does not intersect polygon B
+   */
+  public static boolean intersects(Geometry polygonA, List<Point2D.Double> polygonB) {
+    Polygon polyB = getPolygonByPointList(polygonB);
+    boolean result = polygonA.intersects(polyB);
+    return result;
+  }
+
+  /**
+   * intersect - A intersects B Represents the intersection of polygon A and point B
+   * @param polygonA polygon
+   * @param pointB point
+   * @return true Polygon a intersects point B,false Polygon a does not intersect point B
+   */
+  public static boolean intersects(Geometry polygonA, Point2D.Double pointB) {
+    Point pointGeo = getPointByPoint2D(pointB);
+    boolean result = polygonA.intersects(pointGeo);
+    return result;
+  }
+}
+
+
+/**
+ * Polygon region object
+ */
+class QuadRect {
+  public Double left;
+  public Double top;
+  public Double right;
+  public Double bottom;
+  /**
+   * build func
+   * @param topleft Left upper point
+   * @param bottomRight Right lower point
+   */
+  public QuadRect(Point2D.Double topleft, Point2D.Double bottomRight) {
+    this.left = topleft.x;
+    this.top = topleft.y;
+    this.right = bottomRight.x;
+    this.bottom = bottomRight.y;
+  }
+
+  /**
+   * build func
+   * @param x Leftmost coordinates
+   * @param y Bottom coordinate
+   * @param x2 Rightmost coordinate
+   * @param y2 Top coordinate
+   */
+  public QuadRect(double x, double y, double x2, double y2) {
+    this.left = x;
+    this.bottom = y;
+    this.right = x2;
+    this.top = y2;
+  }
+
+  /**
+   * The given area is outside the current node area
+   * @param polygonRect If the circumscribed rectangle of a given region is larger than
+   *                    the coordinate with the node, it means it is outside the whole region
+   * @return true The given area is outside the point,false The given area is within the point area
+   */
+  public boolean outsideBox(QuadRect polygonRect) {
+    return polygonRect.left < this.left || polygonRect.right > this.right ||
+               polygonRect.top > this.top || polygonRect.bottom < this.bottom;
+
+  }
+
+  /**
+   * Get the polygon list of this area. The point is the rectangle of the inner center point of
+   * the grid area center point. If it is the smallest grid, it is the coordinate of the
+   * peripheral point
+   * @return 矩形区域的顶点列表
+   */
+  public List<Point2D.Double> getPolygonPointList() {
+    Point2D.Double topLeft = new Point2D.Double(this.left, this.top);
+    Point2D.Double topRight = new Point2D.Double(this.right, this.top);
+    Point2D.Double bottomRight = new Point2D.Double(this.right, this.bottom);
+    Point2D.Double bottomLeft = new Point2D.Double(this.left, this.bottom);
+    List<Point2D.Double> polygon = new ArrayList<>();
+    polygon.add(topLeft);
+    polygon.add(topRight);
+    polygon.add(bottomRight);
+    polygon.add(bottomLeft);
+    return polygon;
+  }
+
+  /**
+   * Get the coordinates of the center point of the area
+   * @return Center point coordinates
+   */
+  public Double[] getMidelePoint() {
+    double x = left + (right - left) / 2;
+    double y = bottom + (top - bottom) / 2;
+    return new Double [] {x, y};
+  }
+
+  /**
+   * Get the center point of the grid
+   * @return This grid represents the center point of the area
+   */
+  public Point2D.Double getMiddlePoint() {
+    Double [] mPoint = getMidelePoint();
+    return new Point2D.Double(mPoint[0], mPoint[1]);
+  }
+
+  /**
+   * Split a region into four regions, reduce the creation of objects, and directly return
+   * two coordinates of the region
+   * @return Returns the coordinates of nine points cut into four areas, in the order of top left,
+   * top middle, top right; middle left, middle right, bottom left, bottom middle, bottom right
+   *
+   */
+  public List<Point2D.Double> getSplitRect() {
+    Double [] mPoint = getMidelePoint();
+    // The four remaining points, plus the four points of the boundary, constitute four regions
+    // A region is divided into 4 sub regions by 9 points
+    double middleTopX = mPoint[0];
+    double middleTopY = this.top;
+    Point2D.Double middleTop = new Point2D.Double(middleTopX, middleTopY);
+
+    double middleBottomX = mPoint[0];
+    double middleBottomY = this.bottom;
+    Point2D.Double middleBottom = new Point2D.Double(middleBottomX, middleBottomY);
+
+    double leftMiddleX = this.left;
+    double leftMiddleY = mPoint[1];
+    Point2D.Double leftMiddle = new Point2D.Double(leftMiddleX, leftMiddleY);
+
+    double rightMiddleX = this.right;
+    double rightMiddleY = mPoint[1];
+    Point2D.Double rightMiddle = new Point2D.Double(rightMiddleX, rightMiddleY);
+
+    Point2D.Double middle = new Point2D.Double(mPoint[0], mPoint[1]);
+    Point2D.Double topLeft = new Point2D.Double(this.left, this.top);
+    Point2D.Double topRight = new Point2D.Double(this.right, this.top);
+    Point2D.Double bottomLeft = new Point2D.Double(this.left, this.bottom);
+    Point2D.Double bottomRight = new Point2D.Double(this.right, this.bottom);
+
+    List<Point2D.Double> rectList = new ArrayList<>();
+    rectList.add(topLeft);
+    rectList.add(middleTop);
+    rectList.add(topRight);
+
+    rectList.add(leftMiddle);
+    rectList.add(middle);
+    rectList.add(rightMiddle);
+
+    rectList.add(bottomLeft);
+    rectList.add(middleBottom);
+    rectList.add(bottomRight);
+    return rectList;
+  }
+}
+
+
+/**
+ * Store grid data
+ */
+class GridData {
+  public static final int STATUS_CONTAIN = 0;  // contains sub nodes in the polygon.
+  public static final int STATUS_ALL = 1;  // all children are in the polygon.
+  public static final int STATUS_DISJOIN = 2;  // contains sub nodes in the polygon.
+
+  public long startRow;  // Number of lines started
+  public long endRow;  // Number of lines ended
+  public long startColumn; // Number of columns started
+  public long endColumn;   // Number of columns ended
+  private long startHash; // Start hash
+  private long endHash;   // End hash
+  private int maxDepth;
+  private int status = STATUS_DISJOIN;  // Expressing separation
+
+  /**
+   * Construct grid area and data
+   * @param rs startRow
+   * @param re endRow
+   * @param cs startColumn
+   * @param ce endColumn
+   * @param maxDepth Maximum recursion depth
+   */
+  public GridData(long rs, long re, long cs, long ce, int maxDepth) {
+    this.startRow = rs;
+    this.endRow = re;
+    this.startColumn = cs;
+    this.endColumn = ce;
+    this.maxDepth = maxDepth;
+    computeHashidRange();
+  }
+
+  public void setGridData(GridData grid) {
+    this.startRow = grid.startRow;
+    this.endRow = grid.endRow;
+    this.startColumn = grid.startColumn;
+    this.endColumn = grid.endColumn;
+    this.maxDepth = grid.maxDepth;
+    this.startHash = grid.startHash;
+    this.endHash = grid.endHash;
+    this.status = grid.status;
+  }
+
+  /**
+   * Construct the range of hashid, construct a start and end range
+   */
+  private void computeHashidRange() {
+    startHash = createHashID(startRow, startColumn);
+    endHash = createHashID(endRow - 1, endColumn - 1);
+  }
+
+  /**
+   * Calculate the corresponding hashid value from the grid coordinates
+   * @param row Gridded row index
+   * @param column Gridded column index
+   * @return In practice, I and j are related to longitude and latitude,
+   * and finally the hash value of longitude and latitude data should be brought in
+   */
+  public long createHashID(long row, long column) {
+    long index = 0L;
+    for (int i = 0; i < maxDepth + 1; i++) {
+      long x = (row >> i) & 1;    //取第i位
+      long y = (column >> i) & 1;
+      index = index | (x << (2 * i + 1)) | (y << 2 * i);
+    }
+    return index;
+  }
+
+  /**
+   * Set the state of the grid
+   * @param status  The allowed input range is STATUS_CONTAIN STATUS_ALL
+   */
+  public void setStatus(int status) {
+    this.status = status;
+  }
+
+  /**
+   * Get grid status
+   * @return grid state
+   */
+  public int getStatus() {
+    return this.status;
+  }
+
+  /**
+   * Get ID range of grid
+   * @return Start ID, end ID
+   */
+  public Long[] getHashIDRange() {
+    return new Long[] {startHash, endHash};
+  }
+}
+
+/**
+ * Nodes of quad tree
+ */
+class QuadNode {
+  private static final Logger LOGGER =
+      LogServiceFactory.getLogService(GeoHashImpl.class.getName());
+  // The range Z order of region hashid represented by quadtree is a continuous range
+  private QuadRect rect;
+  // Grid data, actually representing hashid
+  private GridData grid;
+  // The depth of the current number defaults to 4 ^ n nodes per layer starting from 1
+  private int currentDepth;
+  // Maximum depth
+  private int maxDepth;
+  // private long[] rangeHashID
 
 Review comment:
   done

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
[hidden email]


With regards,
Apache Git Services