[
https://issues.apache.org/jira/browse/LUCENE-6196?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14291938#comment-14291938
]
Karl Wright commented on LUCENE-6196:
-------------------------------------
Attention math whizzes: So in order to generally solve the problem of bounding
box for a shape, this is what we need.
We have a plane with equation Ax + By + Cz + D = 0. We have the unit circle,
with equation x^2 + y^2 + z^2 = 1. We want to find the points (x,y,z)
satisfying both equations with the maximum z and minimum z values. There
should be zero, one, or two of these.
I've tried a number of things; the technique that looks like it has the best
chance of success at the moment is the technique of Lagrangian multipliers.
See http://en.wikipedia.org/wiki/Lagrange_multiplier . I think this would
basically apply with:
{code}
g(x,y) = x^2 + y^2 + [-(A/C)x - (B/C)y - (D/C)]^2 - 1
= [(A^2/C^2)x^2 + (B^2/C^2)y^2 + (D^2/C^2) + (2AB/C^2)xy + (2AD/C^2)x
+ (2BD/C^2)y] + x^2 + y^2 - 1
= [1+A^2/C^2] x^2 + [1+B^2/C^2] y^2 + [(D^2/C^2)-1] + (2AB/C^2)xy +
(2AD/C^2)x + (2BD/C^2)y
f(x,y) = -(A/C)x - (B/C)y - (D/C)
{code}
But it's been quite a while since my multivariable calculus days. Anyone want
a nice math challenge? E.g. Mike McCandless? ;-)
> Include geo3d package, along with Lucene integration to make it useful
> ----------------------------------------------------------------------
>
> Key: LUCENE-6196
> URL: https://issues.apache.org/jira/browse/LUCENE-6196
> Project: Lucene - Core
> Issue Type: New Feature
> Components: modules/spatial
> Reporter: Karl Wright
> Assignee: David Smiley
> Attachments: ShapeImpl.java, geo3d.zip
>
>
> I would like to explore contributing a geo3d package to Lucene. This can be
> used in conjunction with Lucene search, both for generating geohashes (via
> spatial4j) for complex geographic shapes, as well as limiting results
> resulting from those queries to those results within the exact shape in
> highly performant ways.
> The package uses 3d planar geometry to do its magic, which basically limits
> computation necessary to determine membership (once a shape has been
> initialized, of course) to only multiplications and additions, which makes it
> feasible to construct a performant BoostSource-based filter for geographic
> shapes. The math is somewhat more involved when generating geohashes, but is
> still more than fast enough to do a good job.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
