[
https://issues.apache.org/jira/browse/LUCENE-7241?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15256410#comment-15256410
]
Karl Wright commented on LUCENE-7241:
-------------------------------------
I've made good progress with this over the weekend. The intersects() code is
complete, although the performance improvements we can expect from it will
depend critically on the bounds of the plane we choose to intersect with.
Luckily, in the XYZSolid case, those edges all have at least one tiny
dimension, so we should get good results by choosing the right tree to traverse.
The crossing logic, while complicated for the case of crossings that are edge
endpoints, is also done. Some work needed to happen to create new basic
functionality in Plane to support this logic, but it is all reasonably
straightforward. There's still some potential for issues arising from
numerical problems in this logic, although I've tried to use computations that
are robust in this way. We'll see.
The last bit of logic we need is finding a path from the test point to the
incoming point (for isWithin()). This path should ideally proceed solely in
x-z, y-z, or x-y. It's therefore likely that a two-step path will be needed.
There is also logic that will be necessary to deal with the case where the
intersection of the two legs of the path happens to sit on an edge. This is
rare but luckily we know that being on an edge is always considered "in-set",
so we can use that to save ourselves in that case.
> Improve performance of geo3d for polygons with very large numbers of points
> ---------------------------------------------------------------------------
>
> Key: LUCENE-7241
> URL: https://issues.apache.org/jira/browse/LUCENE-7241
> Project: Lucene - Core
> Issue Type: Improvement
> Components: modules/spatial3d
> Affects Versions: master
> Reporter: Karl Wright
> Assignee: Karl Wright
>
> This ticket corresponds to LUCENE-7239, except it's for geo3d polygons.
> The trick here is to organize edges by some criteria, e.g. z value range, and
> use that to avoid needing to go through all edges and/or tile large irregular
> polygons. Then we use the ability to quickly determine intersections to
> figure out whether a point is within the polygon, or not.
> The current way geo3d polygons are constructed involves finding a single
> point, or "pole", which all polygon points circle. This point is known to be
> either "in" or "out" based on the direction of the points. So we have one
> place of "truth" on the globe that is known at polygon setup time.
> If edges are organized by z value, where the z values for an edge are
> computed by the standard way of computing bounds for a plane, then we can
> readily organize edges into a tree structure such that it is easy to find all
> edges we need to check for a given z value. Then, we merely need to compute
> how many intersections to consider as we navigate from the "truth" point to
> the point being tested. In practice, this means both having a tree that is
> organized by z, and a tree organized by (x,y), since we need to navigate in
> both directions. But then we can cheaply count the number of intersections,
> and once we do that, we know whether our point is "in" or "out".
> The other performance improvement we need is whether a given plane intersects
> the polygon within provided bounds. This can be done using the same two
> trees (z and (x,y)), by virtue of picking which tree to use based on the
> plane's minimum bounds in z or (x,y). And, in practice, we might well use
> three trees: one in x, one in y, and one in z, which would mean we didn't
> have to compute longitudes ever.
> An implementation like this trades off the cost of finding point membership
> in near O\(log\(n)) time vs. the extra expense per step of finding that
> membership. Setup of the query is O\(n) in this scheme, rather than O\(n^2)
> in the current implementation, but once again each individual step is more
> expensive. Therefore I would expect we'd want to use the current
> implementation for simpler polygons and this sort of implementation for
> tougher polygons. Choosing which to use is a topic for another ticket.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
