lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Karl Wright (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (LUCENE-6699) Integrate lat/lon BKD and spatial3d
Date Sat, 22 Aug 2015 11:17:46 GMT

    [ https://issues.apache.org/jira/browse/LUCENE-6699?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14707988#comment-14707988
] 

Karl Wright commented on LUCENE-6699:
-------------------------------------

[~mikemccand] Here's the analysis, so far.

I first enabled evaluation of all four points where the XYZSolid intersected the planet surface.
 As you can see, only one of them comes back as being inside the GeoCircle:

{code}
   [junit4]   2>  Point 1.0010913867774043 0.007079167343247293 -0.0021855011220022575:
shape.isWithin? true; minx=9.128715394490783E-6, maxx=-3.191195882434883E-6, miny=0.0, maxy=-4.618394311805439E-4,
minz=0.0, maxz=-2.893784038207395E-4
   [junit4]   2>  Point 1.0010919806760743 0.007079167343247293 -0.001896122718181518:
shape.isWithin? false; minx=9.722614064511248E-6, maxx=-2.597297212414418E-6, miny=0.0, maxy=-4.618394311805439E-4,
minz=2.893784038207395E-4, maxz=0.0
   [junit4]   2>  Point 1.001088014365874 0.007541006774427837 -0.0021855011220022575:
shape.isWithin? false; minx=5.7563038642349795E-6, maxx=-6.563607412690686E-6, miny=4.618394311805439E-4,
maxy=0.0, minz=0.0, maxz=-2.893784038207395E-4
   [junit4]   2>  Point 1.0010886082665449 0.007541006774427837 -0.001896122718181518:
shape.isWithin? false; minx=6.35020453509938E-6, maxx=-5.969706741826286E-6, miny=4.618394311805439E-4,
maxy=0.0, minz=2.893784038207395E-4, maxz=0.0
{code}

If the above is an accurate picture, then there should be intersections between the GeoCircle
and two of the edge planes.

miny should intersect:

{code}
   [junit4]   2>  Point 1.0010913867774043 0.007079167343247293 -0.0021855011220022575:
shape.isWithin? true; minx=9.128715394490783E-6, maxx=-3.191195882434883E-6, miny=0.0, maxy=-4.618394311805439E-4,
minz=0.0, maxz=-2.893784038207395E-4
   [junit4]   2>  Point 1.0010919806760743 0.007079167343247293 -0.001896122718181518:
shape.isWithin? false; minx=9.722614064511248E-6, maxx=-2.597297212414418E-6, miny=0.0, maxy=-4.618394311805439E-4,
minz=2.893784038207395E-4, maxz=0.0
{code}

And, minz should intersect:

{code}
   [junit4]   2>  Point 1.0010913867774043 0.007079167343247293 -0.0021855011220022575:
shape.isWithin? true; minx=9.128715394490783E-6, maxx=-3.191195882434883E-6, miny=0.0, maxy=-4.618394311805439E-4,
minz=0.0, maxz=-2.893784038207395E-4
   [junit4]   2>  Point 1.001088014365874 0.007541006774427837 -0.0021855011220022575:
shape.isWithin? false; minx=5.7563038642349795E-6, maxx=-6.563607412690686E-6, miny=4.618394311805439E-4,
maxy=0.0, minz=0.0, maxz=-2.893784038207395E-4
{code}

These two intersections are not being detected, and after much careful analysis, I concluded
that the reason that they are not being detected is because no intersection actually happens.
 Looking at the miny plane:

{code}
   [junit4]   2> Checking for intersections that should be found...
   [junit4]   2>  Not identical plane
   [junit4]   2> Looking for intersection between plane [A=-0.9999680546313309, B=-0.0046605790633783275,
C=0.006493744653569968, D=1.0011065916522879, side=-1.0] and plane [A=0.0, B=1.0, C=0.0, D=-0.007079167343247293,
side=1.0] within bounds
   [junit4]   2>  Two points of intersection
   [junit4]   2>   [X=1.0010359045488204, Y=0.0070791673432472925, Z=-0.010729178478687706]
this=(0.0) q=(-8.673617379884035E-19), and [X=1.0010913867758835, Y=0.0070791673432472925,
Z=-0.0021855018140558226] this=(0.0) q=(-8.673617379884035E-19)
{code}

Two points of intersection are detected, but both are outside the X or Z bounds of the XYZSolid,
so they do not represent intersection.

So, how can this be?  Well, the reason for the discrepancy is because the first point of the
four mentioned at the top is, in fact, not really inside the GeoCircle.  It is coming up as
being inside the GeoCircle only because of the fact that we've increased MINIMUM_RESOLUTION
from its original value of 1e-12:

{code}
   [junit4]   2> circlePlane eval = 2.9731772599461692E-12
{code}

So the problem is that ONE measure of error (point within GeoCircle) disagrees with another
measure of error (intersection points in or out of XYZSolid), leading to an incorrect assessment.

This is obviously going to be challenging to address.  I may need to introduce two distinct
error bounds in order for this logic to be robust.  But I have to think it through carefully.

> Integrate lat/lon BKD and spatial3d
> -----------------------------------
>
>                 Key: LUCENE-6699
>                 URL: https://issues.apache.org/jira/browse/LUCENE-6699
>             Project: Lucene - Core
>          Issue Type: New Feature
>            Reporter: Michael McCandless
>            Assignee: Michael McCandless
>         Attachments: Geo3DPacking.java, LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch,
LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch,
LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch,
LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch,
LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch,
LUCENE-6699.patch, LUCENE-6699.patch, LUCENE-6699.patch
>
>
> I'm opening this for discussion, because I'm not yet sure how to do
> this integration, because of my ignorance about spatial in general and
> spatial3d in particular :)
> Our BKD tree impl is very fast at doing lat/lon shape intersection
> (bbox, polygon, soon distance: LUCENE-6698) against previously indexed
> points.
> I think to integrate with spatial3d, we would first need to record
> lat/lon/z into doc values.  Somewhere I saw discussion about how we
> could stuff all 3 into a single long value with acceptable precision
> loss?  Or, we could use BinaryDocValues?  We need all 3 dims available
> to do the fast per-hit query time filtering.
> But, second: what do we index into the BKD tree?  Can we "just" index
> earth surface lat/lon, and then at query time is spatial3d able to
> give me an enclosing "surface lat/lon" bbox for a 3d shape?  Or
> ... must we index all 3 dimensions into the BKD tree (seems like this
> could be somewhat wasteful)?



--
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


Mime
View raw message