lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kwri...@apache.org
Subject lucene-solr:master: LUCENE-8071: Handle large concave circles properly. Committed on behalf of Ignacio Vera.
Date Fri, 01 Dec 2017 15:45:07 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/master 832a975bc -> 6c3869f8b


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/6c3869f8
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/6c3869f8
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/6c3869f8

Branch: refs/heads/master
Commit: 6c3869f8b1932cef7e13ebc91fe3b04532215ea5
Parents: 832a975
Author: Karl Wright <DaddyWri@gmail.com>
Authored: Fri Dec 1 10:44:58 2017 -0500
Committer: Karl Wright <DaddyWri@gmail.com>
Committed: Fri Dec 1 10:44:58 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/6c3869f8/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/6c3869f8/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


Mime
View raw message