You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by kw...@apache.org on 2017/12/01 15:46:24 UTC
lucene-solr:branch_6x: LUCENE-8071: Handle large concave circles
properly. Committed on behalf of Ignacio Vera.
Repository: lucene-solr
Updated Branches:
refs/heads/branch_6x 8a385a07e -> 1f1d7a326
LUCENE-8071: Handle large concave circles properly. Committed on behalf of Ignacio Vera.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/1f1d7a32
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/1f1d7a32
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/1f1d7a32
Branch: refs/heads/branch_6x
Commit: 1f1d7a326de28326a841229ace3519babba462f2
Parents: 8a385a0
Author: Karl Wright <Da...@gmail.com>
Authored: Fri Dec 1 10:44:58 2017 -0500
Committer: Karl Wright <Da...@gmail.com>
Committed: Fri Dec 1 10:45:52 2017 -0500
----------------------------------------------------------------------
.../lucene/spatial3d/geom/GeoExactCircle.java | 60 +++++---------------
.../spatial3d/geom/GeoExactCircleTest.java | 8 +++
2 files changed, 21 insertions(+), 47 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/1f1d7a32/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoExactCircle.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoExactCircle.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoExactCircle.java
index 1d14ce0..5726e60 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoExactCircle.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoExactCircle.java
@@ -35,13 +35,8 @@ class GeoExactCircle extends GeoBaseCircle {
protected final double cutoffAngle;
/** Actual accuracy */
protected final double actualAccuracy;
-
/** A point that is on the world and on the circle plane */
protected final GeoPoint[] edgePoints;
-
- /** Notable points for a circle -- there aren't any */
- protected static final GeoPoint[] circlePoints = new GeoPoint[0];
-
/** Slices of the circle. */
protected final List<CircleSlice> circleSlices;
@@ -73,7 +68,7 @@ class GeoExactCircle extends GeoBaseCircle {
} else {
actualAccuracy = accuracy;
}
-
+
// We construct approximation planes until we have a low enough error estimate
final List<ApproximationSlice> slices = new ArrayList<>(100);
// Construct four cardinal points, and then we'll build the first two planes
@@ -81,17 +76,18 @@ class GeoExactCircle extends GeoBaseCircle {
final GeoPoint southPoint = planetModel.surfacePointOnBearing(center, cutoffAngle, Math.PI);
final GeoPoint eastPoint = planetModel.surfacePointOnBearing(center, cutoffAngle, Math.PI * 0.5);
final GeoPoint westPoint = planetModel.surfacePointOnBearing(center, cutoffAngle, Math.PI * 1.5);
-
+
+ final boolean mustSplit = cutoffAngle > Math.PI * 0.5;
final GeoPoint edgePoint;
if (planetModel.c > planetModel.ab) {
// z can be greater than x or y, so ellipse is longer in height than width
- slices.add(new ApproximationSlice(center, eastPoint, Math.PI * 0.5, westPoint, Math.PI * -0.5, northPoint, 0.0));
- slices.add(new ApproximationSlice(center, westPoint, Math.PI * 1.5, eastPoint, Math.PI * 0.5, southPoint, Math.PI));
+ slices.add(new ApproximationSlice(center, eastPoint, Math.PI * 0.5, westPoint, Math.PI * -0.5, northPoint, 0.0, mustSplit));
+ slices.add(new ApproximationSlice(center, westPoint, Math.PI * 1.5, eastPoint, Math.PI * 0.5, southPoint, Math.PI, mustSplit));
edgePoint = eastPoint;
} else {
// z will be less than x or y, so ellipse is shorter than it is tall
- slices.add(new ApproximationSlice(center, northPoint, 0.0, southPoint, Math.PI, eastPoint, Math.PI * 0.5));
- slices.add(new ApproximationSlice(center, southPoint, Math.PI, northPoint, Math.PI * 2.0, westPoint, Math.PI * 1.5));
+ slices.add(new ApproximationSlice(center, northPoint, 0.0, southPoint, Math.PI, eastPoint, Math.PI * 0.5, mustSplit));
+ slices.add(new ApproximationSlice(center, southPoint, Math.PI, northPoint, Math.PI * 2.0, westPoint, Math.PI * 1.5, mustSplit));
edgePoint = northPoint;
}
//System.out.println("Edgepoint = " + edgePoint);
@@ -111,7 +107,7 @@ class GeoExactCircle extends GeoBaseCircle {
final GeoPoint interpPoint2 = planetModel.surfacePointOnBearing(center, cutoffAngle, interpPoint2Bearing);
// Is this point on the plane? (that is, is the approximation good enough?)
- if (Math.abs(thisSlice.plane.evaluate(interpPoint1)) < actualAccuracy && Math.abs(thisSlice.plane.evaluate(interpPoint2)) < actualAccuracy) {
+ if (!thisSlice.mustSplit && Math.abs(thisSlice.plane.evaluate(interpPoint1)) < actualAccuracy && Math.abs(thisSlice.plane.evaluate(interpPoint2)) < actualAccuracy) {
circleSlices.add(new CircleSlice(thisSlice.plane, thisSlice.endPoint1, thisSlice.endPoint2, center, thisSlice.middlePoint));
//assert thisSlice.plane.isWithin(center);
} else {
@@ -119,11 +115,11 @@ class GeoExactCircle extends GeoBaseCircle {
slices.add(new ApproximationSlice(center,
thisSlice.endPoint1, thisSlice.point1Bearing,
thisSlice.middlePoint, thisSlice.middlePointBearing,
- interpPoint1, interpPoint1Bearing));
+ interpPoint1, interpPoint1Bearing, false));
slices.add(new ApproximationSlice(center,
thisSlice.middlePoint, thisSlice.middlePointBearing,
thisSlice.endPoint2, thisSlice.point2Bearing,
- interpPoint2, interpPoint2Bearing));
+ interpPoint2, interpPoint2Bearing, false));
}
}
@@ -177,12 +173,6 @@ class GeoExactCircle extends GeoBaseCircle {
@Override
protected double outsideDistance(final DistanceStyle distanceStyle, final double x, final double y, final double z) {
- if (circleSlices.size() == 0) {
- return 0.0;
- }
- if (circleSlices.size() == 1) {
- return distanceStyle.computeDistance(planetModel, circleSlices.get(0).circlePlane, x, y, z);
- }
double outsideDistance = Double.POSITIVE_INFINITY;
for (final CircleSlice slice : circleSlices) {
final double distance = distanceStyle.computeDistance(planetModel, slice.circlePlane, x, y, z, slice.plane1, slice.plane2);
@@ -195,9 +185,6 @@ class GeoExactCircle extends GeoBaseCircle {
@Override
public boolean isWithin(final double x, final double y, final double z) {
- if (circleSlices.size() == 0) {
- return true;
- }
for (final CircleSlice slice : circleSlices) {
if (slice.circlePlane.isWithin(x, y, z) && slice.plane1.isWithin(x, y, z) && slice.plane2.isWithin(x, y, z)) {
return true;
@@ -213,12 +200,6 @@ class GeoExactCircle extends GeoBaseCircle {
@Override
public boolean intersects(final Plane p, final GeoPoint[] notablePoints, final Membership... bounds) {
- if (circleSlices.size() == 0) {
- return false;
- }
- if (circleSlices.size() == 1) {
- return circleSlices.get(0).circlePlane.intersects(planetModel, p, notablePoints, circlePoints, bounds);
- }
for (final CircleSlice slice : circleSlices) {
if (slice.circlePlane.intersects(planetModel, p, notablePoints, slice.notableEdgePoints, bounds, slice.plane1, slice.plane2)) {
return true;
@@ -229,13 +210,6 @@ class GeoExactCircle extends GeoBaseCircle {
@Override
public boolean intersects(GeoShape geoShape) {
- if (circleSlices.size() == 0) {
- return false;
- }
- if (circleSlices.size() == 1) {
- return geoShape.intersects(circleSlices.get(0).circlePlane, circlePoints);
- }
-
for (final CircleSlice slice : circleSlices) {
if (geoShape.intersects(slice.circlePlane, slice.notableEdgePoints, slice.plane1, slice.plane2)) {
return true;
@@ -248,14 +222,7 @@ class GeoExactCircle extends GeoBaseCircle {
@Override
public void getBounds(Bounds bounds) {
super.getBounds(bounds);
- if (circleSlices.size() == 0) {
- return;
- }
bounds.addPoint(center);
- if (circleSlices.size() == 1) {
- bounds.addPlane(planetModel, circleSlices.get(0).circlePlane);
- return;
- }
for (final CircleSlice slice : circleSlices) {
bounds.addPlane(planetModel, slice.circlePlane, slice.plane1, slice.plane2);
for (final GeoPoint point : slice.notableEdgePoints) {
@@ -298,17 +265,19 @@ class GeoExactCircle extends GeoBaseCircle {
public final double point2Bearing;
public final GeoPoint middlePoint;
public final double middlePointBearing;
+ public final boolean mustSplit;
public ApproximationSlice(final GeoPoint center,
final GeoPoint endPoint1, final double point1Bearing,
final GeoPoint endPoint2, final double point2Bearing,
- final GeoPoint middlePoint, final double middlePointBearing) {
+ final GeoPoint middlePoint, final double middlePointBearing, final boolean mustSplit) {
this.endPoint1 = endPoint1;
this.point1Bearing = point1Bearing;
this.endPoint2 = endPoint2;
this.point2Bearing = point2Bearing;
this.middlePoint = middlePoint;
this.middlePointBearing = middlePointBearing;
+ this.mustSplit = mustSplit;
// Construct the plane going through the three given points
this.plane = SidedPlane.constructNormalizedThreePointSidedPlane(center, endPoint1, endPoint2, middlePoint);
if (this.plane == null) {
@@ -347,7 +316,4 @@ class GeoExactCircle extends GeoBaseCircle {
" plane 2 = " + plane2 + " notable edge points = " + notableEdgePoints + "}";
}
}
-
-
-
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/1f1d7a32/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoExactCircleTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoExactCircleTest.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoExactCircleTest.java
index 29dcff9..859cded 100644
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoExactCircleTest.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoExactCircleTest.java
@@ -133,6 +133,14 @@ public class GeoExactCircleTest extends RandomGeo3dShapeGenerator{
assertTrue(exception);
}
+ public void testBigCircleInSphere() {
+ //In Planet model Sphere if circle is close to Math.PI we can get the situation where
+ //circle slice planes are bigger than half of a hemisphere. We need to make
+ //sure we divide the circle in at least 4 slices.
+ GeoCircle circle1 = GeoCircleFactory.makeExactGeoCircle(PlanetModel.SPHERE, 1.1306735252307394, -0.7374283438171261, 3.1415760537549234, 4.816939220262406E-12);
+ GeoPoint point = new GeoPoint(PlanetModel.SPHERE, -1.5707963267948966, 0.0);
+ assertTrue(circle1.isWithin(point));
+ }
/**
* in LUCENE-8054 we have problems with exact circles that have