[
https://issues.apache.org/jira/browse/LUCENE-7239?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15252821#comment-15252821
]
Karl Wright commented on LUCENE-7239:
-------------------------------------
So here's a quick brain-dump of the geo3d technology, which may help. First,
the basic component of membership is what's called a "sided plane", which is a
single plane where one side of the plane is in-set and the other side is
out-of-set. Being on the plane is considered in-set. This is computed with an
inherent level of accuracy, e.g. anything within a perpendicular distance of
epsilon from the plane is considered to sit on the plane. This is also
extremely fast: three multiplications, two additions, and a comparison. The
second technology is finding intersections of two planes on the surface of the
ellipsoid. Since planes intersect along a line, there is also some requirement
of "membership", which is typically a set of sided planes that the intersection
point must lie within. Slightly less fast but still pretty good; there's a
square root involved but otherwise its comparable to sided plane computation.
This is also how we detect intersections between edges. Finally, there's the
ability to find the bounds of any plane's intersection with the ellipsoid.
That's useful but considerably slower and less accurate.
All of the geo3d shapes are built using these technologies. For polygons,
though, because the inherent limitation of sided planes that go through the
center of the ellipsoid is that they describe 1/2 of the ellipsoid, we can only
effectively build convex or concave polygons, where concave polygons are just
the complement of a convex polygon. The current code therefore breaks an
arbitrary messy polygon down into a set of convex and concave polygon tiles
that are well-behaved.
The problem is that for polygons that have lots of edges, even after you
construct a tiled representation, all queries about relationships/intersection
and membership are O(N). This would have to become O(log(N)) to be practical.
In addition, the borough data has very closely spaced points that are
essentially co-linear as far as geo3d is concerned: if you construct a plane
with any two adjacent borough points you have a pretty good chance that the
adjacent points on either side also sit on the plane. So, unless some cleaning
up is done, sided planes are useless for the borough polygons. I've worked,
therefore, on the cleanup problem, and (I think) solved it, but it still
doesn't fix the O(N) issue.
Now, we could do the following kind of thing instead: build edges from simple
planes (not sided planes), and use only plane intersection to compute
membership. Then, there would be a chance of ordering planes hierarchically to
acheive O(log(N)) time. But, two caveats: (1) don't know how to do the
ordering yet, and (2) there may be similar numerical issues with computing
intersections for very short edges.
Anyhow, let's keep kicking these ideas around.
> Speed up LatLonPoint's polygon queries when there are many vertices
> -------------------------------------------------------------------
>
> Key: LUCENE-7239
> URL: https://issues.apache.org/jira/browse/LUCENE-7239
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Robert Muir
> Attachments: LUCENE-7239.patch
>
>
> This is inspired by the "reliability and numerical stability" recommendations
> at the end of http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf.
> Basically our polys need to answer two questions that are slow today:
> contains(point)
> crosses(rectangle)
> Both of these ops only care about a subset of edges: the ones overlapping a y
> interval range. We can organize these edges in an interval tree to be
> practical and speed things up a lot. Worst case is still O(n) but those
> solutions are more complex to do.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
