You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Nicholas Knize (JIRA)" <ji...@apache.org> on 2015/12/03 00:49:10 UTC
[jira] [Comment Edited] (LUCENE-6908) TestGeoUtils.testGeoRelations
is buggy with irregular rectangles
[ https://issues.apache.org/jira/browse/LUCENE-6908?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15036890#comment-15036890 ]
Nicholas Knize edited comment on LUCENE-6908 at 12/2/15 11:48 PM:
------------------------------------------------------------------
Thanks [~mikemccand]. In {{isClosestPointOnRectWithinRange}} it was still using {{SloppyMath.haversin}} where it should have been using the Sinnott haversine. Looks like it was caused by a premature diff from my benchmark workspace.
A quick interesting benchmark re: distance methods. Using 2M iterations I benchmarked average computation time, average spatial error, and maximum spatial error between 5 different geospatial distance methods:
* Vincenty
* Karney - Modified Vincenty that uses Newton's series expansion to fix problems w/ antipodal points
* HaverECF - Same as {{SloppyMath.haversin}} but uses ECEF to accurately compute semi-major axis at the given latitude.
* Sinnott's Haversine - Implementation from the original haversine publication
* SloppyMath.haversin
|| Distance Method || Avg Computation (ns) || Avg Error (%) || Max Error (%) ||
| Vincenty | 1286.5529689998828 | 8.4561794778802E-11 | 7.2565793775802E-10 |
| Karney | 31770.479206999946 | 8.4561794778802E-11 | 7.2565793775802E-10 |
| HaverECF | 717.1139850000152 | 0.18409042301798453 | 0.6681179192384695 |
| SloppyMath.haverin | 159.3095249999995 | 0.22594450803222424 | 0.6539314586426048 |
| Sinnott Haversine | 146.81236699999738 | 0.18158435835918563 | 0.4931242857748373 |
I need to run some better descriptive statistics before drawing any conclusions. At the moment, the discrepancy between {{Sloppymath.haversin}} and Sinnott's implementation is consistent with the error described in the original publication (which is where the tolerance of 0.5% originated).
More to come....
was (Author: nknize):
Thanks [~mikemccand]. In {{isClosestPointOnRectWithinRange}} it was still using {{SloppyMath.haversin}} where it should have been using the Sinnott haversine. Looks like it was caused by a premature diff from my benchmark workspace.
A quick interesting benchmark re: distance methods. Using 2M iterations I benchmarked average computation time, average spatial error, and maximum spatial error between 5 different geospatial distance methods:
* Vincenty
* Karney - Modified Vincenty that uses Newton's series expansion to fix problems w/ antipodal points
* HaverECF - Same as {{SloppyMath.haversin}} but uses ECEF to accurately compute semi-major axis at the given latitude.
* Sinnott's Haversine - Implementation from the original haversine publicatoin
* SloppyMath
|| Distance Method || Avg Computation (ns) || Avg Error (%) || Max Error (%) ||
| Vincenty | 1286.5529689998828 | 8.4561794778802E-11 | 7.2565793775802E-10 |
| Karney | 31770.479206999946 | 8.4561794778802E-11 | 7.2565793775802E-10 |
| HaverECF | 717.1139850000152 | 0.18409042301798453 | 0.6681179192384695 |
| SloppyMath.haverin | 159.3095249999995 | 0.22594450803222424 | 0.6539314586426048 |
| Sinnott Haversine | 146.81236699999738 | 0.18158435835918563 | 0.4931242857748373 |
I need to run some better descriptive statistics before drawing any conclusions. At the moment, the discrepancy between {{Sloppymath.haversin}} and Sinnott's implementation is consistent with the error described in the original publication (which is where the tolerance of 0.5% originated).
More to come....
> TestGeoUtils.testGeoRelations is buggy with irregular rectangles
> ----------------------------------------------------------------
>
> Key: LUCENE-6908
> URL: https://issues.apache.org/jira/browse/LUCENE-6908
> Project: Lucene - Core
> Issue Type: Bug
> Reporter: Nicholas Knize
> Attachments: LUCENE-6908.patch, LUCENE-6908.patch, LUCENE-6908.patch, LUCENE-6908.patch
>
>
> The {{.testGeoRelations}} method doesn't exactly test the behavior of GeoPoint*Query as its using the BKD split technique (instead of quad cell division) to divide the space on each pass. For "large" distance queries this can create a lot of irregular rectangles producing large radial distortion error when using the cartesian approximation methods provided by {{GeoUtils}}. This issue improves the accuracy of GeoUtils cartesian approximation methods on irregular rectangles without having to cut over to an expensive oblate geometry approach.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org