[GitHub] [carbondata] ajantha-bhat 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]

ajantha-bhat 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_r356561819
 
 

 ##########
 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
+  // Hashid range, 0 min, 1 Max
+  private QuadNode northWest = null;
+  private QuadNode northEast = null;
+  private QuadNode southWest = null;
+  private QuadNode southEast = null;
+
+
+  /* Quadrant division of a rectangular region：:
+
+     TL(1)   |    TR(0)
+   ----------|-----------
+     BL(2)   |    BR(3)
+  */
+
+  public enum ChildEnum {
+    TOPLEFT, TOPRIGHT, BOTTOMLEFT, BOTTOMRIGHT
+  }
+
+  /**
+   * build func
+   *
+   * @param rect         region
+   * @param grid         raster data
+   * @param currentDepth Current depth
+   * @param maxDepth     Maximum depth
+   */
+  public QuadNode(QuadRect rect, GridData grid, int currentDepth, int maxDepth) {
+    this.rect = rect;
+    this.grid = grid;
+    this.currentDepth = currentDepth;
+    this.maxDepth = maxDepth;
+    // this.rangeHashID = this.grid.getHashIDRange();
+  }
+
+
+  /**
+   * Insert a given polygon into a quadtree
+   *
+   * @param queryPolygon Given polygon area
+   */
+  public boolean insert(List<double[]> queryPolygon) {
+    Polygon polygonGeo = GeometryOperation.getPolygonByDoubleList(queryPolygon);
+    if (polygonGeo != null) {
+      // Insert polygon into area
+      // Before inserting, use the external rectangle to judge whether they are separated.
+      // If they are, they are separated from the rectangle. Otherwise, judge the rectangle
+      // The functions that enter the insert are inseparable. Judge first in the outer layer
+      Geometry rect = polygonGeo.getEnvelope();
+      List<Point2D.Double> polygon = this.rect.getPolygonPointList();
+      if (GeometryOperation.disjoint(rect, polygon)) {
+        LOGGER.info("quad tree disJoint with query polygon envelope return");
+        return false;
+      } else {
+        if (!GeometryOperation.disjoint(polygonGeo, polygon)) {
+          LOGGER.info("start to insert query polygon to tree");
+          insert(polygonGeo);
+          LOGGER.info("end to insert query polygon to tree");
+          return true;
+        } else {
+          LOGGER.info("polygon disJoint with query polygon return");
+          return false;
+        }
+      }
+    } else {
+      LOGGER.info("query polygon is null return");
+      return false;
+    }
+  }
+
+  /**
+   * Insert a region into the point of a quadtree. All the regions that can
+   * be inserted are not disjoin regions. They must not be separated
+   *
+   * @param queryPolygon Area to be inserted
+   */
+  public void insert(Polygon queryPolygon) {
+    List<Point2D.Double> polygon = this.rect.getPolygonPointList();
+    Geometry queryRect = queryPolygon.getEnvelope();
+    if (isMaxDepth()) {
+      // If it is the final grid division, the center point of the grid area will be
+      // calculated to determine whether the center point is in the polygon
+      // If they are inseparable and not included, they must be intersected and in state.
+      // Intersecting indicates partial selection, or they may not be selected when they are
+      // the last node
+      Point2D.Double middlePoint = this.rect.getMiddlePoint();
+      if (!GeometryOperation.disjoint(queryPolygon, middlePoint)) {
+        // Select this area and fill in the data range
+        this.grid.setStatus(GridData.STATUS_ALL);
+      } else {
+        // If not, do nothing
+        this.grid.setStatus(GridData.STATUS_DISJOIN);
+      }
+    } else {
+      if (GeometryOperation.contains(queryPolygon, polygon)) {
+        // If the point area is included in the area to be queried, the area is selected as a
+        // whole. After the area is selected as a whole, the data range needs to be filled in
+        this.grid.setStatus(GridData.STATUS_ALL);
+      } else {
+        // Set state to partially contain
+        this.grid.setStatus(GridData.STATUS_CONTAIN);
+        // If it is less than the maximum depth, it will cut down and find its corresponding
+        // four child nodes directly
+        List<Point2D.Double> rectList = this.rect.getSplitRect();
+        // Judge the area and create children only when there is intersection. Otherwise, skip.
+        // Judge four quadrants respectively
+        List<Point2D.Double> topLeft = Arrays.asList(rectList.get(0), rectList.get(1),
+            rectList.get(4), rectList.get(3));
+        List<Point2D.Double> topRight = Arrays.asList(rectList.get(1), rectList.get(2),
+            rectList.get(5), rectList.get(4));
+        List<Point2D.Double> bottomLeft = Arrays.asList(rectList.get(3), rectList.get(4),
+            rectList.get(7), rectList.get(6));
+        List<Point2D.Double> bottomRight = Arrays.asList(rectList.get(4), rectList.get(5),
+            rectList.get(8), rectList.get(7));
+        long gridRowMiddle = this.grid.startRow + (this.grid.endRow - this.grid.startRow) / 2;
+        long gridColumnMiddle = this.grid.startColumn + (this.grid.endColumn -
+                                                            this.grid.startColumn) / 2;
+        if (!GeometryOperation.disjoint(queryRect, topLeft) && !GeometryOperation
+                                               .disjoint(queryPolygon, topLeft)) {
+          // If they are not separated, select the upper left half of the mesh
+          GridData grid = new GridData(this.grid.startRow, gridRowMiddle, gridColumnMiddle,
+              this.grid.endColumn, this.maxDepth);
+          insertIntoChildren(ChildEnum.TOPLEFT, grid, topLeft, queryPolygon);
+        }
+        if (!GeometryOperation.disjoint(queryRect, topRight) && !GeometryOperation
+                                               .disjoint(queryPolygon, topRight)) {
+          // If not separated, select the upper right half of the mesh
+          GridData grid = new GridData(gridRowMiddle, this.grid.endRow, gridColumnMiddle,
+              this.grid.endColumn, this.maxDepth);
+          insertIntoChildren(ChildEnum.TOPRIGHT, grid, topRight, queryPolygon);
+        }
+        if (!GeometryOperation.disjoint(queryRect, bottomLeft) && !GeometryOperation
+                                                 .disjoint(queryPolygon, bottomLeft)) {
+          // If they are not separated, select the lower left half of the mesh
+          GridData grid = new GridData(this.grid.startRow, gridRowMiddle, this.grid.startColumn,
+              gridColumnMiddle, this.maxDepth);
+          insertIntoChildren(ChildEnum.BOTTOMLEFT, grid, bottomLeft, queryPolygon);
+        }
+        if (!GeometryOperation.disjoint(queryRect, bottomRight) && !GeometryOperation
+                                                  .disjoint(queryPolygon, bottomRight)) {
+          // If not, select the lower right half of the mesh
+          GridData grid = new GridData(gridRowMiddle, this.grid.endRow, this.grid.startColumn,
+              gridColumnMiddle, this.maxDepth);
+          insertIntoChildren(ChildEnum.BOTTOMRIGHT, grid, bottomRight, queryPolygon);
+        }
+        // When processing four children, it is necessary to judge whether all four children
+        // are selected. If selected, they will be merged
+        combineChild();
+        // When there is a non empty node and the node status is disjoin, all nodes except this
+        // node are null,need to refresh the node state to disjoin and set all its children to
+        // be empty
+        checkAndSetDisJoin();
+      }
+    }
+  }
+
+  /**
+   * Insert grid into tree child node
+   *
+   * @param childType Child node
+   * @param rectangle The area represented by the child's s node
+   */
+  private void insertIntoChildren(ChildEnum childType, GridData grid,
+                                  List<Point2D.Double> rectangle, Polygon queryPolygon) {
+    QuadRect rect = new QuadRect(rectangle.get(0), rectangle.get(2));
+    switch (childType) {
+      case TOPLEFT:
+        this.northWest = new QuadNode(rect, grid, currentDepth + 1, maxDepth);
+        this.northWest.insert(queryPolygon);
+        break;
+      case TOPRIGHT:
+        this.northEast = new QuadNode(rect, grid, currentDepth + 1, maxDepth);
+        this.northEast.insert(queryPolygon);
+        break;
+      case BOTTOMLEFT:
+        this.southWest = new QuadNode(rect, grid, currentDepth + 1, maxDepth);
+        this.southWest.insert(queryPolygon);
+        break;
+      case BOTTOMRIGHT:
+        this.southEast = new QuadNode(rect, grid, currentDepth + 1, maxDepth);
+        this.southEast.insert(queryPolygon);
+        break;
+      default:
+        LOGGER.warn("child type not match");
+    }
+  }
+
+  /**
+   * Merge child nodes
+   */
+  private void combineChild() {
+    if (checkChildCanCombine(this.northWest) && checkChildCanCombine(this.northEast) &&
+            checkChildCanCombine(this.southWest) && checkChildCanCombine(this.southEast)) {
+      // Can merge
+      this.getGrid().setStatus(GridData.STATUS_ALL);
+      this.northWest.clean();
+      this.northWest = null;
+      this.northEast.clean();
+      this.northEast = null;
+      this.southWest.clean();
+      this.southWest = null;
+      this.southEast.clean();
+      this.southEast = null;
+    }
+  }
+
+  /**
+   * Determine whether the child node can be merged.
+   * When the child node is not empty and the grid data state of the
+   * child node is all inclusive, it can be merged
+   *
+   * @param child Child nodes in the tree
+   * @return true Can merge,false Can not merge
+   */
+  private boolean checkChildCanCombine(QuadNode child) {
+    return child != null && child.getGrid().getStatus() == GridData.STATUS_ALL;
+  }
+
+  /**
+   * Determine whether the region can be set to disjoin state
+   */
+  private void checkAndSetDisJoin() {
+    // Flag allowed to be modified. It is not allowed to be modified by default
+    boolean canChange = false;
+    // If the status of a child node is status "disjoin, the child node can be left blank
+    if (this.northEast != null && this.northEast.getGrid().getStatus() == GridData.STATUS_DISJOIN) {
+      this.northEast.clean();
+      this.northEast = null;
+      canChange = true;
+    }
+    if (this.northWest != null && this.northWest.getGrid().getStatus() == GridData.STATUS_DISJOIN) {
+      this.northWest.clean();
+      this.northWest = null;
+      canChange = true;
+    }
+    if (this.southWest != null && this.southWest.getGrid().getStatus() == GridData.STATUS_DISJOIN) {
+      this.southWest.clean();
+      this.southWest = null;
+      canChange = true;
+    }
+    if (this.southEast != null && this.southEast.getGrid().getStatus() == GridData.STATUS_DISJOIN) {
+      this.southEast.clean();
+      this.southEast = null;
+      canChange = true;
+    }
+    if (canChange) {
+      if (childrenIsNull()) {
+        this.getGrid().setStatus(GridData.STATUS_DISJOIN);
+      }
+    }
+  }
+
+  /**
+   * Get the area of the node
+   *
+   * @return rect
+   */
+  public QuadRect getRect() {
+    return rect;
+  }
+
+  public GridData getGrid() {
+    return grid;
+  }
+
+  /**
+   * Determine whether the leaf node has been reached
+   *
+   * @return true Already achieved,false not achieved
+   */
+  protected boolean isMaxDepth() {
+    return currentDepth > maxDepth;
+  }
+
+  /**
+   * Judge whether the child node is empty
+   *
+   * @return true Child node is empty, false Child node is not empty
+   */
+  public boolean childrenIsNull() {
+    return this.northWest == null && this.northEast == null && this.southWest == null
+               && this.southEast == null;
+  }
+
+  /**
+   * Clean up the nodes of the tree
+   */
+  public void clean() {
+    rect = null;
+    grid = null;
+    if (northWest != null) northWest.clean();
+    if (northEast != null) northEast.clean();
+    if (southWest != null) southWest.clean();
+    if (southEast != null) southEast.clean();
+  }
+
+  /**
+   * Get the child node of a tree node
+   *
+   * @param childType Enumeration value of child node
+   * @return Tree object
+   */
+  public QuadNode getChildren(ChildEnum childType) {
+    switch (childType) {
+      case TOPLEFT:
+        return this.northWest;
+      case TOPRIGHT:
+        return this.northEast;
+      case BOTTOMRIGHT:
+        return this.southEast;
+      case BOTTOMLEFT:
+        return this.southWest;
+      default:
+        return null;
+    }
+  }
+
+  /**
+   * Get the status of the current node
+   *
+   * @return STATUS_CONTAIN 0 or STATUS_ALL 1
+   */
+  public int getNodeStatus() {
+    return grid.getStatus();
+  }
+
+}
+
+/**
+ * Quad tree object
+ */
+public class QuadTreeCls {
+  private static final Logger LOGGER =
+      LogServiceFactory.getLogService(QuadTreeCls.class.getName());
+  private QuadNode root;
+  /**
+   * Create the root node, which contains the entire grid area
+   * @param depth Depth of tree
+   * @param left Lower left point of coordinate
+   * @param down Lower left point of coordinate
+   * @param width Width of area
+   * @param height Height of area
+   */
+  public QuadTreeCls(double left, double down, double width, double height, int depth) {
+    QuadRect rect = new QuadRect(left, down,  width,  height);
+    // Maximum column length based on depth
+    int maxColumn = (int) Math.pow(2, depth);
+    // write row,column data to grid use it to build hash id
+    GridData grid = new GridData(0, maxColumn, 0, maxColumn, depth);
+    root = new QuadNode(rect, grid, 1, depth);
+    LOGGER.info("build quad tree successfully, the max column is " + maxColumn);
+  }
+
+  /**
+   * Given the cutting depth, the region range of quadtree, and the query region, build a quadtree
+   * @param vertexes List of polygons given at query time
+   */
+  public boolean insert(List<double[]> vertexes) {
+    // If the initial area is larger than the root node, exit directly
+    QuadRect outerRectangle = getOuterRectangle(vertexes);
+    if (this.root.getRect().outsideBox(outerRectangle)) {
+      LOGGER.warn("the query outer rect is bigger than the root node return");
+      return false;
+    }
+    return root.insert(vertexes);
+  }
+
+  /**
+   * Obtain the range of all nodes of tree species
+   * @return Scope List
+   */
+  public List<Long[]> getNodesData() {
+    List<Long[]> result = new ArrayList<>();
+    getNodeGridRange(root, result);
+    sortRange(result);
+    combineRange(result);
+    LOGGER.info("after query the range size is " + result.size());
+    return result;
+  }
+
+  /**
+   * Get the data range of a node
+   * @param node node
+   * @param result Return value
+   */
+  public void getNodeGridRange(QuadNode node, List<Long[]> result) {
+    if (node.getNodeStatus() == GridData.STATUS_ALL) {
+      Long[] range = node.getGrid().getHashIDRange();
+      result.add(range);
+    } else {
+      // The order of addition is, bottom left, top left, top right, bottom right
+      getSubChildGridRange(node, QuadNode.ChildEnum.BOTTOMLEFT, result);
+      getSubChildGridRange(node, QuadNode.ChildEnum.TOPLEFT, result);
+      getSubChildGridRange(node, QuadNode.ChildEnum.TOPRIGHT, result);
+      getSubChildGridRange(node, QuadNode.ChildEnum.BOTTOMRIGHT, result);
+    }
+  }
+
+  /**
+   * Get the range of a node's child nodes
+   * @param node tree node
+   * @param childType Child node type
+   * @param result  return value
+   */
+  public void getSubChildGridRange(QuadNode node, QuadNode.ChildEnum childType,
+                                   List<Long[]> result) {
+    QuadNode child = node.getChildren(childType);
+    if (child != null) {
+      getNodeGridRange(child, result);
+    }
+  }
+
+  /**
+   * Sorting and merging area results
+   * @param rangeList Region list
+   */
+  public void sortRange(List<Long[]> rangeList) {
+    // When sorting, you only need to sort the first node of long [],
+    // because you can ensure that the interval is not repeated
+    rangeList.sort(new Comparator<Long[]>() {
+      @Override
+      public int compare(Long[] x, Long[] y) {
+        return Long.compare(x[0], y[0]);
+      }
+    });
+  }
+
+  /**
+   * If the ordered data is merged, the number of data segments after merging may be reduced.
+   * @param rangeList Area list, sorted
+   */
+  public void combineRange(List<Long[]> rangeList) {
+    if (rangeList.size() > 1) {
+      for (int i = 0, j = i + 1; i < rangeList.size() - 1; i++, j++) {
+        long previousEnd = rangeList.get(i)[1];
+        long nextStart = rangeList.get(j)[0];
+        if (previousEnd + 1 == nextStart) {
+          rangeList.get(j)[0] = rangeList.get(i)[0];
+          rangeList.remove(i);
+        }
+      }
+    }
+  }
+
+  /**
+   * Get the circumscribed rectangle of a polygon
+   * @param polygon polygon
+   * @return Rectangular area
+   */
+  private QuadRect getOuterRectangle(List<double[]> polygon) {
+    double left = Double.MAX_VALUE;
+    double top = Double.MIN_VALUE;
+    double right = Double.MIN_VALUE;
+    double bottom = Double.MAX_VALUE;
+    for (double[] point : polygon) {
+      if (point[0] < left) {
+        left = point[0];
+      }
+      if (point[0] > right) {
+        right = point[0];
+      }
+      if (point[1] < bottom) {
+        bottom = point[1];
+      }
+      if (point[1] > top) {
+        top = point[1];
+      }
+    }
+    Point2D.Double topLeft = new Point2D.Double(left, top);
+    Point2D.Double bottomRight = new Point2D.Double(right, bottom);
+    return new QuadRect(topLeft, bottomRight);
+  }
+
+  public QuadNode getRoot() {
+    return root;
+  }
+
+  public void clean() {
+    if (root != null) {
+      root.clean();
+      root = null;
+    }
+  }
+}
+
+
 
 Review comment:
   check and remove empty lines in all the places of this PR

----------------------------------------------------------------
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