You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2020/02/19 15:05:51 UTC
[lucene-solr] branch branch_8x updated: LUCENE-8707: Add
LatLonShape and XYShape distance query (#587)
This is an automated email from the ASF dual-hosted git repository.
ivera pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/branch_8x by this push:
new 50168ab LUCENE-8707: Add LatLonShape and XYShape distance query (#587)
50168ab is described below
commit 50168ab5bc85c382a6d558553caa1f752bf5afc1
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Wed Feb 19 16:03:30 2020 +0100
LUCENE-8707: Add LatLonShape and XYShape distance query (#587)
---
lucene/CHANGES.txt | 4 +-
.../org/apache/lucene/document/LatLonShape.java | 7 +
.../java/org/apache/lucene/document/XYShape.java | 6 +
.../src/java/org/apache/lucene/geo/Circle.java | 104 +++++
.../src/java/org/apache/lucene/geo/Circle2D.java | 463 +++++++++++++++++++++
.../src/java/org/apache/lucene/geo/XYCircle.java | 99 +++++
.../lucene/document/BaseLatLonShapeTestCase.java | 16 +
.../apache/lucene/document/BaseShapeTestCase.java | 106 ++++-
.../lucene/document/BaseXYShapeTestCase.java | 16 +
.../apache/lucene/document/TestLatLonShape.java | 52 ++-
.../org/apache/lucene/document/TestXYShape.java | 43 ++
.../test/org/apache/lucene/geo/ShapeTestUtil.java | 8 +
.../src/test/org/apache/lucene/geo/TestCircle.java | 70 ++++
.../test/org/apache/lucene/geo/TestCircle2D.java | 134 ++++++
.../test/org/apache/lucene/geo/TestXYCircle.java | 93 +++++
.../java/org/apache/lucene/geo/GeoTestUtil.java | 7 +
16 files changed, 1224 insertions(+), 4 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 8807a24..b5bcb21 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -27,7 +27,9 @@ API Changes
New Features
---------------------
-* LUCENE-8903: Add LatLonShape point query. (Ignacio Vera)
+* LUCENE-8903: Add LatLonShape and XYShape point query. (Ignacio Vera)
+
+* LUCENE-8707: Add LatLonShape and XYShape distance query. (Ignacio Vera)
Improvements
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/document/LatLonShape.java b/lucene/core/src/java/org/apache/lucene/document/LatLonShape.java
index 3c4c39c..a583e2c 100644
--- a/lucene/core/src/java/org/apache/lucene/document/LatLonShape.java
+++ b/lucene/core/src/java/org/apache/lucene/document/LatLonShape.java
@@ -21,6 +21,7 @@ import java.util.List;
import org.apache.lucene.document.ShapeField.QueryRelation; // javadoc
import org.apache.lucene.document.ShapeField.Triangle;
+import org.apache.lucene.geo.Circle;
import org.apache.lucene.geo.GeoUtils;
import org.apache.lucene.geo.LatLonGeometry;
import org.apache.lucene.geo.Line;
@@ -131,6 +132,11 @@ public class LatLonShape {
return newGeometryQuery(field, queryRelation, pointArray);
}
+ /** create a query to find all polygons that intersect a provided circle. */
+ public static Query newDistanceQuery(String field, QueryRelation queryRelation, Circle... circle) {
+ return newGeometryQuery(field, queryRelation, circle);
+ }
+
/** create a query to find all indexed geo shapes that intersect a provided geometry (or array of geometries).
**/
public static Query newGeometryQuery(String field, QueryRelation queryRelation, LatLonGeometry... latLonGeometries) {
@@ -143,4 +149,5 @@ public class LatLonShape {
}
return new LatLonShapeQuery(field, queryRelation, latLonGeometries);
}
+
}
diff --git a/lucene/core/src/java/org/apache/lucene/document/XYShape.java b/lucene/core/src/java/org/apache/lucene/document/XYShape.java
index 88f9a5d..7eb8403 100644
--- a/lucene/core/src/java/org/apache/lucene/document/XYShape.java
+++ b/lucene/core/src/java/org/apache/lucene/document/XYShape.java
@@ -22,6 +22,7 @@ import java.util.List;
import org.apache.lucene.document.ShapeField.QueryRelation; // javadoc
import org.apache.lucene.document.ShapeField.Triangle;
import org.apache.lucene.geo.Tessellator;
+import org.apache.lucene.geo.XYCircle;
import org.apache.lucene.geo.XYGeometry;
import org.apache.lucene.geo.XYPoint;
import org.apache.lucene.geo.XYRectangle;
@@ -117,6 +118,11 @@ public class XYShape {
return newGeometryQuery(field, queryRelation, pointArray);
}
+ /** create a query to find all cartesian shapes that intersect a provided circle (or arrays of circles) **/
+ public static Query newDistanceQuery(String field, QueryRelation queryRelation, XYCircle... circle) {
+ return newGeometryQuery(field, queryRelation, circle);
+ }
+
/** create a query to find all indexed geo shapes that intersect a provided geometry collection
* note: Components do not support dateline crossing
**/
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Circle.java b/lucene/core/src/java/org/apache/lucene/geo/Circle.java
new file mode 100644
index 0000000..4bb63c8
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/geo/Circle.java
@@ -0,0 +1,104 @@
+/*
+ * 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.lucene.geo;
+
+
+/**
+ * Represents a circle on the earth's surface.
+ * <p>
+ * NOTES:
+ * <ol>
+ * <li> Latitude/longitude values must be in decimal degrees.
+ * <li> Radius must be in meters.
+ * <li>For more advanced GeoSpatial indexing and query operations see the {@code spatial-extras} module
+ * </ol>
+ * @lucene.experimental
+ */
+public final class Circle extends LatLonGeometry {
+ /** Center latitude */
+ private final double lat;
+ /** Center longitude */
+ private final double lon;
+ /** radius in meters */
+ private final double radiusMeters;
+ /** Max radius allowed, half of the earth mean radius.*/
+ public static double MAX_RADIUS = GeoUtils.EARTH_MEAN_RADIUS_METERS / 2.0;
+
+
+ /**
+ * Creates a new circle from the supplied latitude/longitude center and a radius in meters..
+ */
+ public Circle(double lat, double lon, double radiusMeters) {
+ GeoUtils.checkLatitude(lat);
+ GeoUtils.checkLongitude(lon);
+ if (radiusMeters <= 0) {
+ throw new IllegalArgumentException("radius must be bigger than 0, got " + radiusMeters);
+ }
+ if (radiusMeters < MAX_RADIUS == false) {
+ throw new IllegalArgumentException("radius must be lower than " + MAX_RADIUS + ", got " + radiusMeters);
+ }
+ this.lat = lat;
+ this.lon = lon;
+ this.radiusMeters = radiusMeters;
+ }
+
+ /** Returns the center's latitude */
+ public double getLat() {
+ return lat;
+ }
+
+ /** Returns the center's longitude */
+ public double getLon() {
+ return lon;
+ }
+
+ /** Returns the radius in meters */
+ public double getRadius() {
+ return radiusMeters;
+ }
+
+ @Override
+ protected Component2D toComponent2D() {
+ return Circle2D.create(this);
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (!(o instanceof Circle)) return false;
+ Circle circle = (Circle) o;
+ return lat == circle.lat && lon == circle.lon && radiusMeters == circle.radiusMeters;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = Double.hashCode(lat);
+ result = 31 * result + Double.hashCode(lon);
+ result = 31 * result + Double.hashCode(radiusMeters);
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder sb = new StringBuilder();
+ sb.append("CIRCLE(");
+ sb.append("[" + lat + "," + lon + "]");
+ sb.append(" radius = " + radiusMeters + " meters");
+ sb.append(')');
+ return sb.toString();
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Circle2D.java b/lucene/core/src/java/org/apache/lucene/geo/Circle2D.java
new file mode 100644
index 0000000..18bc587
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/geo/Circle2D.java
@@ -0,0 +1,463 @@
+/*
+ * 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.lucene.geo;
+
+import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.util.SloppyMath;
+
+/**
+ * 2D circle implementation containing spatial logic.
+ */
+class Circle2D implements Component2D {
+
+ private final DistanceCalculator calculator;
+
+ private Circle2D(DistanceCalculator calculator) {
+ this.calculator = calculator;
+ }
+
+ @Override
+ public double getMinX() {
+ return calculator.getMinX();
+ }
+
+ @Override
+ public double getMaxX() {
+ return calculator.getMaxX();
+ }
+
+ @Override
+ public double getMinY() {
+ return calculator.getMinY();
+ }
+
+ @Override
+ public double getMaxY() {
+ return calculator.getMaxY();
+ }
+
+ @Override
+ public boolean contains(double x, double y) {
+ return calculator.contains(x, y);
+ }
+
+ @Override
+ public Relation relate(double minX, double maxX, double minY, double maxY) {
+ if (calculator.disjoint(minX, maxX, minY, maxY)) {
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+ if (calculator.within(minX, maxX, minY, maxY)) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+ return calculator.relate(minX, maxX, minY, maxY);
+ }
+
+ @Override
+ public Relation relateTriangle(double minX, double maxX, double minY, double maxY,
+ double ax, double ay, double bx, double by, double cx, double cy) {
+ if (calculator.disjoint(minX, maxX, minY, maxY)) {
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+ if (ax == bx && bx == cx && ay == by && by == cy) {
+ // indexed "triangle" is a point: shortcut by checking contains
+ return contains(ax, ay) ? Relation.CELL_INSIDE_QUERY : Relation.CELL_OUTSIDE_QUERY;
+ } else if (ax == cx && ay == cy) {
+ // indexed "triangle" is a line segment: shortcut by calling appropriate method
+ return relateIndexedLineSegment(ax, ay, bx, by);
+ } else if (ax == bx && ay == by) {
+ // indexed "triangle" is a line segment: shortcut by calling appropriate method
+ return relateIndexedLineSegment(bx, by, cx, cy);
+ } else if (bx == cx && by == cy) {
+ // indexed "triangle" is a line segment: shortcut by calling appropriate method
+ return relateIndexedLineSegment(cx, cy, ax, ay);
+ }
+ // indexed "triangle" is a triangle:
+ return relateIndexedTriangle(minX, maxX, minY, maxY, ax, ay, bx, by, cx, cy);
+ }
+
+ @Override
+ public WithinRelation withinTriangle(double minX, double maxX, double minY, double maxY,
+ double ax, double ay, boolean ab, double bx, double by, boolean bc, double cx, double cy, boolean ca) {
+ // short cut, lines and points cannot contain this type of shape
+ if ((ax == bx && ay == by) || (ax == cx && ay == cy) || (bx == cx && by == cy)) {
+ return WithinRelation.DISJOINT;
+ }
+
+ if (calculator.disjoint(minX, maxX, minY, maxY)) {
+ return WithinRelation.DISJOINT;
+ }
+
+ // if any of the points is inside the polygon, the polygon cannot be within this indexed
+ // shape because points belong to the original indexed shape.
+ if (contains(ax, ay) || contains(bx, by) || contains(cx, cy)) {
+ return WithinRelation.NOTWITHIN;
+ }
+
+ WithinRelation relation = WithinRelation.DISJOINT;
+ // if any of the edges intersects an the edge belongs to the shape then it cannot be within.
+ // if it only intersects edges that do not belong to the shape, then it is a candidate
+ // we skip edges at the dateline to support shapes crossing it
+ if (intersectsLine(ax, ay, bx, by)) {
+ if (ab == true) {
+ return WithinRelation.NOTWITHIN;
+ } else {
+ relation = WithinRelation.CANDIDATE;
+ }
+ }
+
+ if (intersectsLine(bx, by, cx, cy)) {
+ if (bc == true) {
+ return WithinRelation.NOTWITHIN;
+ } else {
+ relation = WithinRelation.CANDIDATE;
+ }
+ }
+ if (intersectsLine(cx, cy, ax, ay)) {
+ if (ca == true) {
+ return WithinRelation.NOTWITHIN;
+ } else {
+ relation = WithinRelation.CANDIDATE;
+ }
+ }
+
+ // if any of the edges crosses and edge that does not belong to the shape
+ // then it is a candidate for within
+ if (relation == WithinRelation.CANDIDATE) {
+ return WithinRelation.CANDIDATE;
+ }
+
+ // Check if shape is within the triangle
+ if (Component2D.pointInTriangle(minX, maxX, minY, maxY, calculator.geX(), calculator.getY(), ax, ay, bx, by, cx, cy) == true) {
+ return WithinRelation.CANDIDATE;
+ }
+ return relation;
+ }
+
+ /** relates an indexed line segment (a "flat triangle") with the polygon */
+ private Relation relateIndexedLineSegment(double a2x, double a2y, double b2x, double b2y) {
+ // check endpoints of the line segment
+ int numCorners = 0;
+ if (contains(a2x, a2y)) {
+ ++numCorners;
+ }
+ if (contains(b2x, b2y)) {
+ ++numCorners;
+ }
+
+ if (numCorners == 2) {
+ return Relation.CELL_INSIDE_QUERY;
+ } else if (numCorners == 0) {
+ if (intersectsLine(a2x, a2y, b2x, b2y)) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+ return Relation.CELL_CROSSES_QUERY;
+ }
+
+ /** relates an indexed triangle with the polygon */
+ private Relation relateIndexedTriangle(double minX, double maxX, double minY, double maxY,
+ double ax, double ay, double bx, double by, double cx, double cy) {
+ // check each corner: if < 3 && > 0 are present, its cheaper than crossesSlowly
+ int numCorners = numberOfTriangleCorners(ax, ay, bx, by, cx, cy);
+ if (numCorners == 3) {
+ return Relation.CELL_INSIDE_QUERY;
+ } else if (numCorners == 0) {
+ if (Component2D.pointInTriangle(minX, maxX, minY, maxY, calculator.geX(), calculator.getY(), ax, ay, bx, by, cx, cy) == true) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+ if (intersectsLine(ax, ay, bx, by) ||
+ intersectsLine(bx, by, cx, cy) ||
+ intersectsLine(cx, cy, ax, ay)) {
+ return Relation.CELL_CROSSES_QUERY;
+ }
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+ return Relation.CELL_CROSSES_QUERY;
+ }
+
+ private int numberOfTriangleCorners(double ax, double ay, double bx, double by, double cx, double cy) {
+ int containsCount = 0;
+ if (contains(ax, ay)) {
+ containsCount++;
+ }
+ if (contains(bx, by)) {
+ containsCount++;
+ }
+ if (containsCount == 1) {
+ // if one point is inside and the other outside, we know
+ // already that the triangle intersect.
+ return containsCount;
+ }
+ if (contains(cx, cy)) {
+ containsCount++;
+ }
+ return containsCount;
+ }
+
+ // This methods in a new helper class XYUtil?
+ private boolean intersectsLine(double aX, double aY, double bX, double bY) {
+ //Algorithm based on this thread : https://stackoverflow.com/questions/3120357/get-closest-point-to-a-line
+ final double[] vectorAP = new double[] {calculator.geX() - aX, calculator.getY() - aY};
+ final double[] vectorAB = new double[] {bX - aX, bY - aY};
+
+ final double magnitudeAB = vectorAB[0] * vectorAB[0] + vectorAB[1] * vectorAB[1];
+ final double dotProduct = vectorAP[0] * vectorAB[0] + vectorAP[1] * vectorAB[1];
+
+ final double distance = dotProduct / magnitudeAB;
+
+ if (distance < 0 || distance > dotProduct) {
+ return false;
+ }
+
+ final double pX = aX + vectorAB[0] * distance;
+ final double pY = aY + vectorAB[1] * distance;
+
+ final double minX = StrictMath.min(aX, bX);
+ final double minY = StrictMath.min(aY, bY);
+ final double maxX = StrictMath.max(aX, bX);
+ final double maxY = StrictMath.max(aY, bY);
+
+ if (pX >= minX && pX <= maxX && pY >= minY && pY <= maxY) {
+ return contains(pX, pY);
+ }
+ return false;
+ }
+
+ private interface DistanceCalculator {
+
+ Relation relate(double minX, double maxX, double minY, double maxY);
+
+ boolean contains(double x, double y);
+
+ boolean disjoint(double minX, double maxX, double minY, double maxY);
+
+ boolean within(double minX, double maxX, double minY, double maxY);
+
+ double getMinX();
+
+ double getMaxX();
+
+ double getMinY();
+
+ double getMaxY();
+
+ double geX();
+
+ double getY();
+ }
+
+ private static class CartesianDistance implements DistanceCalculator {
+
+ private final double centerX;
+ private final double centerY;
+ private final double radiusSquared;
+ private final double minX;
+ private final double maxX;
+ private final double minY;
+ private final double maxY;
+
+ public CartesianDistance(double centerX, double centerY, double radius) {
+ this.centerX = centerX;
+ this.centerY = centerY;
+ this.minX = Math.max(-Float.MAX_VALUE, centerX - radius);
+ this.maxX = Math.min(Float.MAX_VALUE, centerX + radius);
+ this.minY = Math.max(-Float.MAX_VALUE, centerY - radius);
+ this.maxY = Math.min(Float.MAX_VALUE, centerY + radius);
+ this.radiusSquared = radius * radius;
+ }
+
+ @Override
+ public Relation relate(double minX, double maxX, double minY, double maxY) {
+ if (Component2D.containsPoint(centerX, centerY, minX, maxX, minY, maxY)) {
+ if (contains(minX, minY) && contains(maxX, minY) && contains(maxX, maxY) && contains(minX, maxY)) {
+ // we are fully enclosed, collect everything within this subtree
+ return Relation.CELL_INSIDE_QUERY;
+ }
+ } else {
+ // circle not fully inside, compute closest distance
+ double sumOfSquaredDiffs = 0.0d;
+ if (centerX < minX) {
+ double diff = minX - centerX;
+ sumOfSquaredDiffs += diff * diff;
+ } else if (centerX > maxX) {
+ double diff = maxX - centerX;
+ sumOfSquaredDiffs += diff * diff;
+ }
+ if (centerY < minY) {
+ double diff = minY - centerY;
+ sumOfSquaredDiffs += diff * diff;
+ } else if (centerY > maxY) {
+ double diff = maxY - centerY;
+ sumOfSquaredDiffs += diff * diff;
+ }
+ if (sumOfSquaredDiffs > radiusSquared) {
+ // disjoint
+ return Relation.CELL_OUTSIDE_QUERY;
+ }
+ }
+ return Relation.CELL_CROSSES_QUERY;
+ }
+
+ @Override
+ public boolean contains(double x, double y) {
+ final double diffX = x - this.centerX;
+ final double diffY = y - this.centerY;
+ return diffX * diffX + diffY * diffY <= radiusSquared;
+ }
+
+ @Override
+ public boolean disjoint(double minX, double maxX, double minY, double maxY) {
+ return Component2D.disjoint(this.minX, this.maxX, this.minY, this.maxY, minX, maxX, minY, maxY);
+ }
+
+ @Override
+ public boolean within(double minX, double maxX, double minY, double maxY) {
+ return Component2D.within(this.minX, this.maxX, this.minY, this.maxY, minX, maxX, minY, maxY);
+ }
+
+ @Override
+ public double getMinX() {
+ return minX;
+ }
+
+ @Override
+ public double getMaxX() {
+ return maxX;
+ }
+
+ @Override
+ public double getMinY() {
+ return minY;
+ }
+
+ @Override
+ public double getMaxY() {
+ return maxY;
+ }
+
+ @Override
+ public double geX() {
+ return centerX;
+ }
+
+ @Override
+ public double getY() {
+ return centerY;
+ }
+ }
+
+ private static class HaversinDistance implements DistanceCalculator {
+
+ final double centerLat;
+ final double centerLon;
+ final double sortKey;
+ final double axisLat;
+ final Rectangle rectangle;
+ final boolean crossesDateline;
+
+ public HaversinDistance(double centerLon, double centerLat, double radius) {
+ this.centerLat = centerLat;
+ this.centerLon = centerLon;
+ this.sortKey = GeoUtils.distanceQuerySortKey(radius);
+ this.axisLat = Rectangle.axisLat(centerLat, radius);
+ this.rectangle = Rectangle.fromPointDistance(centerLat, centerLon, radius);
+ this.crossesDateline = rectangle.minLon > rectangle.maxLon;
+ }
+
+ @Override
+ public Relation relate(double minX, double maxX, double minY, double maxY) {
+ return GeoUtils.relate(minY, maxY, minX, maxX, centerLat, centerLon, sortKey, axisLat);
+ }
+
+ @Override
+ public boolean contains(double x, double y) {
+ return SloppyMath.haversinSortKey(y, x, this.centerLat, this.centerLon) <= sortKey;
+ }
+
+ @Override
+ public boolean disjoint(double minX, double maxX, double minY, double maxY) {
+ if (crossesDateline) {
+ return Component2D.disjoint(rectangle.minLon, GeoUtils.MAX_LON_INCL, rectangle.minLat, rectangle.maxLat, minX, maxX, minY, maxY)
+ && Component2D.disjoint(GeoUtils.MIN_LON_INCL, rectangle.maxLon, rectangle.minLat, rectangle.maxLat, minX, maxX, minY, maxY);
+ } else {
+ return Component2D.disjoint(rectangle.minLon, rectangle.maxLon, rectangle.minLat, rectangle.maxLat, minX, maxX, minY, maxY);
+ }
+ }
+
+ @Override
+ public boolean within(double minX, double maxX, double minY, double maxY) {
+ if (crossesDateline) {
+ return Component2D.within(rectangle.minLon, GeoUtils.MAX_LON_INCL, rectangle.minLat, rectangle.maxLat, minX, maxX, minY, maxY)
+ || Component2D.within(GeoUtils.MIN_LON_INCL, rectangle.maxLon, rectangle.minLat, rectangle.maxLat, minX, maxX, minY, maxY);
+ } else {
+ return Component2D.within(rectangle.minLon, rectangle.maxLon, rectangle.minLat, rectangle.maxLat, minX, maxX, minY, maxY);
+ }
+ }
+
+ @Override
+ public double getMinX() {
+ if (crossesDateline) {
+ // Component2D does not support boxes that crosses the dateline
+ return GeoUtils.MIN_LON_INCL;
+ }
+ return rectangle.minLon;
+ }
+
+ @Override
+ public double getMaxX() {
+ if (crossesDateline) {
+ // Component2D does not support boxes that crosses the dateline
+ return GeoUtils.MAX_LON_INCL;
+ }
+ return rectangle.maxLon;
+ }
+
+ @Override
+ public double getMinY() {
+ return rectangle.minLat;
+ }
+
+ @Override
+ public double getMaxY() {
+ return rectangle.maxLat;
+ }
+
+ @Override
+ public double geX() {
+ return centerLon;
+ }
+
+ @Override
+ public double getY() {
+ return centerLat;
+ }
+ }
+
+ /** Builds a XYCircle2D from XYCircle. Distance calculations are performed using cartesian distance.*/
+ static Component2D create(XYCircle circle) {
+ DistanceCalculator calculator = new CartesianDistance(circle.getX(), circle.getY(), circle.getRadius());
+ return new Circle2D(calculator);
+ }
+
+ /** Builds a Circle2D from Circle. Distance calculations are performed using haversin distance. */
+ static Component2D create(Circle circle) {
+ DistanceCalculator calculator = new HaversinDistance(circle.getLon(), circle.getLat(), circle.getRadius());
+ return new Circle2D(calculator);
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/geo/XYCircle.java b/lucene/core/src/java/org/apache/lucene/geo/XYCircle.java
new file mode 100644
index 0000000..b312673
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/geo/XYCircle.java
@@ -0,0 +1,99 @@
+/*
+ * 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.lucene.geo;
+
+import static org.apache.lucene.geo.XYEncodingUtils.checkVal;
+
+/**
+ * Represents a circle on the XY plane.
+ * <p>
+ * NOTES:
+ * <ol>
+ * <li> X/Y precision is float.
+ * <li> Radius precision is float.
+ * </ol>
+ * @lucene.experimental
+ */
+public final class XYCircle extends XYGeometry {
+ /** Center x */
+ private final float x;
+ /** Center y */
+ private final float y;
+ /** radius */
+ private final float radius;
+
+ /**
+ * Creates a new circle from the supplied x/y center and radius.
+ */
+ public XYCircle(float x, float y, float radius) {
+ if (radius <= 0) {
+ throw new IllegalArgumentException("radius must be bigger than 0, got " + radius);
+ }
+ if (Float.isFinite(radius) == false) {
+ throw new IllegalArgumentException("radius must be finite, got " + radius);
+ }
+ this.x = checkVal(x);
+ this.y = checkVal(y);
+ this.radius = radius;
+ }
+
+ /** Returns the center's x */
+ public float getX() {
+ return x;
+ }
+
+ /** Returns the center's y */
+ public float getY() {
+ return y;
+ }
+
+ /** Returns the radius */
+ public float getRadius() {
+ return radius;
+ }
+
+ @Override
+ protected Component2D toComponent2D() {
+ return Circle2D.create(this);
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (!(o instanceof XYCircle)) return false;
+ XYCircle circle = (XYCircle) o;
+ return x == circle.x && y == circle.y && radius == circle.radius;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = Float.hashCode(x);
+ result = 31 * result + Float.hashCode(y);
+ result = 31 * result + Float.hashCode(radius);
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder sb = new StringBuilder();
+ sb.append("CIRCLE(");
+ sb.append("[" + x + "," + y + "]");
+ sb.append(" radius = " + radius);
+ sb.append(')');
+ return sb.toString();
+ }
+}
diff --git a/lucene/core/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java b/lucene/core/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
index c49496a..f15062a 100644
--- a/lucene/core/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
+++ b/lucene/core/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
@@ -29,6 +29,7 @@ import org.apache.lucene.geo.Rectangle;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.QueryUtils;
import org.apache.lucene.util.TestUtil;
+import org.apache.lucene.geo.Circle;
import static org.apache.lucene.geo.GeoEncodingUtils.decodeLatitude;
import static org.apache.lucene.geo.GeoEncodingUtils.decodeLongitude;
@@ -92,6 +93,21 @@ public abstract class BaseLatLonShapeTestCase extends BaseShapeTestCase {
}
@Override
+ protected Query newDistanceQuery(String field, QueryRelation queryRelation, Object circle) {
+ return LatLonShape.newDistanceQuery(field, queryRelation, (Circle) circle);
+ }
+
+ @Override
+ protected Component2D toCircle2D(Object circle) {
+ return LatLonGeometry.create((Circle) circle);
+ }
+
+ @Override
+ protected Circle nextCircle() {
+ return new Circle(nextLatitude(), nextLongitude(), random().nextDouble() * Circle.MAX_RADIUS);
+ }
+
+ @Override
public Rectangle randomQueryBox() {
return GeoTestUtil.nextBox();
}
diff --git a/lucene/core/src/test/org/apache/lucene/document/BaseShapeTestCase.java b/lucene/core/src/test/org/apache/lucene/document/BaseShapeTestCase.java
index 21ed121..16f7a21 100644
--- a/lucene/core/src/test/org/apache/lucene/document/BaseShapeTestCase.java
+++ b/lucene/core/src/test/org/apache/lucene/document/BaseShapeTestCase.java
@@ -164,6 +164,8 @@ public abstract class BaseShapeTestCase extends LuceneTestCase {
protected abstract Object[] nextPoints();
+ protected abstract Object nextCircle();
+
protected abstract double rectMinX(Object rect);
protected abstract double rectMaxX(Object rect);
protected abstract double rectMinY(Object rect);
@@ -183,6 +185,10 @@ public abstract class BaseShapeTestCase extends LuceneTestCase {
return nextPolygon();
}
+ protected Object randomQueryCircle() {
+ return nextCircle();
+ }
+
/** factory method to create a new bounding box query */
protected abstract Query newRectQuery(String field, QueryRelation queryRelation, double minX, double maxX, double minY, double maxY);
@@ -192,15 +198,20 @@ public abstract class BaseShapeTestCase extends LuceneTestCase {
/** factory method to create a new polygon query */
protected abstract Query newPolygonQuery(String field, QueryRelation queryRelation, Object... polygons);
- /** factory method to create a new polygon query */
+ /** factory method to create a new point query */
protected abstract Query newPointsQuery(String field, QueryRelation queryRelation, Object... points);
+ /** factory method to create a new distance query */
+ protected abstract Query newDistanceQuery(String field, QueryRelation queryRelation, Object circle);
+
protected abstract Component2D toLine2D(Object... line);
protected abstract Component2D toPolygon2D(Object... polygon);
protected abstract Component2D toPoint2D(Object... points);
+ protected abstract Component2D toCircle2D(Object circle);
+
private void verify(Object... shapes) throws Exception {
IndexWriterConfig iwc = newIndexWriterConfig();
iwc.setMergeScheduler(new SerialMergeScheduler());
@@ -261,6 +272,8 @@ public abstract class BaseShapeTestCase extends LuceneTestCase {
verifyRandomPolygonQueries(reader, shapes);
// test random point queries
verifyRandomPointQueries(reader, shapes);
+ // test random distance queries
+ verifyRandomDistanceQueries(reader, shapes);
}
/** test random generated bounding boxes */
@@ -655,6 +668,97 @@ public abstract class BaseShapeTestCase extends LuceneTestCase {
}
}
+ /** test random generated circles */
+ protected void verifyRandomDistanceQueries(IndexReader reader, Object... shapes) throws Exception {
+ IndexSearcher s = newSearcher(reader);
+
+ final int iters = scaledIterationCount(shapes.length);
+
+ Bits liveDocs = MultiBits.getLiveDocs(s.getIndexReader());
+ int maxDoc = s.getIndexReader().maxDoc();
+
+ for (int iter = 0; iter < iters; ++iter) {
+ if (VERBOSE) {
+ System.out.println("\nTEST: iter=" + (iter + 1) + " of " + iters + " s=" + s);
+ }
+
+ // Polygon
+ Object queryCircle = randomQueryCircle();
+ Component2D queryCircle2D = toCircle2D(queryCircle);
+ QueryRelation queryRelation = RandomPicks.randomFrom(random(), QueryRelation.values());
+ Query query = newDistanceQuery(FIELD_NAME, queryRelation, queryCircle);
+
+ if (VERBOSE) {
+ System.out.println(" query=" + query + ", relation=" + queryRelation);
+ }
+
+ final FixedBitSet hits = new FixedBitSet(maxDoc);
+ s.search(query, new SimpleCollector() {
+
+ private int docBase;
+
+ @Override
+ public ScoreMode scoreMode() {
+ return ScoreMode.COMPLETE_NO_SCORES;
+ }
+
+ @Override
+ protected void doSetNextReader(LeafReaderContext context) throws IOException {
+ docBase = context.docBase;
+ }
+
+ @Override
+ public void collect(int doc) throws IOException {
+ hits.set(docBase+doc);
+ }
+ });
+
+ boolean fail = false;
+ NumericDocValues docIDToID = MultiDocValues.getNumericValues(reader, "id");
+ for (int docID = 0; docID < maxDoc; ++docID) {
+ assertEquals(docID, docIDToID.nextDoc());
+ int id = (int) docIDToID.longValue();
+ boolean expected;
+ if (liveDocs != null && liveDocs.get(docID) == false) {
+ // document is deleted
+ expected = false;
+ } else if (shapes[id] == null) {
+ expected = false;
+ } else {
+ expected = VALIDATOR.setRelation(queryRelation).testComponentQuery(queryCircle2D, shapes[id]);
+ }
+
+ if (hits.get(docID) != expected) {
+ StringBuilder b = new StringBuilder();
+
+ if (expected) {
+ b.append("FAIL: id=" + id + " should match but did not\n");
+ } else {
+ b.append("FAIL: id=" + id + " should not match but did\n");
+ }
+ b.append(" relation=" + queryRelation + "\n");
+ b.append(" query=" + query + " docID=" + docID + "\n");
+ if (shapes[id] instanceof Object[]) {
+ b.append(" shape=" + Arrays.toString((Object[]) shapes[id]) + "\n");
+ } else {
+ b.append(" shape=" + shapes[id] + "\n");
+ }
+ b.append(" deleted?=" + (liveDocs != null && liveDocs.get(docID) == false));
+ b.append(" distanceQuery=" + queryCircle.toString());
+ if (true) {
+ fail("wrong hit (first of possibly more):\n\n" + b);
+ } else {
+ System.out.println(b.toString());
+ fail = true;
+ }
+ }
+ }
+ if (fail) {
+ fail("some hits were wrong");
+ }
+ }
+ }
+
protected abstract Validator getValidator();
diff --git a/lucene/core/src/test/org/apache/lucene/document/BaseXYShapeTestCase.java b/lucene/core/src/test/org/apache/lucene/document/BaseXYShapeTestCase.java
index ef34cfe..b13974d 100644
--- a/lucene/core/src/test/org/apache/lucene/document/BaseXYShapeTestCase.java
+++ b/lucene/core/src/test/org/apache/lucene/document/BaseXYShapeTestCase.java
@@ -23,6 +23,7 @@ import com.carrotsearch.randomizedtesting.generators.RandomPicks;
import org.apache.lucene.document.ShapeField.QueryRelation;
import org.apache.lucene.geo.Component2D;
import org.apache.lucene.geo.ShapeTestUtil;
+import org.apache.lucene.geo.XYCircle;
import org.apache.lucene.geo.XYGeometry;
import org.apache.lucene.geo.XYLine;
import org.apache.lucene.geo.XYPoint;
@@ -66,6 +67,11 @@ public abstract class BaseXYShapeTestCase extends BaseShapeTestCase {
}
@Override
+ protected Query newDistanceQuery(String field, QueryRelation queryRelation, Object circle) {
+ return XYShape.newDistanceQuery(field, queryRelation, (XYCircle) circle);
+ }
+
+ @Override
protected Component2D toPoint2D(Object... points) {
float[][] p = Arrays.stream(points).toArray(float[][]::new);
XYPoint[] pointArray = new XYPoint[points.length];
@@ -86,6 +92,11 @@ public abstract class BaseXYShapeTestCase extends BaseShapeTestCase {
}
@Override
+ protected Component2D toCircle2D(Object circle) {
+ return XYGeometry.create((XYCircle) circle);
+ }
+
+ @Override
public XYRectangle randomQueryBox() {
return ShapeTestUtil.nextBox(random());
}
@@ -151,6 +162,11 @@ public abstract class BaseXYShapeTestCase extends BaseShapeTestCase {
}
@Override
+ protected Object nextCircle() {
+ return ShapeTestUtil.nextCircle();
+ }
+
+ @Override
protected Encoder getEncoder() {
return new Encoder() {
@Override
diff --git a/lucene/core/src/test/org/apache/lucene/document/TestLatLonShape.java b/lucene/core/src/test/org/apache/lucene/document/TestLatLonShape.java
index 28c4382..acc8982 100644
--- a/lucene/core/src/test/org/apache/lucene/document/TestLatLonShape.java
+++ b/lucene/core/src/test/org/apache/lucene/document/TestLatLonShape.java
@@ -18,6 +18,7 @@ package org.apache.lucene.document;
import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
import org.apache.lucene.document.ShapeField.QueryRelation;
+import org.apache.lucene.geo.Circle;
import org.apache.lucene.geo.Component2D;
import org.apache.lucene.geo.GeoEncodingUtils;
import org.apache.lucene.geo.GeoTestUtil;
@@ -409,8 +410,8 @@ public class TestLatLonShape extends LuceneTestCase {
byte[] encoded = new byte[7 * ShapeField.BYTES];
ShapeField.encodeTriangle(encoded, encodeLatitude(t.getY(0)), encodeLongitude(t.getX(0)), t.isEdgefromPolygon(0),
- encodeLatitude(t.getY(1)), encodeLongitude(t.getX(1)), t.isEdgefromPolygon(1),
- encodeLatitude(t.getY(2)), encodeLongitude(t.getX(2)), t.isEdgefromPolygon(2));
+ encodeLatitude(t.getY(1)), encodeLongitude(t.getX(1)), t.isEdgefromPolygon(1),
+ encodeLatitude(t.getY(2)), encodeLongitude(t.getX(2)), t.isEdgefromPolygon(2));
ShapeField.DecodedTriangle decoded = new ShapeField.DecodedTriangle();
ShapeField.decodeTriangle(encoded, decoded);
@@ -740,4 +741,51 @@ public class TestLatLonShape extends LuceneTestCase {
IOUtils.close(w, reader, dir);
}
+
+
+ public void testPointIndexAndDistanceQuery() throws Exception {
+ Directory dir = newDirectory();
+ RandomIndexWriter writer = new RandomIndexWriter(random(), dir);
+ Document document = new Document();
+ BaseLatLonShapeTestCase.Point p = (BaseLatLonShapeTestCase.Point) BaseLatLonShapeTestCase.ShapeType.POINT.nextShape();
+ Field[] fields = LatLonShape.createIndexableFields(FIELDNAME, p.lat,p.lon);
+ for (Field f : fields) {
+ document.add(f);
+ }
+ writer.addDocument(document);
+
+ //// search
+ IndexReader r = writer.getReader();
+ writer.close();
+ IndexSearcher s = newSearcher(r);
+
+ double lat = GeoTestUtil.nextLatitude();
+ double lon = GeoTestUtil.nextLongitude();
+ double radiusMeters = random().nextDouble() * Circle.MAX_RADIUS;
+ while (radiusMeters == 0 || radiusMeters == Circle.MAX_RADIUS) {
+ radiusMeters = random().nextDouble() * Circle.MAX_RADIUS;
+ }
+ Circle circle = new Circle(lat, lon, radiusMeters);
+ Component2D circle2D = LatLonGeometry.create(circle);
+ int expected;
+ int expectedDisjoint;
+ if (circle2D.contains(p.lon, p.lat)) {
+ expected = 1;
+ expectedDisjoint = 0;
+ } else {
+ expected = 0;
+ expectedDisjoint = 1;
+ }
+
+ Query q = LatLonShape.newDistanceQuery(FIELDNAME, QueryRelation.INTERSECTS, circle);
+ assertEquals(expected, s.count(q));
+
+ q = LatLonShape.newDistanceQuery(FIELDNAME, QueryRelation.WITHIN, circle);
+ assertEquals(expected, s.count(q));
+
+ q = LatLonShape.newDistanceQuery(FIELDNAME, QueryRelation.DISJOINT, circle);
+ assertEquals(expectedDisjoint, s.count(q));
+
+ IOUtils.close(r, dir);
+ }
}
diff --git a/lucene/core/src/test/org/apache/lucene/document/TestXYShape.java b/lucene/core/src/test/org/apache/lucene/document/TestXYShape.java
index fad04cb..5cfdf07 100644
--- a/lucene/core/src/test/org/apache/lucene/document/TestXYShape.java
+++ b/lucene/core/src/test/org/apache/lucene/document/TestXYShape.java
@@ -19,8 +19,11 @@ package org.apache.lucene.document;
import java.util.Random;
import org.apache.lucene.document.ShapeField.QueryRelation;
+import org.apache.lucene.geo.Component2D;
import org.apache.lucene.geo.ShapeTestUtil;
import org.apache.lucene.geo.Tessellator;
+import org.apache.lucene.geo.XYCircle;
+import org.apache.lucene.geo.XYGeometry;
import org.apache.lucene.geo.XYLine;
import org.apache.lucene.geo.XYPolygon;
import org.apache.lucene.geo.XYRectangle;
@@ -159,6 +162,46 @@ public class TestXYShape extends LuceneTestCase {
IOUtils.close(reader, dir);
}
+ public void testPointIndexAndDistanceQuery() throws Exception {
+ Directory dir = newDirectory();
+ RandomIndexWriter writer = new RandomIndexWriter(random(), dir);
+ Document document = new Document();
+ float pX = ShapeTestUtil.nextFloat(random());
+ float py = ShapeTestUtil.nextFloat(random());
+ Field[] fields = XYShape.createIndexableFields(FIELDNAME, pX, py);
+ for (Field f : fields) {
+ document.add(f);
+ }
+ writer.addDocument(document);
+
+ //// search
+ IndexReader r = writer.getReader();
+ writer.close();
+ IndexSearcher s = newSearcher(r);
+ XYCircle circle = ShapeTestUtil.nextCircle();
+ Component2D circle2D = XYGeometry.create(circle);
+ int expected;
+ int expectedDisjoint;
+ if (circle2D.contains(pX, py)) {
+ expected = 1;
+ expectedDisjoint = 0;
+ } else {
+ expected = 0;
+ expectedDisjoint = 1;
+ }
+
+ Query q = XYShape.newDistanceQuery(FIELDNAME, QueryRelation.INTERSECTS, circle);
+ assertEquals(expected, s.count(q));
+
+ q = XYShape.newDistanceQuery(FIELDNAME, QueryRelation.WITHIN, circle);
+ assertEquals(expected, s.count(q));
+
+ q = XYShape.newDistanceQuery(FIELDNAME, QueryRelation.DISJOINT, circle);
+ assertEquals(expectedDisjoint, s.count(q));
+
+ IOUtils.close(r, dir);
+ }
+
private static boolean areBoxDisjoint(XYRectangle r1, XYRectangle r2) {
return ( r1.minX <= r2.minX && r1.minY <= r2.minY && r1.maxX >= r2.maxX && r1.maxY >= r2.maxY);
}
diff --git a/lucene/core/src/test/org/apache/lucene/geo/ShapeTestUtil.java b/lucene/core/src/test/org/apache/lucene/geo/ShapeTestUtil.java
index 13e0235..51b7a70 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/ShapeTestUtil.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/ShapeTestUtil.java
@@ -69,6 +69,14 @@ public class ShapeTestUtil {
return new XYLine(x, y);
}
+ public static XYCircle nextCircle() {
+ Random random = random();
+ float x = nextFloat(random);
+ float y = nextFloat(random);
+ float radius = random().nextFloat() * Float.MAX_VALUE / 2;
+ return new XYCircle(x, y, radius);
+ }
+
private static XYPolygon trianglePolygon(XYRectangle box) {
final float[] polyX = new float[4];
final float[] polyY = new float[4];
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestCircle.java b/lucene/core/src/test/org/apache/lucene/geo/TestCircle.java
new file mode 100644
index 0000000..8005d72
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestCircle.java
@@ -0,0 +1,70 @@
+/*
+ * 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.lucene.geo;
+
+import org.apache.lucene.util.LuceneTestCase;
+
+public class TestCircle extends LuceneTestCase {
+
+ /** latitude should be on range */
+ public void testInvalidLat() {
+ IllegalArgumentException expected = expectThrows(IllegalArgumentException.class, () -> {
+ new Circle(134.14, 45.23, 1000);
+ });
+ assertTrue(expected.getMessage().contains("invalid latitude 134.14; must be between -90.0 and 90.0"));
+ }
+
+ /** longitude should be on range */
+ public void testInvalidLon() {
+ IllegalArgumentException expected = expectThrows(IllegalArgumentException.class, () -> {
+ new Circle(43.5, 180.5, 1000);
+ });
+ assertTrue(expected.getMessage().contains("invalid longitude 180.5; must be between -180.0 and 180.0"));
+ }
+
+ /** radius must be positive */
+ public void testNegativeRadius() {
+ IllegalArgumentException expected = expectThrows(IllegalArgumentException.class, () -> {
+ new Circle(43.5, 45.23, -1000);
+ });
+ assertTrue(expected.getMessage().contains("radius must be bigger than 0, got -1000.0"));
+ }
+
+ /** radius must be lower than 3185504.3857 */
+ public void testInfiniteRadius() {
+ IllegalArgumentException expected = expectThrows(IllegalArgumentException.class, () -> {
+ new Circle(43.5, 45.23, Double.POSITIVE_INFINITY);
+ });
+ assertTrue(expected.getMessage().contains("radius must be lower than 3185504.3857, got Infinity"));
+ }
+
+ /** equals and hashcode */
+ public void testEqualsAndHashCode() {
+ Circle circle = GeoTestUtil.nextCircle();
+ Circle copy = new Circle(circle.getLat(), circle.getLon(), circle.getRadius());
+ assertEquals(circle, copy);
+ assertEquals(circle.hashCode(), copy.hashCode());
+ Circle otherCircle = GeoTestUtil.nextCircle();
+ if (circle.getLon() != otherCircle.getLon() || circle.getLat() != otherCircle.getLat() || circle.getRadius() != otherCircle.getRadius()) {
+ assertNotEquals(circle, otherCircle);
+ assertNotEquals(circle.hashCode(), otherCircle.hashCode());
+ } else {
+ assertEquals(circle, otherCircle);
+ assertEquals(circle.hashCode(), otherCircle.hashCode());
+ }
+ }
+}
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestCircle2D.java b/lucene/core/src/test/org/apache/lucene/geo/TestCircle2D.java
new file mode 100644
index 0000000..2ad5c21
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestCircle2D.java
@@ -0,0 +1,134 @@
+/*
+ * 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.lucene.geo;
+
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.util.LuceneTestCase;
+
+public class TestCircle2D extends LuceneTestCase {
+
+ public void testTriangleDisjoint() {
+ Component2D circle2D;
+ if (random().nextBoolean()) {
+ Circle circle = new Circle(0, 0, 100);
+ circle2D = LatLonGeometry.create(circle);
+ } else {
+ XYCircle xyCircle = new XYCircle(0, 0, 1);
+ circle2D = XYGeometry.create(xyCircle);
+ }
+ double ax = 4;
+ double ay = 4;
+ double bx = 5;
+ double by = 5;
+ double cx = 5;
+ double cy = 4;
+ assertEquals(PointValues.Relation.CELL_OUTSIDE_QUERY, circle2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.DISJOINT, circle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
+ }
+
+ public void testTriangleIntersects() {
+ Component2D circle2D;
+ if (random().nextBoolean()) {
+ Circle circle = new Circle(0, 0, 1000000);
+ circle2D = LatLonGeometry.create(circle);
+ } else {
+ XYCircle xyCircle = new XYCircle(0, 0, 10);
+ circle2D = XYGeometry.create(xyCircle);
+ }
+ double ax = -20;
+ double ay = 1;
+ double bx = 20;
+ double by = 1;
+ double cx = 0;
+ double cy = 90;
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, circle2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.NOTWITHIN, circle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
+ }
+
+ public void testTriangleContains() {
+ Component2D circle2D;
+ if (random().nextBoolean()) {
+ Circle circle = new Circle(0, 0, 1000000);
+ circle2D = LatLonGeometry.create(circle);
+ } else {
+ XYCircle xyCircle = new XYCircle(0, 0, 1);
+ circle2D = XYGeometry.create(xyCircle);
+ }
+ double ax = 0.25;
+ double ay = 0.25;
+ double bx = 0.5;
+ double by = 0.5;
+ double cx = 0.5;
+ double cy = 0.25;
+ assertEquals(PointValues.Relation.CELL_INSIDE_QUERY, circle2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.NOTWITHIN, circle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
+ }
+
+ public void testTriangleWithin() {
+ Component2D circle2D;
+ if (random().nextBoolean()) {
+ Circle circle = new Circle(0, 0, 1000);
+ circle2D = LatLonGeometry.create(circle);
+ } else {
+ XYCircle xyCircle = new XYCircle(0, 0, 1);
+ circle2D = XYGeometry.create(xyCircle);
+ }
+
+ double ax = -20;
+ double ay = -20;
+ double bx = 20;
+ double by = -20;
+ double cx = 0;
+ double cy = 20;
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, circle2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.CANDIDATE, circle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
+ }
+
+ public void testRandomTriangles() {
+ Component2D circle2D;
+ if (random().nextBoolean()) {
+ Circle circle = GeoTestUtil.nextCircle();
+ circle2D = LatLonGeometry.create(circle);
+ } else {
+ XYCircle circle = ShapeTestUtil.nextCircle();
+ circle2D = XYGeometry.create(circle);
+ }
+ for (int i =0; i < 100; i++) {
+ double ax = GeoTestUtil.nextLongitude();
+ double ay = GeoTestUtil.nextLatitude();
+ double bx = GeoTestUtil.nextLongitude();
+ double by = GeoTestUtil.nextLatitude();
+ double cx = GeoTestUtil.nextLongitude();
+ double cy = GeoTestUtil.nextLatitude();
+
+ double tMinX = StrictMath.min(StrictMath.min(ax, bx), cx);
+ double tMaxX = StrictMath.max(StrictMath.max(ax, bx), cx);
+ double tMinY = StrictMath.min(StrictMath.min(ay, by), cy);
+ double tMaxY = StrictMath.max(StrictMath.max(ay, by), cy);
+
+ PointValues.Relation r = circle2D.relate(tMinX, tMaxX, tMinY, tMaxY);
+ if (r == PointValues.Relation.CELL_OUTSIDE_QUERY) {
+ assertEquals(PointValues.Relation.CELL_OUTSIDE_QUERY, circle2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.DISJOINT, circle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
+ } else if (r == PointValues.Relation.CELL_INSIDE_QUERY) {
+ assertEquals(PointValues.Relation.CELL_CROSSES_QUERY, circle2D.relateTriangle(ax, ay, bx, by , cx, cy));
+ assertEquals(Component2D.WithinRelation.NOTWITHIN, circle2D.withinTriangle(ax, ay, true, bx, by, true, cx, cy, true));
+ }
+ }
+ }
+}
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestXYCircle.java b/lucene/core/src/test/org/apache/lucene/geo/TestXYCircle.java
new file mode 100644
index 0000000..a6400bb
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestXYCircle.java
@@ -0,0 +1,93 @@
+/*
+ * 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.lucene.geo;
+
+import org.apache.lucene.util.LuceneTestCase;
+
+public class TestXYCircle extends LuceneTestCase {
+
+ /** point values cannot be NaN */
+ public void testNaN() {
+ IllegalArgumentException expected = expectThrows(IllegalArgumentException.class, () -> {
+ new XYCircle(Float.NaN, 45.23f, 35.5f);
+ });
+ assertTrue(expected.getMessage().contains("invalid value NaN"));
+
+ expected = expectThrows(IllegalArgumentException.class, () -> {
+ new XYCircle(43.5f, Float.NaN, 35.5f);
+ });
+ assertTrue(expected.getMessage(), expected.getMessage().contains("invalid value NaN"));
+ }
+
+ /** point values mist be finite */
+ public void testPositiveInf() {
+ IllegalArgumentException expected = expectThrows(IllegalArgumentException.class, () -> {
+ new XYCircle(Float.POSITIVE_INFINITY, 45.23f, 35.5f);
+ });
+ assertTrue(expected.getMessage().contains("invalid value Inf"));
+
+ expected = expectThrows(IllegalArgumentException.class, () -> {
+ new XYCircle(43.5f, Float.POSITIVE_INFINITY, 35.5f);
+ });
+ assertTrue(expected.getMessage(), expected.getMessage().contains("invalid value Inf"));
+ }
+
+ /** point values mist be finite */
+ public void testNegativeInf() {
+ IllegalArgumentException expected = expectThrows(IllegalArgumentException.class, () -> {
+ new XYCircle(Float.NEGATIVE_INFINITY, 45.23f, 35.5f);
+ });
+ assertTrue(expected.getMessage().contains("invalid value -Inf"));
+
+ expected = expectThrows(IllegalArgumentException.class, () -> {
+ new XYCircle(43.5f, Float.NEGATIVE_INFINITY, 35.5f);
+ });
+ assertTrue(expected.getMessage(), expected.getMessage().contains("invalid value -Inf"));
+ }
+
+ /** radius must be positive */
+ public void testNegativeRadius() {
+ IllegalArgumentException expected = expectThrows(IllegalArgumentException.class, () -> {
+ new XYCircle(43.5f, 45.23f, -1000f);
+ });
+ assertTrue(expected.getMessage(), expected.getMessage().contains("radius must be bigger than 0, got -1000.0"));
+ }
+
+ /** radius must be lower than 3185504.3857 */
+ public void testInfiniteRadius() {
+ IllegalArgumentException expected = expectThrows(IllegalArgumentException.class, () -> {
+ new XYCircle(43.5f, 45.23f, Float.POSITIVE_INFINITY);
+ });
+ assertTrue(expected.getMessage(), expected.getMessage().contains("radius must be finite, got Infinity"));
+ }
+
+ /** equals and hashcode */
+ public void testEqualsAndHashCode() {
+ XYCircle circle = ShapeTestUtil.nextCircle();
+ XYCircle copy = new XYCircle(circle.getX(), circle.getY(), circle.getRadius());
+ assertEquals(circle, copy);
+ assertEquals(circle.hashCode(), copy.hashCode());
+ XYCircle otherCircle = ShapeTestUtil.nextCircle();
+ if (circle.getX() != otherCircle.getX() || circle.getY() != otherCircle.getY() || circle.getRadius() != otherCircle.getRadius()) {
+ assertNotEquals(circle, otherCircle);
+ assertNotEquals(circle.hashCode(), otherCircle.hashCode());
+ } else {
+ assertEquals(circle, otherCircle);
+ assertEquals(circle.hashCode(), otherCircle.hashCode());
+ }
+ }
+}
\ No newline at end of file
diff --git a/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java b/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
index aec0978..4b73f8d 100644
--- a/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
+++ b/lucene/test-framework/src/java/org/apache/lucene/geo/GeoTestUtil.java
@@ -384,6 +384,13 @@ public class GeoTestUtil {
return new Polygon(result[0], result[1]);
}
+ public static Circle nextCircle() {
+ double lat = nextLatitude();
+ double lon = nextLongitude();
+ double radiusMeters = random().nextDouble() * Circle.MAX_RADIUS;
+ return new Circle(lat, lon, radiusMeters);
+ }
+
/** returns next pseudorandom polygon */
public static Polygon nextPolygon() {
if (random().nextBoolean()) {