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/03/02 05:58:42 UTC
[lucene-solr] branch branch_8x updated: LUCENE-9243: Add fudge
factor when creating a bounding box of a xycircle (#1278)
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 d978740 LUCENE-9243: Add fudge factor when creating a bounding box of a xycircle (#1278)
d978740 is described below
commit d9787406f895d166e0d13eb5ce8a98865f1f3e39
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Mon Mar 2 06:56:29 2020 +0100
LUCENE-9243: Add fudge factor when creating a bounding box of a xycircle (#1278)
---
lucene/CHANGES.txt | 2 +
.../lucene/document/XYPointDistanceComparator.java | 12 +++--
.../src/java/org/apache/lucene/geo/Circle2D.java | 27 +++++------
.../java/org/apache/lucene/geo/XYRectangle.java | 20 ++++++++
.../org/apache/lucene/geo/TestXYRectangle.java | 53 ++++++++++++++++++++++
5 files changed, 93 insertions(+), 21 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index c6bb656..c9b3ee4 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -121,6 +121,8 @@ Bug Fixes
* LUCENE-9250: Add support for Circle2d#intersectsLine around the dateline. (Ignacio Vera)
+* LUCENE-9243: Add fudge factor when creating a bounding box of a XYCircle. (Ignacio Vera)
+
Other
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/document/XYPointDistanceComparator.java b/lucene/core/src/java/org/apache/lucene/document/XYPointDistanceComparator.java
index 2555411..0b20764 100644
--- a/lucene/core/src/java/org/apache/lucene/document/XYPointDistanceComparator.java
+++ b/lucene/core/src/java/org/apache/lucene/document/XYPointDistanceComparator.java
@@ -19,6 +19,7 @@ package org.apache.lucene.document;
import java.io.IOException;
import org.apache.lucene.geo.XYEncodingUtils;
+import org.apache.lucene.geo.XYRectangle;
import org.apache.lucene.index.DocValues;
import org.apache.lucene.index.FieldInfo;
import org.apache.lucene.index.LeafReader;
@@ -84,14 +85,15 @@ class XYPointDistanceComparator extends FieldComparator<Double> implements LeafF
// make bounding box(es) to exclude non-competitive hits, but start
// sampling if we get called way too much: don't make gobs of bounding
// boxes if comparator hits a worst case order (e.g. backwards distance order)
- if (setBottomCounter < 1024 || (setBottomCounter & 0x3F) == 0x3F) {
+ if (bottom < Float.MAX_VALUE && (setBottomCounter < 1024 || (setBottomCounter & 0x3F) == 0x3F)) {
+ XYRectangle rectangle = XYRectangle.fromPointDistance((float) x, (float) y, (float) bottom);
// pre-encode our box to our integer encoding, so we don't have to decode
// to double values for uncompetitive hits. This has some cost!
- this.minX = XYEncodingUtils.encode((float) Math.max(-Float.MAX_VALUE, x - bottom));
- this.maxX = XYEncodingUtils.encode((float) Math.min(Float.MAX_VALUE, x + bottom));
- this.minY = XYEncodingUtils.encode((float) Math.max(-Float.MAX_VALUE, y - bottom));
- this.maxY = XYEncodingUtils.encode((float) Math.min(Float.MAX_VALUE, y + bottom));
+ this.minX = XYEncodingUtils.encode(rectangle.minX);
+ this.maxX = XYEncodingUtils.encode(rectangle.maxX);
+ this.minY = XYEncodingUtils.encode(rectangle.minY);
+ this.maxY = XYEncodingUtils.encode(rectangle.maxY);
}
setBottomCounter++;
}
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Circle2D.java b/lucene/core/src/java/org/apache/lucene/geo/Circle2D.java
index 91690f1..a3227cb 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Circle2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Circle2D.java
@@ -272,19 +272,14 @@ class Circle2D implements Component2D {
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;
+ private final XYRectangle rectangle;
- public CartesianDistance(double centerX, double centerY, double radius) {
+ public CartesianDistance(float centerX, float centerY, float 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;
+ this.rectangle = XYRectangle.fromPointDistance(centerX, centerY, radius);
+ // product performed with doubles
+ this.radiusSquared = (double) radius * radius;
}
@Override
@@ -333,32 +328,32 @@ class Circle2D implements Component2D {
@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);
+ return Component2D.disjoint(rectangle.minX, rectangle.maxX, rectangle.minY, rectangle.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);
+ return Component2D.within(rectangle.minX, rectangle.maxX, rectangle.minY, rectangle.maxY, minX, maxX, minY, maxY);
}
@Override
public double getMinX() {
- return minX;
+ return rectangle.minX;
}
@Override
public double getMaxX() {
- return maxX;
+ return rectangle.maxX;
}
@Override
public double getMinY() {
- return minY;
+ return rectangle.minY;
}
@Override
public double getMaxY() {
- return maxY;
+ return rectangle.maxY;
}
@Override
diff --git a/lucene/core/src/java/org/apache/lucene/geo/XYRectangle.java b/lucene/core/src/java/org/apache/lucene/geo/XYRectangle.java
index 8012d79..99c0154 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/XYRectangle.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/XYRectangle.java
@@ -62,6 +62,26 @@ public final class XYRectangle extends XYGeometry {
}
+ /** Compute Bounding Box for a circle in cartesian geometry */
+ public static XYRectangle fromPointDistance(final float x, final float y, final float radius) {
+ checkVal(x);
+ checkVal(y);
+ 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);
+ }
+ // LUCENE-9243: We round up the bounding box to avoid
+ // numerical errors.
+ float distanceBox = Math.nextUp(radius);
+ float minX = Math.max(-Float.MAX_VALUE, x - distanceBox);
+ float maxX = Math.min(Float.MAX_VALUE, x + distanceBox);
+ float minY = Math.max(-Float.MAX_VALUE, y - distanceBox);
+ float maxY = Math.min(Float.MAX_VALUE, y + distanceBox);
+ return new XYRectangle(minX, maxX, minY, maxY);
+ }
+
@Override
public int hashCode() {
int result;
diff --git a/lucene/core/src/test/org/apache/lucene/geo/TestXYRectangle.java b/lucene/core/src/test/org/apache/lucene/geo/TestXYRectangle.java
index e3a4689..fd2b944 100644
--- a/lucene/core/src/test/org/apache/lucene/geo/TestXYRectangle.java
+++ b/lucene/core/src/test/org/apache/lucene/geo/TestXYRectangle.java
@@ -18,6 +18,7 @@ package org.apache.lucene.geo;
import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.util.TestUtil;
public class TestXYRectangle extends LuceneTestCase {
@@ -103,4 +104,56 @@ public class TestXYRectangle extends LuceneTestCase {
}
}
+ /** make sure that if a point is inside a circle, it is inside of the bbox as well */
+ public void testRandomCircleToBBox() {
+ int iters = atLeast(100);
+ for(int iter= 0;iter < iters; iter++) {
+
+ float centerX = ShapeTestUtil.nextFloat(random());
+ float centerY = ShapeTestUtil.nextFloat(random());
+
+ final float radius;
+ if (random().nextBoolean()) {
+ radius = random().nextFloat() * TestUtil.nextInt(random(), 1, 100000);
+ } else {
+ radius = Math.abs(ShapeTestUtil.nextFloat(random()));
+ }
+
+ XYRectangle bbox = XYRectangle.fromPointDistance(centerX, centerY, radius);
+ Component2D component2D = bbox.toComponent2D();
+
+ int numPointsToTry = 1000;
+ for(int i = 0; i < numPointsToTry; i++) {
+
+ double x;
+ if (random().nextBoolean()) {
+ x = Math.min(Float.MAX_VALUE, centerX + radius + random().nextDouble());
+ } else {
+ x = Math.max(-Float.MAX_VALUE, centerX + radius - random().nextDouble());
+ }
+ double y;
+ if (random().nextBoolean()) {
+ y = Math.min(Float.MAX_VALUE, centerY + radius + random().nextDouble());
+ } else {
+ y = Math.max(-Float.MAX_VALUE, centerY + radius - random().nextDouble());
+ }
+
+ // cartesian says it's within the circle:
+ boolean cartesianSays = component2D.contains(x, y);
+ // BBox says its within the box:
+ boolean bboxSays = x >= bbox.minX && x <= bbox.maxX && y >= bbox.minY && y <= bbox.maxY;
+
+ if (cartesianSays) {
+ if (bboxSays == false) {
+ System.out.println(" centerX=" + centerX + " centerY=" + centerY + " radius=" + radius);
+ System.out.println(" bbox: x=" + bbox.minX + " to " + bbox.maxX + " y=" + bbox.minY + " to " + bbox.maxY);
+ System.out.println(" point: x=" + x + " y=" + y);
+ fail("point was within the distance according to cartesian distance, but the bbox doesn't contain it");
+ }
+ } else {
+ // it's fine if cartesian said it was outside the radius and bbox said it was inside the box
+ }
+ }
+ }
+ }
}
\ No newline at end of file