G3d wrapper: Improve circles for non spherical planets [LUCENE-8086]

[asfimport]

Hi @dsmiley,

The purpose of this ticket is to add a new circle shape (GeoExactCircle) for non-spherical planets and therefore remove the method relate from Geo3dCircleShape. The patch will include some simplifications on the wrapper and some refactoring of the tests.

I will open shortly a pull request.

---

Migrated from LUCENE-8086 by Ignacio Vera (@iverase), resolved Dec 13 2017

[asfimport]

ASF GitHub Bot (migrated from JIRA)

GitHub user iverase opened a pull request:

https://github.com/apache/lucene-solr/pull/288

LUCENE-8086

Here are the changes, in particular:

• Geo3dFactory: Use GeoExactCircle for non-spherical planets.
• Geo3dCircleShape: Remove method relate.
• Geo3DShape: Use new factory method for building GeoBbox from bounds object.
• Geo3dDistanceCalculator: use pointonbearing from planet model.
• Test refactoring

You can merge this pull request into a Git repository by running:

$ git pull https://github.com/iverase/lucene-solr master

Alternatively you can review and apply these changes as the patch at:

https://github.com/apache/lucene-solr/pull/288.patch

To close this pull request, make a commit to your master/trunk branch with (at least) the following in the commit message:

This closes `#288`

---

commit 73d9ce324b217c633ae72b24233099dd2afc43d5 Author: iverase <ivera@eso.org> Date: 2017-12-08T15:33:22Z

LUCENE-8086

---

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155821440

— Diff: lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShapeFactory.java —
`@@` -55,6 +55,13 `@@`
   private SpatialContext context;
   private PlanetModel planetModel;

+  /\*\*
+   \* Default accuracy for circles when not using the unit sphere.
+   \* It is equivalent to 10m on the surface of the earth.
+   \*/
+  private static double DEFAULT_CIRCLE_ACCURACY = 1.6e-6;
— End diff –

should be final

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155826399

— Diff: lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dCircleShape.java —
`@@` -67,16 +64,4 `@@` public Point getCenter() {
     }
     return center;
   }
-
— End diff –

Yay

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155822689

— Diff: lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShapeFactory.java —
`@@` -150,10 +176,21 `@@` public Rectangle rect(double minX, double maxX, double minY, double maxY) {

   `@Override`
   public Circle circle(double x, double y, double distance) {

• GeoCircle circle = GeoCircleFactory.makeGeoCircle(planetModel,
• y * DistanceUtils.DEGREES_TO_RADIANS,
• x * DistanceUtils.DEGREES_TO_RADIANS,

• distance * DistanceUtils.DEGREES_TO_RADIANS);

  • GeoCircle circle;
  • if (planetModel.ab == planetModel.c) { — End diff –

  Should there be a method on planetModel that more descriptively characterizes the condition? (e.g. isSpherical?) Just a suggestion; perhaps not if it's too hard to give an appropriate name. If not then maybe add a comment here so we know what "ab" being equal to "c" means.

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155824604

— Diff: lucene/spatial-extras/src/test/org/apache/lucene/spatial/spatial4j/Geo3dShapeRectRelationTestCase.java —
`@@` -155,16 +107,12 `@@` protected Geo3dShape generateRandomShape(Point nearP) {
           ulhcPoint = lrhcPoint;
           lrhcPoint = temp;
         }

• final GeoBBox shape = GeoBBoxFactory.makeGeoBBox(planetModel, ulhcPoint.getY() * DEGREES_TO_RADIANS,
• lrhcPoint.getY() * DEGREES_TO_RADIANS,
• ulhcPoint.getX() * DEGREES_TO_RADIANS,
• lrhcPoint.getX() * DEGREES_TO_RADIANS);

• return new Geo3dShape(shape, ctx);

  • return (Geo3dShape<?>) ctx.getShapeFactory().rect(lrhcPoint, ulhcPoint); — End diff –

  change is good but the variable names are wrong. rect(lowerLeft, upperRight)

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155826444

— Diff: lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dDistanceCalculator.java —
`@@` -73,62 +74,20 `@@` public boolean within(Point from, double toX, double toY, double distance) {

   `@Override`
   public Point pointOnBearing(Point from, double distDEG, double bearingDEG, SpatialContext ctx, Point reuse) {

• // Algorithm using Vincenty's formulae (https://en.wikipedia.org/wiki/Vincenty%27s_formulae)
• // which takes into account that planets may not be spherical.
• //Code adaptation from http://www.movable-type.co.uk/scripts/latlong-vincenty.html Geo3dPointShape geoFrom = (Geo3dPointShape) from; GeoPoint point = (GeoPoint) geoFrom.shape;
• double lat = point.getLatitude();

• double lon = point.getLongitude(); double dist = DistanceUtils.DEGREES_TO_RADIANS * distDEG; double bearing = DistanceUtils.DEGREES_TO_RADIANS * bearingDEG;

  — End diff –

  Yay

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155825386

— Diff: lucene/spatial-extras/src/test/org/apache/lucene/spatial/spatial4j/Geo3dShapeRectRelationTestCase.java —
`@@` -16,29 +16,15 `@@`
  \*/
 package org.apache.lucene.spatial.spatial4j;

-import java.util.ArrayList;
-import java.util.List;
-
-import org.apache.lucene.spatial3d.geom.GeoPath;
-import org.apache.lucene.spatial3d.geom.GeoPolygon;
+import org.junit.Rule;
+import org.junit.Test;
 import org.locationtech.spatial4j.TestLog;
 import org.locationtech.spatial4j.context.SpatialContext;
-import org.locationtech.spatial4j.distance.DistanceUtils;
 import org.locationtech.spatial4j.shape.Circle;
 import org.locationtech.spatial4j.shape.Point;
 import org.locationtech.spatial4j.shape.RectIntersectionTestHelper;
-import org.apache.lucene.spatial3d.geom.LatLonBounds;
— End diff –

If I get this right, you've removed the Geo3D dependencies of this test.  Yet it's still named to be Geo3d?

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155822251

— Diff: lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShapeFactory.java —
`@@` -67,6 +74,25 `@@` public SpatialContext getSpatialContext() {
     return context;
   }

+  /\*\*
+   \* Set the accuracy for circles.
+   \*
+   \* "Accuracy" is defined as the maximum linear distance between any point on the
+   \* surface circle and planes that describe the circle. Therefore on WSG84, since the
+   \* radius of earth is 6,371,000 meters, an accuracy of 1e-6 corresponds to 6.3 meters.
+   \* For an accuracy of 1.0 meters, the value of 1.6e-7.
+   \*
+   \* The default value is set to 10m (1.6e-6).
+   \*
+   \* Note that accuracy has no effect when the planet model is a sphere. In that case circles
+   \* are always fully precise.
+   \*
+   \* `@param` circleAccuracy the provided accuracy as a linear distance.
— End diff –

by "linear distance" do you mean decimal degrees as is used in other parts of the Spatial4j API? If so please say "decimal degrees".  If not, perhaps it should be in that unit?

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user iverase commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155843390

— Diff: lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShapeFactory.java —
`@@` -67,6 +74,25 `@@` public SpatialContext getSpatialContext() {
     return context;
   }

+  /\*\*
+   \* Set the accuracy for circles.
+   \*
+   \* "Accuracy" is defined as the maximum linear distance between any point on the
+   \* surface circle and planes that describe the circle. Therefore on WSG84, since the
+   \* radius of earth is 6,371,000 meters, an accuracy of 1e-6 corresponds to 6.3 meters.
+   \* For an accuracy of 1.0 meters, the value of 1.6e-7.
+   \*
+   \* The default value is set to 10m (1.6e-6).
+   \*
+   \* Note that accuracy has no effect when the planet model is a sphere. In that case circles
+   \* are always fully precise.
+   \*
+   \* `@param` circleAccuracy the provided accuracy as a linear distance.
— End diff –

I need to ask Karl Wright if that is what it means, but I guess so. I will update accordingly.

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user iverase commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155843938

— Diff: lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShapeFactory.java —
`@@` -150,10 +176,21 `@@` public Rectangle rect(double minX, double maxX, double minY, double maxY) {

   `@Override`
   public Circle circle(double x, double y, double distance) {

• GeoCircle circle = GeoCircleFactory.makeGeoCircle(planetModel,
• y * DistanceUtils.DEGREES_TO_RADIANS,
• x * DistanceUtils.DEGREES_TO_RADIANS,

• distance * DistanceUtils.DEGREES_TO_RADIANS);

  • GeoCircle circle;
  • if (planetModel.ab == planetModel.c) { — End diff –

  I think spatial3d is a low level library in that respect, so it shouldn't have such a method. Karl Wright has the last word, comment would be fine

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user iverase commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155844074

— Diff: lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShapeFactory.java —
`@@` -55,6 +55,13 `@@`
   private SpatialContext context;
   private PlanetModel planetModel;

+  /\*\*
+   \* Default accuracy for circles when not using the unit sphere.
+   \* It is equivalent to 10m on the surface of the earth.
+   \*/
+  private static double DEFAULT_CIRCLE_ACCURACY = 1.6e-6;
— End diff –

Indeed!

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user iverase commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155844229

— Diff: lucene/spatial-extras/src/test/org/apache/lucene/spatial/spatial4j/Geo3dShapeRectRelationTestCase.java —
`@@` -155,16 +107,12 `@@` protected Geo3dShape generateRandomShape(Point nearP) {
           ulhcPoint = lrhcPoint;
           lrhcPoint = temp;
         }

• final GeoBBox shape = GeoBBoxFactory.makeGeoBBox(planetModel, ulhcPoint.getY() * DEGREES_TO_RADIANS,
• lrhcPoint.getY() * DEGREES_TO_RADIANS,
• ulhcPoint.getX() * DEGREES_TO_RADIANS,
• lrhcPoint.getX() * DEGREES_TO_RADIANS);

• return new Geo3dShape(shape, ctx);

  • return (Geo3dShape<?>) ctx.getShapeFactory().rect(lrhcPoint, ulhcPoint); — End diff –

  Indeed!

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user iverase commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155844958

— Diff: lucene/spatial-extras/src/test/org/apache/lucene/spatial/spatial4j/Geo3dShapeRectRelationTestCase.java —
`@@` -16,29 +16,15 `@@`
  \*/
 package org.apache.lucene.spatial.spatial4j;

-import java.util.ArrayList;
-import java.util.List;
-
-import org.apache.lucene.spatial3d.geom.GeoPath;
-import org.apache.lucene.spatial3d.geom.GeoPolygon;
+import org.junit.Rule;
+import org.junit.Test;
 import org.locationtech.spatial4j.TestLog;
 import org.locationtech.spatial4j.context.SpatialContext;
-import org.locationtech.spatial4j.distance.DistanceUtils;
 import org.locationtech.spatial4j.shape.Circle;
 import org.locationtech.spatial4j.shape.Point;
 import org.locationtech.spatial4j.shape.RectIntersectionTestHelper;
-import org.apache.lucene.spatial3d.geom.LatLonBounds;
— End diff –

I didn't dear to change it but that was the idea of the effort, I will remove Geo3d. 

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

Thanks for the quick review, I don't think I will manage to do the changes during the weekend so early next week.

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155938309

— Diff: lucene/spatial-extras/src/test/org/apache/lucene/spatial/spatial4j/ShapeRectRelationTestCase.java —
`@@` -75,9 +75,9 `@@` public void testGeoCircleRect() {
     new Geo3dRectIntersectionTestHelper(ctx) {
— End diff –

Should be renamed as this class is no longer Geo3d specific

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

Hi @DaddyWri,

Can you review the following supositions:

1) Accuracy in GeoExactCircle is defined as a linear distance, still I guess is a distance in radians, is that correct?

2) Is correct to represent that error in decimal degrees by using transformation between radians and degrees?

I checked the value provided in here:

https://en.wikipedia.org/wiki/Decimal_degrees

1m correspond to around 9e-6 decimal degrees with is more or less 1.6e-7 radians. So it looks consistent.

Thanks!

[asfimport]

Karl Wright (@DaddyWri) (migrated from JIRA)

@iverase, the error distance is the linear (perpendicular) distance from a plane to a point that is supposedly on that plane but which is not quite.

The units we're using here are not radians – those are an angular unit. Instead we're talking about the unit ellipsoid, where x^2/ab^2 + y^2/ab^2 + z^2/c^2 = 1. (It is possible, as you noted before, to construct a non-unit planetmodel, but I don't know what effects that might have, and maybe we should put in a check to prevent it.) The error is therefore relative to 1.0, so it's best described as a fraction of the circle or ellipsoid.

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

I guess we do not want to expose this complexity on this interface and it would be nice if accuracy could be expressed in decimal degrees to follow spatial4j convention.

We are dealing at the moment with unit planet models so better don't worry about that now.

What comes to my mind is that we can approximate linear distance to surface distance (in radians) at this level as distances are very tiny. Then the problem is easy as we just need to transform between degrees and radians to set accuracy. I think we are overstimating the accuracy so everything should be ok.

Does it make sense?

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155938315

— Diff: lucene/spatial-extras/src/test/org/apache/lucene/spatial/spatial4j/ShapeRectRelationTestCase.java —
`@@` -28,15 +28,15 `@@`

 import static org.locationtech.spatial4j.distance.DistanceUtils.DEGREES_TO_RADIANS;

-public abstract class Geo3dShapeRectRelationTestCase extends RandomizedShapeTestCase {
+public abstract class ShapeRectRelationTestCase extends RandomizedShapeTestCase {
   protected final static double RADIANS_PER_DEGREE = Math.PI/180.0;

   `@Rule`
   public final TestLog testLog = TestLog.instance;

   protected int maxRadius = 180;

• public Geo3dShapeRectRelationTestCase() {

  • public ShapeRectRelationTestCase() { super(SpatialContext.GEO); — End diff –

  I think the subclass should pass in the context.

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user dsmiley commented on a diff in the pull request:

https://github.com/apache/lucene-solr/pull/288#discussion_r155938328

— Diff: lucene/spatial-extras/src/java/org/apache/lucene/spatial/spatial4j/Geo3dShapeFactory.java —
`@@` -150,10 +176,21 `@@` public Rectangle rect(double minX, double maxX, double minY, double maxY) {

   `@Override`
   public Circle circle(double x, double y, double distance) {

• GeoCircle circle = GeoCircleFactory.makeGeoCircle(planetModel,
• y * DistanceUtils.DEGREES_TO_RADIANS,
• x * DistanceUtils.DEGREES_TO_RADIANS,

• distance * DistanceUtils.DEGREES_TO_RADIANS);

  • GeoCircle circle;
  • if (planetModel.ab == planetModel.c) { — End diff –

  @DaddyWri comments?

[asfimport]

David Smiley (@dsmiley) (migrated from JIRA)

@DaddyWri and @iverase I'm looking at GeoCircleFactory and GeoStandardCircle and GeoExactCircle. Try to put yourself into a user's shoes who has no idea which to choose. Note that both circles have the same class javadocs (albeit not "public"). Also note that both factory methods on GeoCircleFactory look similar. So I've been following these issues loosely and have some vague idea of what's going on. I think it's weird that GeoExactCircle is named as such which, by it's name, might suggest (to me) that any other circle isn't "exact". Yet AFAICT this isn't true and in fact is the opposite! GeoStandardCircle is accurate in spherical, and GeoExactCircle, despite it's name, is an approximation with configurable error for non-spherical.

Sure some more/better javadocs would help but I have to wonder if we need to express the distinction publicly. That is... if the PlanetModel passed is a sphere, then use GeoStandardCircle, and if it isn't, use GeoExactCircle. Essentially with this I'm suggesting moving the change in this patch in Geo3dShapeFactory (Spatial4j abstraction) to GeoCircleFactory (down a layer of abstraction). WDYT?

[asfimport]

David Smiley (@dsmiley) (migrated from JIRA)

BTW @iverase my tentative CHANGES.txt note for this issue is this:

* LUCENE-8086: spatial-extras Geo3dFactory: Use GeoExactCircle with
  configurable precision for non-spherical planet models.
  (Ignacio Vera via David Smiley)

Yeah I know there's more going on but I think that's essentially it from a user perspective. It's common for issues to include various internal refactorings but need not mention in CHANGES.txt.

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

Hi @dsmiley,

Here are my comments:

1) The javadocs can indeed be improved. I open a JIRA ticket and added a patch with my suggestions.

2) Both shapes should be exposed and it should be the user that decides which one fits his/her use case. It is perfectly fine to use GeoStandardCircle in non-spherical planets if you are not so worried about accuracy as it is the fastest shape. I can even imagine applications that use this type of circles for big radius and then use GeoExactCircle where radius become small. The implementation I have provided is maybe the more generic approach but it is a decision I made and I think it belongs there .... maybe one day it is decided to do it in a different way e.g. depending on radio size.

3) The CHANGES.txt note is fine. The other changes on the patch are just cosmetic.

Thanks!

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit d66d9549d7c4fe50eb599a2960c555d06d335a2a in lucene-solr's branch refs/heads/master from @dsmiley https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=d66d954

LUCENE-8086: spatial-extras Geo3dFactory: Use GeoExactCircle with configurable precision for non-spherical planet models. Some internal refactorings as well.

[asfimport]

ASF subversion and git services (migrated from JIRA)

Commit caf401c43bbe40771ae633c1a62732823930f35f in lucene-solr's branch refs/heads/branch_7x from @dsmiley https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=caf401c

LUCENE-8086: spatial-extras Geo3dFactory: Use GeoExactCircle with configurable precision for non-spherical planet models. Some internal refactorings as well.

(cherry picked from commit d66d954)

[asfimport]

ASF GitHub Bot (migrated from JIRA)

Github user iverase closed the pull request at:

https://github.com/apache/lucene-solr/pull/288