# lucene-dev mailing list archives

##### Site index · List index
Message view
Top
From "Karl Wright (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (LUCENE-6699) Integrate lat/lon BKD and spatial3d
Date Fri, 21 Aug 2015 09:29:46 GMT
```
[ https://issues.apache.org/jira/browse/LUCENE-6699?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14706460#comment-14706460
]

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

[~mikemccand] Looking at the source of the actual error, here's how it works.

The GeoCircle shape constructs its plane using the following code:

{code}
// Construct normal plane
final Plane normalPlane = Plane.constructNormalizedZPlane(upperPoint, lowerPoint, center);
// Construct a sided plane that goes through the two points and whose normal is in the
normalPlane.
this.circlePlane = SidedPlane.constructNormalizedPerpendicularSidedPlane(center, normalPlane,
upperPoint, lowerPoint);
if (circlePlane == null)
throw new RuntimeException("Couldn't construct circle plane.  Cutoff angle = "+cutoffAngle+";
upperPoint = "+upperPoint+"; lowerPoint = "+lowerPoint);
this.edgePoints = new GeoPoint[]{upperPoint};
{code}

So, it constructs a plane including the Z axis first, then constructs a plane perpendicular
to it.  The edge point of that plane is one of the points it used to construct both the Z
plane and the perpendicular plane.  Tests show that the edge point is not quite perfectly
on the circle edge, but is close enough to pass isWithin().  (This is expected given the math
that has to take place to construct the circle plane.  The error gets larger the smaller the
circle is.)

When the bounds are computed, another plane intersection is computed.  This adds more error,
of a comparable amount.  So we are dealing here with twice the amount of error as usual.

Solutions: I *could* compute the edge point directly from the vertical plane and the circle
plane.  This adds an additional square root and a couple of allocations to the cost of constructing
a circle.  Or, I *could* add in the edge point to the GeoCircle bounds computation.  That's
not quite right but would effectively solve the problem forever at little cost.  Finally,
we could keep fiddling with MINIMUM_RESOLUTION which technically would also be able to solve
the problem at some point.  Which would you prefer?

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