You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@carbondata.apache.org by aj...@apache.org on 2020/02/12 04:53:02 UTC
[carbondata] branch master updated: [CARBONDATA-3548] Implement
hash id generation and quadtree processing for polygon geo spatial queries
This is an automated email from the ASF dual-hosted git repository.
ajantha pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/carbondata.git
The following commit(s) were added to refs/heads/master by this push:
new 9608607 [CARBONDATA-3548] Implement hash id generation and quadtree processing for polygon geo spatial queries
9608607 is described below
commit 9608607b1cef7e22e487a57f75719577f19e3a43
Author: litao <li...@126.com>
AuthorDate: Wed Feb 5 19:11:22 2020 +0800
[CARBONDATA-3548] Implement hash id generation and quadtree processing for polygon geo spatial queries
Why is this PR needed?
To support geo spatial feature in carbondata
What changes were proposed in this PR?
Implement hash id generation and quadtree processing for polygon geo
spatial queries
Does this PR introduce any user interface change?
No
Is any new testcase added?
Added functional UT, end to end test cases will be added in another PR
This closes #3481
---
geo/pom.xml | 12 +-
.../org/apache/carbondata/geo/GeoHashImpl.java | 240 +++++-
.../org/apache/carbondata/geo/QuadTreeCls.java | 922 +++++++++++++++++++++
.../org/apache/carbondata/geo/QuadTreeClsTest.java | 325 ++++++++
4 files changed, 1489 insertions(+), 10 deletions(-)
diff --git a/geo/pom.xml b/geo/pom.xml
index 4fdcea6..38bb9bd 100644
--- a/geo/pom.xml
+++ b/geo/pom.xml
@@ -56,9 +56,19 @@
<artifactId>scalatest_${scala.binary.version}</artifactId>
<scope>test</scope>
</dependency>
+ <dependency>
+ <groupId>org.locationtech.jts</groupId>
+ <artifactId>jts-core</artifactId>
+ <version>1.16.1</version>
+ </dependency>
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <scope>test</scope>
+ </dependency>
</dependencies>
<build>
- <testSourceDirectory>src/test/scala</testSourceDirectory>
+ <testSourceDirectory>src/test/java</testSourceDirectory>
<plugins>
<plugin>
<artifactId>maven-compiler-plugin</artifactId>
diff --git a/geo/src/main/java/org/apache/carbondata/geo/GeoHashImpl.java b/geo/src/main/java/org/apache/carbondata/geo/GeoHashImpl.java
index 7e9803e..a2fa7ce 100644
--- a/geo/src/main/java/org/apache/carbondata/geo/GeoHashImpl.java
+++ b/geo/src/main/java/org/apache/carbondata/geo/GeoHashImpl.java
@@ -22,11 +22,14 @@ import java.util.List;
import java.util.Map;
import org.apache.carbondata.common.exceptions.sql.MalformedCarbonCommandException;
+import org.apache.carbondata.common.logging.LogServiceFactory;
import org.apache.carbondata.core.constants.CarbonCommonConstants;
import org.apache.carbondata.core.util.CustomIndex;
import org.apache.commons.lang3.StringUtils;
+import org.apache.log4j.Logger;
+
/**
* GeoHash custom implementation.
* This class extends {@link CustomIndex}. It provides methods to
@@ -38,10 +41,64 @@ import org.apache.commons.lang3.StringUtils;
* columns.
*/
public class GeoHashImpl extends CustomIndex<List<Long[]>> {
+ private static final Logger LOGGER =
+ LogServiceFactory.getLogService(GeoHashImpl.class.getName());
+
+ // conversion factor of angle to radian
+ private static final double CONVERT_FACTOR = 180.0;
+ // Earth radius
+ private static final double EARTH_RADIUS = 6371004.0;
+ // Latitude of coordinate origin
+ private double oriLatitude;
+ // User defined maximum longitude of map
+ private double userDefineMaxLongitude;
+ // User defined maximum latitude of map
+ private double userDefineMaxLatitude;
+ // User defined map minimum longitude
+ private double userDefineMinLongitude;
+ // User defined map minimum latitude
+ private double userDefineMinLatitude;
+ // The maximum longitude of the completed map after calculation
+ private double CalculateMaxLongitude;
+ // The maximum latitude of the completed map after calculation
+ private double CalculateMaxLatitude;
+ // Grid length is in meters
+ private int gridSize;
+ // cos value of latitude of origin of coordinate
+ private double mCos;
+ // The degree of Y axis corresponding to each grid size length
+ private double deltaY;
+ // Each grid size length should be the degree of X axis
+ private double deltaX;
+ // Degree * coefficient of Y axis corresponding to each grid size length
+ private double deltaYByRatio;
+ // Each grid size length should be X-axis Degree * coefficient
+ private double deltaXByRatio;
+ // The number of knives cut for the whole area (one horizontally and one vertically)
+ // is the depth of quad tree
+ private int cutLevel;
+ // used to convert the latitude and longitude of double type to int type for calculation
+ private int conversionRatio;
+ // * Constant of coefficient
+ private double lon0ByRation;
+ // * Constant of coefficient
+ private double lat0ByRation;
+
+
/**
* Initialize the geohash index handler instance.
- * @param handlerName
- * @param properties
+ * the properties is like that:
+ * TBLPROPERTIES ('INDEX_HANDLER'='mygeohash',
+ * 'INDEX_HANDLER.mygeohash.type'='geohash',
+ * 'INDEX_HANDLER.mygeohash.sourcecolumns'='longitude, latitude',
+ * 'INDEX_HANDLER.mygeohash.gridSize'=''
+ * 'INDEX_HANDLER.mygeohash.minLongitude'=''
+ * 'INDEX_HANDLER.mygeohash.maxLongitude'=''
+ * 'INDEX_HANDLER.mygeohash.minLatitude'=''
+ * 'INDEX_HANDLER.mygeohash.maxLatitude'=''
+ * 'INDEX_HANDLER.mygeohash.orilatitude''')
+ * @param handlerName the class name of generating algorithm
+ * @param properties input properties,please check the describe
* @throws Exception
*/
@Override
@@ -141,7 +198,15 @@ public class GeoHashImpl extends CustomIndex<List<Long[]>> {
CarbonCommonConstants.INDEX_HANDLER, CONVERSION_RATIO));
}
- // TODO: Fill the values to the instance fields
+ // Fill the values to the instance fields
+ this.oriLatitude = Double.valueOf(originLatitude);
+ this.userDefineMaxLongitude = Double.valueOf(maxLongitude);
+ this.userDefineMaxLatitude = Double.valueOf(maxLatitude);
+ this.userDefineMinLongitude = Double.valueOf(minLongitude);
+ this.userDefineMinLatitude = Double.valueOf(minLatitude);
+ this.gridSize = Integer.parseInt(gridSize);
+ this.conversionRatio = Integer.parseInt(conversionRatio);
+ calculateData();
}
/**
@@ -162,20 +227,177 @@ public class GeoHashImpl extends CustomIndex<List<Long[]>> {
if (!(sources.get(0) instanceof Long) || !(sources.get(1) instanceof Long)) {
throw new RuntimeException("Source columns must be of Long type.");
}
- //TODO: generate geohashId
- return String.valueOf(0);
+ Long longitude = (Long) sources.get(0);
+ Long latitude = (Long) sources.get(1);
+ // generate the hash code
+ int[] gridPoint = calculateID(longitude, latitude);
+ Long hashId = createHashID(gridPoint[0], gridPoint[1]);
+ return String.valueOf(hashId);
}
/**
* Query processor for GeoHash.
- * @param polygon
+ * example: POLYGON (35 10, 45 45, 15 40, 10 20, 35 10)
+ * so there will be a sample check
+ * @param polygon a group of pints, close out to form an area
* @return Returns list of ranges of GeoHash IDs
* @throws Exception
*/
@Override
public List<Long[]> query(String polygon) throws Exception {
- List<Long[]> rangeList = new ArrayList<Long[]>();
- // TODO: process the polygon coordinates and generate the list of ranges of GeoHash IDs
- return rangeList;
+ if (!validate(polygon)) {
+ return null;
+ } else {
+ String[] pointList = polygon.trim().split(",");
+ List<double[]> queryList = new ArrayList<>();
+ for (String str: pointList) {
+ String[] points = splitString(str);
+ if (2 != points.length) {
+ throw new RuntimeException("longitude and latitude is a pair need 2 data");
+ } else {
+ try {
+ queryList.add(new double[] {Double.valueOf(points[0]), Double.valueOf(points[1])});
+ } catch (NumberFormatException e) {
+ throw new RuntimeException("can not covert the string data to double", e);
+ }
+ }
+ }
+ if (!checkPointsSame(pointList[0], pointList[pointList.length - 1])) {
+ throw new RuntimeException("the first point and last point in polygon should be same");
+ } else {
+ List<Long[]> rangeList = getPolygonRangeList(queryList);
+ return rangeList;
+ }
+ }
+ }
+
+ private String[] splitString(String str) {
+ return str.trim().split("\\s+");
+ }
+
+ private boolean checkPointsSame(String point1, String point2) throws Exception {
+ String[] points1 = splitString(point1);
+ String[] points2 = splitString(point2);
+ return points1[0].equals(points2[0]) && points1[1].equals(points2[1]);
+ }
+
+ private boolean validate(String polygon) throws Exception {
+ String[] pointList = polygon.trim().split(",");
+ if (4 > pointList.length) {
+ throw new RuntimeException("polygon need at least 3 points, really has " + pointList.length);
+ }
+ return true;
+ }
+
+ /**
+ * use query polygon condition to get the hash id list, the list is merged and sorted.
+ * @param queryList polygon points close out to form an area
+ * @return hash id list
+ * @throws Exception
+ */
+ private List<Long[]> getPolygonRangeList(List<double[]> queryList) throws Exception {
+ QuadTreeCls qTreee = new QuadTreeCls(userDefineMinLongitude, userDefineMinLatitude,
+ CalculateMaxLongitude, CalculateMaxLatitude, cutLevel);
+ qTreee.insert(queryList);
+ return qTreee.getNodesData();
+ }
+
+ /**
+ * After necessary attributes, perform necessary calculation
+ * @throws Exception
+ */
+ private void calculateData() throws Exception {
+ // Angular to radian, radians = (Math.PI / 180) * degrees
+ // Cosine value of latitude angle of origin
+ this.mCos = Math.cos(this.oriLatitude / this.conversionRatio * Math.PI / CONVERT_FACTOR);
+ // get δx=L∗360/(2πR∗cos(lat))
+ this.deltaX = (this.gridSize * 360) / (2 * Math.PI * EARTH_RADIUS * this.mCos);
+ this.deltaXByRatio = this.deltaX * this.conversionRatio;
+ // get δy=L∗360/2πR
+ this.deltaY = (this.gridSize * 360) / (2 * Math.PI * EARTH_RADIUS);
+ this.deltaYByRatio = this.deltaY * this.conversionRatio;
+ LOGGER.info("after spatial calculate delta X is: " + String.format("%f", this.deltaX)
+ + "the delta Y is: " + String.format("%f", this.deltaY));
+ LOGGER.info("after spatial calculate X ByRatio is: " + String.format("%f", this.deltaXByRatio)
+ + "the Y ByRatio is: " + String.format("%f", this.deltaYByRatio));
+ // Calculate the complement area and grid i,j for grid number
+ // Xmax = x0+(2^n∗δx) Ymax = y0+(2^n∗δx) Where n is the number of cut
+ // Where x0, Y0 are the minimum x, y coordinates of a given region，
+ // Xmax >= maxLongitude Ymax >= maxLatitude
+ // In the calculation process, first substitute maxlongitude and maxlatitude to calculate n.
+ // if n is not an integer, then take the next integer of N, and then substitute to find
+ // xmax and ymax。
+ this.calculateArea();
+ }
+
+ /**
+ * Calculate the complement area, including the range of the complement area, t
+ * he number of knives cut and the depth of the quad tree
+ */
+ private void calculateArea() {
+ // step 1 calculate xn, yn by using maxLongitude, maxLatitude, minLongitude, minLatitude
+ // substitution formula
+ // Here, the user's given area is mostly rectangle, which needs to be extended to
+ // square processing to find the maximum value of XN and yn
+ // n=log_2 （Xmax−X0)/δx， log_2 （Ymax−Y0)/δy
+ userDefineMinLongitude = userDefineMinLongitude - deltaX / 2;
+ userDefineMaxLongitude = userDefineMaxLongitude + deltaX / 2;
+ userDefineMinLatitude = userDefineMinLatitude - deltaY / 2;
+ userDefineMaxLatitude = userDefineMaxLatitude + deltaY / 2;
+
+ this.lon0ByRation = userDefineMinLongitude * this.conversionRatio;
+ this.lat0ByRation = userDefineMinLatitude * this.conversionRatio;
+
+ double Xn = Math.log((userDefineMaxLongitude - userDefineMinLongitude) / deltaX)
+ / Math.log(2);
+ double Yn = Math.log((userDefineMaxLatitude - userDefineMinLatitude) / deltaY)
+ / Math.log(2);
+ double doubleMax = Math.max(Xn, Yn);
+ this.cutLevel = doubleMax % 1 == 0 ? (int) doubleMax : (int) (doubleMax + 1);
+ // step 2 recalculate the region according to the number of segmentation
+ this.CalculateMaxLongitude = userDefineMinLongitude + Math.pow(2, this.cutLevel)
+ * deltaX;
+ this.CalculateMaxLatitude = userDefineMinLatitude + Math.pow(2, this.cutLevel)
+ * deltaY;
+ LOGGER.info("After spatial calculate the cut level is: " + String.format("%d", this.cutLevel));
+ LOGGER.info("the min longitude is: " + String.format("%f", this.userDefineMinLongitude) +
+ " the max longitude is: " + String.format("%f", this.CalculateMaxLongitude));
+ LOGGER.info("the min latitude is: " + String.format("%f", this.userDefineMinLatitude) +
+ " the max latitude is: " + String.format("%f", this.CalculateMaxLatitude));
+ }
+
+ /**
+ * Through grid index coordinates and calculation of hashid, grid latitude and longitude
+ * coordinates can be transformed by latitude and longitude
+ * @param longitude Longitude, the actual longitude and latitude are processed by * coefficient,
+ * and the floating-point calculation is converted to integer calculation
+ * @param latitude Latitude, the actual longitude and latitude are processed by * coefficient,
+ * and the floating-point calculation is converted to integer calculation.
+ * @return Grid ID value [row, column] column starts from 1
+ */
+ private int[] calculateID(long longitude, long latitude) throws Exception {
+ try {
+ int row = (int) ((longitude - this.lon0ByRation) / this.deltaXByRatio);
+ int column = (int) ((latitude - this.lat0ByRation) / this.deltaYByRatio);
+ return new int[]{row, column};
+ } catch (ArithmeticException e) {
+ throw new RuntimeException("can not divide by zero.");
+ }
+ }
+
+ /**
+ * Calculate the corresponding hashid value from the grid coordinates
+ * @param row Gridded row index
+ * @param column Gridded column index
+ * @return hash id
+ */
+ private long createHashID(long row, long column) {
+ long index = 0L;
+ for (int i = 0; i < cutLevel + 1; i++) {
+ long x = (row >> i) & 1; // take position I
+ long y = (column >> i) & 1;
+ index = index | (x << (2 * i + 1)) | (y << 2 * i);
+ }
+ return index;
}
}
diff --git a/geo/src/main/java/org/apache/carbondata/geo/QuadTreeCls.java b/geo/src/main/java/org/apache/carbondata/geo/QuadTreeCls.java
new file mode 100644
index 0000000..fdd5c8f
--- /dev/null
+++ b/geo/src/main/java/org/apache/carbondata/geo/QuadTreeCls.java
@@ -0,0 +1,922 @@
+/*
+ * 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);
+ }
+ // making a closed polygon by keeping first point and last point same
+ 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 < 4) {
+ return null;
+ } else {
+ Coordinate[] rect = new Coordinate[size];
+ for (int i = 0; i < size; i++) {
+ rect[i] = new Coordinate(polygon.get(i)[0], polygon.get(i)[1]);
+ }
+ 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;
+ public Point2D.Double topLeft;
+ public Point2D.Double topRight;
+ public Point2D.Double bottomRight;
+ public Point2D.Double bottomLeft;
+
+ /**
+ * 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;
+ this.topLeft = new Point2D.Double(this.left, this.top);
+ this.topRight = new Point2D.Double(this.right, this.top);
+ this.bottomRight = new Point2D.Double(this.right, this.bottom);
+ this.bottomLeft = new Point2D.Double(this.left, this.bottom);
+ }
+
+ /**
+ * 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;
+ this.topLeft = new Point2D.Double(this.left, this.top);
+ this.topRight = new Point2D.Double(this.right, this.top);
+ this.bottomRight = new Point2D.Double(this.right, this.bottom);
+ this.bottomLeft = new Point2D.Double(this.left, this.bottom);
+ }
+
+ /**
+ * 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 List of vertices in rectangular area
+ */
+ public List<Point2D.Double> getPolygonPointList() {
+ List<Point2D.Double> polygon = new ArrayList<>();
+ polygon.add(this.topLeft);
+ polygon.add(this.topRight);
+ polygon.add(this.bottomRight);
+ polygon.add(this.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]);
+
+ List<Point2D.Double> rectList = new ArrayList<>();
+ rectList.add(this.topLeft);
+ rectList.add(middleTop);
+ rectList.add(this.topRight);
+
+ rectList.add(leftMiddle);
+ rectList.add(middle);
+ rectList.add(rightMiddle);
+
+ rectList.add(this.bottomLeft);
+ rectList.add(middleBottom);
+ rectList.add(this.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; // take position 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;
+ // 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;
+ }
+
+ /**
+ * 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 (4 > vertexes.size()) {
+ throw new RuntimeException("polygon at least need 4 points, first and last is same.");
+ }
+ if (!isPointsSame(vertexes.get(0), vertexes.get(vertexes.size() - 1))) {
+ throw new RuntimeException("please make first point the same as last point");
+ } else {
+ // If the initial area is larger than the root node, exit directly
+ QuadRect outerRectangle = getOuterRectangle(vertexes.subList(0, vertexes.size() - 1));
+ 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.get(i)[0] = null;
+ rangeList.get(i)[1] = null;
+ }
+ }
+ rangeList.removeIf(item -> item[0] == null && item[1] == null);
+ }
+ }
+
+ /**
+ * 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;
+ }
+ }
+
+ /**
+ * check the 2 point is same.
+ * because the queryList has been checked so no need to check x and y
+ * @param x a double[] has 2 data
+ * @param y a double[] has 2 data
+ * @return true 2 point is same, false 2 point is not same
+ */
+ private boolean isPointsSame(double[] x, double[] y) {
+ return Double.toString(x[0]).equals(Double.toString(y[0]))
+ && Double.toString(x[1]).equals(Double.toString(y[1]));
+ }
+}
+
+
+
+
+
+
+
diff --git a/geo/src/test/java/org/apache/carbondata/geo/QuadTreeClsTest.java b/geo/src/test/java/org/apache/carbondata/geo/QuadTreeClsTest.java
new file mode 100644
index 0000000..0eecbae
--- /dev/null
+++ b/geo/src/test/java/org/apache/carbondata/geo/QuadTreeClsTest.java
@@ -0,0 +1,325 @@
+/*
+ * 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 org.junit.*;
+import org.junit.rules.ExpectedException;
+
+import java.util.ArrayList;
+import java.util.List;
+
+
+/**
+ * QuadTreeClsTest Tester.
+ */
+public class QuadTreeClsTest {
+
+ @Rule
+ public ExpectedException exception = ExpectedException.none();
+
+ QuadTreeCls qtreee;
+
+ @Before
+ public void before() throws Exception {
+ qtreee = new QuadTreeCls(0, 0, 16, 16, 4 );
+ }
+
+ @After
+ public void after() throws Exception {
+ qtreee.clean();
+ }
+
+ @Test
+ public void testInsertPolygonFirstAndLastPoint() throws Exception {
+ //Insert the entire area, directly root
+ List<double[]> pointList = new ArrayList<>();
+ pointList.add(new double[] {0, 0});
+ pointList.add(new double[] {0, 16});
+ pointList.add(new double[] {16, 16});
+ pointList.add(new double[] {16, 0});
+ exception.expect(RuntimeException.class);
+ exception.expectMessage("please make first point the same as last point");
+ qtreee.insert(pointList);
+ }
+
+ /**
+ * The test just inserts the entire coordinate area
+ */
+ @Test
+ public void testInsertPolygonFullRange() throws Exception {
+ //Insert the entire area, directly root
+ List<double[]> pointList = new ArrayList<>();
+ pointList.add(new double[] {0, 0});
+ pointList.add(new double[] {0, 16});
+ pointList.add(new double[] {16, 16});
+ pointList.add(new double[] {16, 0});
+ pointList.add(new double[] {0, 0});
+ qtreee.insert(pointList);
+ Assume.assumeTrue(qtreee.getRoot().getGrid().getStatus() == GridData.STATUS_ALL);
+ Long[] gridRange = qtreee.getRoot().getGrid().getHashIDRange();
+ Assume.assumeTrue(gridRange[0] == 0);
+ Assume.assumeTrue(gridRange[1] == 255);
+ }
+
+ /**
+ * Test insertion area is larger than the whole area
+ */
+ @Test
+ public void testInsertBiggerPolygon() throws Exception {
+ List<double[]> pointList = new ArrayList<>();
+ pointList.add(new double[] {4.3, 20});
+ pointList.add(new double[] {7.3, 13.8});
+ pointList.add(new double[] {18, 11.8});
+ pointList.add(new double[] {11.5, 6.3});
+ pointList.add(new double[] {4.3, 20});
+
+ qtreee.insert(pointList);
+ QuadNode root = qtreee.getRoot();
+
+ Assume.assumeTrue(root.childrenIsNull());
+ }
+
+ /**
+ * Illegal test insertion area
+ */
+ @Test
+ public void testInsertLessThan3Points() throws Exception {
+ List<double[]> pointList = new ArrayList<>();
+ pointList.add(new double[] {4.3, 9.4});
+ pointList.add(new double[] {7.3, 13.8});
+ exception.expect(RuntimeException.class);
+ exception.expectMessage("polygon at least need 4 points, first and last is same.");
+ qtreee.insert(pointList);
+ QuadNode root = qtreee.getRoot();
+ Assume.assumeTrue(root.childrenIsNull());
+ }
+
+ /**
+ * Test creation Hadid
+ */
+ @Test
+ public void testCreateHashID() throws Exception {
+ GridData grid = new GridData(0,0, 15,15,4);
+ // Here is a grid
+ Assume.assumeTrue(grid.createHashID(0,0) == 0);
+ Assume.assumeTrue(grid.createHashID(0,1) == 1);
+ Assume.assumeTrue(grid.createHashID(1,0) == 2);
+ Assume.assumeTrue(grid.createHashID(1,1) == 3);
+
+ Assume.assumeTrue(grid.createHashID(0,2) == 4);
+ Assume.assumeTrue(grid.createHashID(0,3) == 5);
+ Assume.assumeTrue(grid.createHashID(1,2) == 6);
+ Assume.assumeTrue(grid.createHashID(1,3) == 7);
+
+ Assume.assumeTrue(grid.createHashID(2,0) == 8);
+ Assume.assumeTrue(grid.createHashID(2,1) == 9);
+ Assume.assumeTrue(grid.createHashID(3,0) == 10);
+ Assume.assumeTrue(grid.createHashID(3,1) == 11);
+
+ Assume.assumeTrue(grid.createHashID(2,2) == 12);
+ Assume.assumeTrue(grid.createHashID(2,3) == 13);
+ Assume.assumeTrue(grid.createHashID(3,2) == 14);
+ Assume.assumeTrue(grid.createHashID(3,3) == 15);
+ // Center point
+ Assume.assumeTrue(grid.createHashID(0,4) == 16);
+ Assume.assumeTrue(grid.createHashID(0,5) == 17);
+ Assume.assumeTrue(grid.createHashID(1,4) == 18);
+ Assume.assumeTrue(grid.createHashID(1,5) == 19);
+
+ Assume.assumeTrue(grid.createHashID(0,6) == 20);
+ Assume.assumeTrue(grid.createHashID(0,7) == 21);
+ Assume.assumeTrue(grid.createHashID(1,6) == 22);
+ Assume.assumeTrue(grid.createHashID(1,7) == 23);
+
+ Assume.assumeTrue(grid.createHashID(2,4) == 24);
+ Assume.assumeTrue(grid.createHashID(2,5) == 25);
+ Assume.assumeTrue(grid.createHashID(3,4) == 26);
+ Assume.assumeTrue(grid.createHashID(3,5) == 27);
+
+ Assume.assumeTrue(grid.createHashID(2,6) == 28);
+ Assume.assumeTrue(grid.createHashID(2,7) == 29);
+ Assume.assumeTrue(grid.createHashID(3,6) == 30);
+ Assume.assumeTrue(grid.createHashID(3,7) == 31);
+
+ Assume.assumeTrue(grid.createHashID(15,15) == 255);
+ Assume.assumeTrue(grid.createHashID(8,8) == 192);
+
+ }
+
+ /**
+ * Test inserts a rectangle
+ */
+ @Test
+ public void testQueryOne() throws Exception {
+ List<double[]> pointList = new ArrayList<>();
+ pointList.add(new double[] {4.3, 9.4});
+ pointList.add(new double[] {7.3, 13.8});
+ pointList.add(new double[] {13.6, 11.8});
+ pointList.add(new double[] {11.5, 6.3});
+ pointList.add(new double[] {4.3, 9.4});
+ boolean flag = qtreee.insert(pointList);
+ // First floor
+ QuadNode oneLevel_TOPLEFT = qtreee.getRoot().getChildren(QuadNode.ChildEnum.TOPLEFT);
+ QuadNode oneLevel_TOPRIGHT = qtreee.getRoot().getChildren(QuadNode.ChildEnum.TOPRIGHT);
+ QuadNode oneLevel_BOTTOMRIGHT = qtreee.getRoot().getChildren(QuadNode.ChildEnum.BOTTOMRIGHT);
+ QuadNode oneLevel_BOTTOMLEFT = qtreee.getRoot().getChildren(QuadNode.ChildEnum.BOTTOMLEFT);
+ Assume.assumeTrue(!oneLevel_TOPLEFT.childrenIsNull());
+ Assume.assumeTrue(!oneLevel_TOPRIGHT.childrenIsNull());
+ Assume.assumeTrue(!oneLevel_BOTTOMRIGHT.childrenIsNull());
+ Assume.assumeTrue(oneLevel_BOTTOMLEFT == null);
+ Assume.assumeTrue(oneLevel_TOPLEFT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+ Assume.assumeTrue(oneLevel_TOPRIGHT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+ Assume.assumeTrue(oneLevel_BOTTOMRIGHT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+ // The second floor
+ // oneLevel_TOPLEFT
+ QuadNode twoLevel_TOPLEFT_TOPLEFT = oneLevel_TOPLEFT.getChildren(QuadNode.ChildEnum.TOPLEFT);
+ QuadNode twoLevel_TOPLEFT_TOPRIGHT = oneLevel_TOPLEFT.getChildren(QuadNode.ChildEnum.TOPRIGHT);
+ QuadNode twoLevel_TOPLEFT_BOTTOMRIGHT = oneLevel_TOPLEFT.getChildren(QuadNode.ChildEnum.BOTTOMRIGHT);
+ QuadNode twoLevel_TOPLEFT_BOTTOMLEFT = oneLevel_TOPLEFT.getChildren(QuadNode.ChildEnum.BOTTOMLEFT );
+ Assume.assumeTrue(twoLevel_TOPLEFT_TOPLEFT == null);
+ Assume.assumeTrue(!twoLevel_TOPLEFT_TOPRIGHT.childrenIsNull());
+ Assume.assumeTrue(!twoLevel_TOPLEFT_BOTTOMRIGHT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPLEFT_BOTTOMLEFT == null);
+ //oneLevel_TOPRIGHT
+ QuadNode twoLevel_TOPRIGHT_TOPLEFT = oneLevel_TOPRIGHT.getChildren(QuadNode.ChildEnum.TOPLEFT);
+ QuadNode twoLevel_TOPRIGHT_TOPRIGHT = oneLevel_TOPRIGHT.getChildren(QuadNode.ChildEnum.TOPRIGHT);
+ QuadNode twoLevel_TOPRIGHT_BOTTOMRIGHT = oneLevel_TOPRIGHT.getChildren(QuadNode.ChildEnum.BOTTOMRIGHT);
+ QuadNode twoLevel_TOPRIGHT_BOTTOMLEFT = oneLevel_TOPRIGHT.getChildren(QuadNode.ChildEnum.BOTTOMLEFT );
+ Assume.assumeTrue(!twoLevel_TOPRIGHT_TOPLEFT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPRIGHT_TOPRIGHT == null);
+ Assume.assumeTrue(!twoLevel_TOPRIGHT_BOTTOMRIGHT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPRIGHT_BOTTOMLEFT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPRIGHT_BOTTOMLEFT.getGrid().getStatus() == GridData.STATUS_ALL);
+ //oneLevel_BOTTOMLEFT
+ //null
+
+ // oneLevel_BOTTOMRIGHT
+ QuadNode twoLevel_BOTTOMRIGHT_TOPLEFT = oneLevel_BOTTOMRIGHT.getChildren(QuadNode.ChildEnum.TOPLEFT);
+ QuadNode twoLevel_BOTTOMRIGHT_TOPRIGHT = oneLevel_BOTTOMRIGHT.getChildren(QuadNode.ChildEnum.TOPRIGHT);
+ QuadNode twoLevel_BOTTOMRIGHT_BOTTOMRIGHT = oneLevel_BOTTOMRIGHT.getChildren(QuadNode.ChildEnum.BOTTOMRIGHT);
+ QuadNode twoLevel_BOTTOMRIGHT_BOTTOMLEFT = oneLevel_BOTTOMRIGHT.getChildren(QuadNode.ChildEnum.BOTTOMLEFT );
+ Assume.assumeTrue(!twoLevel_BOTTOMRIGHT_TOPLEFT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_BOTTOMRIGHT_TOPLEFT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+ Assume.assumeTrue(twoLevel_BOTTOMRIGHT_TOPRIGHT == null);
+ Assume.assumeTrue(twoLevel_BOTTOMRIGHT_BOTTOMRIGHT == null);
+ Assume.assumeTrue(twoLevel_BOTTOMRIGHT_BOTTOMLEFT == null);
+
+ // The third level
+ // twoLevel_TOPLEFT_TOPRIGHT
+ QuadNode twoLevel_TOPLEFT_TOPRIGHT_TOPLEFT = twoLevel_TOPLEFT_TOPRIGHT.getChildren(QuadNode.ChildEnum.TOPLEFT);
+ QuadNode twoLevel_TOPLEFT_TOPRIGHT_TOPRIGHT = twoLevel_TOPLEFT_TOPRIGHT.getChildren(QuadNode.ChildEnum.TOPRIGHT);
+ QuadNode twoLevel_TOPLEFT_TOPRIGHT_BOTTOMRIGHT = twoLevel_TOPLEFT_TOPRIGHT.getChildren(QuadNode.ChildEnum.BOTTOMRIGHT);
+ QuadNode twoLevel_TOPLEFT_TOPRIGHT_BOTTOMLEFT = twoLevel_TOPLEFT_TOPRIGHT.getChildren(QuadNode.ChildEnum.BOTTOMLEFT );
+ Assume.assumeTrue(twoLevel_TOPLEFT_TOPRIGHT_TOPLEFT == null);
+ Assume.assumeTrue(twoLevel_TOPLEFT_TOPRIGHT_TOPRIGHT == null);
+ Assume.assumeTrue(!twoLevel_TOPLEFT_TOPRIGHT_BOTTOMRIGHT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPLEFT_TOPRIGHT_BOTTOMRIGHT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+ Assume.assumeTrue(twoLevel_TOPLEFT_TOPRIGHT_BOTTOMLEFT == null);
+ // twoLevel_TOPLEFT_BOTTOMRIGHT
+ QuadNode twoLevel_TOPLEFT_BOTTOMRIGHT_TOPLEFT = twoLevel_TOPLEFT_BOTTOMRIGHT.getChildren(QuadNode.ChildEnum.TOPLEFT);
+ QuadNode twoLevel_TOPLEFT_BOTTOMRIGHT_TOPRIGHT = twoLevel_TOPLEFT_BOTTOMRIGHT.getChildren(QuadNode.ChildEnum.TOPRIGHT);
+ QuadNode twoLevel_TOPLEFT_BOTTOMRIGHT_BOTTOMRIGHT = twoLevel_TOPLEFT_BOTTOMRIGHT.getChildren(QuadNode.ChildEnum.BOTTOMRIGHT);
+ QuadNode twoLevel_TOPLEFT_BOTTOMRIGHT_BOTTOMLEFT = twoLevel_TOPLEFT_BOTTOMRIGHT.getChildren(QuadNode.ChildEnum.BOTTOMLEFT );
+ Assume.assumeTrue(!twoLevel_TOPLEFT_BOTTOMRIGHT_TOPLEFT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPLEFT_BOTTOMRIGHT_TOPLEFT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+
+ Assume.assumeTrue(twoLevel_TOPLEFT_BOTTOMRIGHT_TOPRIGHT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPLEFT_BOTTOMRIGHT_TOPRIGHT.getGrid().getStatus() == GridData.STATUS_ALL);
+
+ Assume.assumeTrue(twoLevel_TOPLEFT_BOTTOMRIGHT_BOTTOMRIGHT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPLEFT_BOTTOMRIGHT_BOTTOMRIGHT.getGrid().getStatus() == GridData.STATUS_ALL);
+
+ Assume.assumeTrue(!twoLevel_TOPLEFT_BOTTOMRIGHT_BOTTOMLEFT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPLEFT_BOTTOMRIGHT_BOTTOMLEFT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+ // twoLevel_TOPRIGHT_TOPLEFT
+ QuadNode twoLevel_TOPRIGHT_TOPLEFT_TOPLEFT = twoLevel_TOPRIGHT_TOPLEFT.getChildren(QuadNode.ChildEnum.TOPLEFT);
+ QuadNode twoLevel_TOPRIGHT_TOPLEFT_TOPRIGHT = twoLevel_TOPRIGHT_TOPLEFT.getChildren(QuadNode.ChildEnum.TOPRIGHT);
+ QuadNode twoLevel_TOPRIGHT_TOPLEFT_BOTTOMRIGHT = twoLevel_TOPRIGHT_TOPLEFT.getChildren(QuadNode.ChildEnum.BOTTOMRIGHT);
+ QuadNode twoLevel_TOPRIGHT_TOPLEFT_BOTTOMLEFT = twoLevel_TOPRIGHT_TOPLEFT.getChildren(QuadNode.ChildEnum.BOTTOMLEFT );
+ Assume.assumeTrue(twoLevel_TOPRIGHT_TOPLEFT_TOPLEFT == null);
+ Assume.assumeTrue(twoLevel_TOPRIGHT_TOPLEFT_TOPRIGHT == null);
+ Assume.assumeTrue(!twoLevel_TOPRIGHT_TOPLEFT_BOTTOMRIGHT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPRIGHT_TOPLEFT_BOTTOMRIGHT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+ Assume.assumeTrue(!twoLevel_TOPRIGHT_TOPLEFT_BOTTOMLEFT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPRIGHT_TOPLEFT_BOTTOMLEFT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+ //twoLevel_TOPRIGHT_BOTTOMRIGHT
+ QuadNode twoLevel_TOPRIGHT_BOTTOMRIGHT_TOPLEFT = twoLevel_TOPRIGHT_BOTTOMRIGHT.getChildren(QuadNode.ChildEnum.TOPLEFT);
+ QuadNode twoLevel_TOPRIGHT_BOTTOMRIGHT_TOPRIGHT = twoLevel_TOPRIGHT_BOTTOMRIGHT.getChildren(QuadNode.ChildEnum.TOPRIGHT);
+ QuadNode twoLevel_TOPRIGHT_BOTTOMRIGHT_BOTTOMRIGHT = twoLevel_TOPRIGHT_BOTTOMRIGHT.getChildren(QuadNode.ChildEnum.BOTTOMRIGHT);
+ QuadNode twoLevel_TOPRIGHT_BOTTOMRIGHT_BOTTOMLEFT = twoLevel_TOPRIGHT_BOTTOMRIGHT.getChildren(QuadNode.ChildEnum.BOTTOMLEFT );
+
+ Assume.assumeTrue(!twoLevel_TOPRIGHT_BOTTOMRIGHT_TOPLEFT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPRIGHT_BOTTOMRIGHT_TOPLEFT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+ Assume.assumeTrue(twoLevel_TOPRIGHT_BOTTOMRIGHT_TOPRIGHT == null);
+ Assume.assumeTrue(twoLevel_TOPRIGHT_BOTTOMRIGHT_BOTTOMRIGHT == null);
+ Assume.assumeTrue(!twoLevel_TOPRIGHT_BOTTOMRIGHT_BOTTOMLEFT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_TOPRIGHT_BOTTOMRIGHT_BOTTOMLEFT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+ // twoLevel_BOTTOMRIGHT_TOPLEFT
+ QuadNode twoLevel_BOTTOMRIGHT_TOPLEFT_TOPLEFT = twoLevel_BOTTOMRIGHT_TOPLEFT.getChildren(QuadNode.ChildEnum.TOPLEFT);
+ QuadNode twoLevel_BOTTOMRIGHT_TOPLEFT_TOPRIGHT = twoLevel_BOTTOMRIGHT_TOPLEFT.getChildren(QuadNode.ChildEnum.TOPRIGHT);
+ QuadNode twoLevel_BOTTOMRIGHT_TOPLEFT_BOTTOMRIGHT = twoLevel_BOTTOMRIGHT_TOPLEFT.getChildren(QuadNode.ChildEnum.BOTTOMRIGHT);
+ QuadNode twoLevel_BOTTOMRIGHT_TOPLEFT_BOTTOMLEFT = twoLevel_BOTTOMRIGHT_TOPLEFT.getChildren(QuadNode.ChildEnum.BOTTOMLEFT );
+ Assume.assumeTrue(!twoLevel_BOTTOMRIGHT_TOPLEFT_TOPLEFT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_BOTTOMRIGHT_TOPLEFT_TOPLEFT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+ Assume.assumeTrue(!twoLevel_BOTTOMRIGHT_TOPLEFT_TOPRIGHT.childrenIsNull());
+ Assume.assumeTrue(twoLevel_BOTTOMRIGHT_TOPLEFT_TOPRIGHT.getGrid().getStatus() == GridData.STATUS_CONTAIN);
+ Assume.assumeTrue(twoLevel_BOTTOMRIGHT_TOPLEFT_BOTTOMRIGHT == null);
+ Assume.assumeTrue(twoLevel_BOTTOMRIGHT_TOPLEFT_BOTTOMLEFT == null);
+
+ }
+
+ /**
+ * Initial result 120->120 123->123 122->122 97->97 99->99 102->102 108->111 104->107 192->207 208->208 210->210 216->216 225->225 228->228 229->229 151->151 157->157 159->159 158->158
+ * Results after sorting 97->97 99->99 102->102 104->107 108->111 120->120 122->122 123->123 151->151 157->157 158->158 159->159 192->207 208->208 210->210 216->216 225->225 228->228 229->229
+ * Combined results 97->97 99->99 102->102 104->111 120->120 122->123 151->151 157->158 159->159 192->208 210->210 216->216 225->225 228->229
+ * @throws Exception
+ */
+ @Test
+ public void testGetRange() throws Exception {
+ List<double[]> pointList = new ArrayList<>();
+ pointList.add(new double[] {4.3, 9.4});
+ pointList.add(new double[] {7.3, 13.8});
+ pointList.add(new double[] {13.6, 11.8});
+ pointList.add(new double[] {11.5, 6.3});
+ pointList.add(new double[] {4.3, 9.4});
+ qtreee.insert(pointList);
+ List<Long[]> data = qtreee.getNodesData();
+
+ // 97->97 99->99 102->102 104->111 120->120 122->123 151->151 157->159 192->208 210->210 216->216 225->225 228->229
+
+ Assume.assumeTrue(checkValidate(data, 0, 97, 97));
+ Assume.assumeTrue(checkValidate(data, 1, 99, 99));
+ Assume.assumeTrue(checkValidate(data, 2, 102, 102));
+ Assume.assumeTrue(checkValidate(data, 3, 104, 111));
+ Assume.assumeTrue(checkValidate(data, 4, 120, 120));
+ Assume.assumeTrue(checkValidate(data, 5, 122, 123));
+
+ Assume.assumeTrue(checkValidate(data, 6, 151, 151));
+ Assume.assumeTrue(checkValidate(data, 7, 157, 159));
+ Assume.assumeTrue(checkValidate(data, 8, 192, 208));
+ Assume.assumeTrue(checkValidate(data, 9, 210, 210));
+ Assume.assumeTrue(checkValidate(data, 10, 216, 216));
+ Assume.assumeTrue(checkValidate(data, 11, 225, 225));
+ Assume.assumeTrue(checkValidate(data, 12, 228, 229));
+ }
+
+ private boolean checkValidate(List<Long[]> data, int index, int start, int end) {
+ Long[] tmp = data.get(index);
+ return tmp[0] == start && tmp[1] == end;
+ }
+}