[jira] [Updated] (LUCENE-7241) Improve performance of geo3d for polygons with very large numbers of points
[ https://issues.apache.org/jira/browse/LUCENE-7241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Karl Wright updated LUCENE-7241: Attachment: LUCENE-7241.patch Debugged and partly tested patch. Had to rework the tree structure due to massive oversight on my part, and also had some confusion about picking the right path. Seems to work for basic polygons now though. > 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 > Attachments: LUCENE-7241.patch, LUCENE-7241.patch, LUCENE-7241.patch, > LUCENE-7241.patch, LUCENE-7241.patch > > > 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: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org
[jira] [Updated] (LUCENE-7241) Improve performance of geo3d for polygons with very large numbers of points
[ https://issues.apache.org/jira/browse/LUCENE-7241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Karl Wright updated LUCENE-7241: Attachment: LUCENE-7241.patch Latest patch. Logic is complete; not yet tested, and we have a small problem of implementing hashCode(), equals(), toString() for these polygons, which could have 1,000,000+ edges... > 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 > Attachments: LUCENE-7241.patch, LUCENE-7241.patch, LUCENE-7241.patch, > LUCENE-7241.patch > > > 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: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org
[jira] [Updated] (LUCENE-7241) Improve performance of geo3d for polygons with very large numbers of points
[ https://issues.apache.org/jira/browse/LUCENE-7241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Karl Wright updated LUCENE-7241: Attachment: LUCENE-7241.patch Once more, attaching code for safekeeping. This implements the tie-in to GeoPolygonFactory. The new method, makeLargeGeoPolygon, has characteristics which make it quite distinct from the current makeGeoPolygon methods, which is why there's a separate factory method and not just a heuristic at this level to choose the best. These are listed in the javadoc for it, but summarized quickly here: (1) No error checking; polygons are assumed to be properly constructed; (2) Very short edges are supported which are essentially coplanar with adjoining edges; (3) Algorithm is optimized for very large polygons ( > 100 sides); What this has in common with the standard polygon implementation is: (1) Computing the bounds of the shape remains expensive (O(N)); (2) Computing the outside distance to the shape remains expensive (O(N)). > 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 > Attachments: LUCENE-7241.patch, LUCENE-7241.patch, LUCENE-7241.patch > > > 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: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org
[jira] [Updated] (LUCENE-7241) Improve performance of geo3d for polygons with very large numbers of points
[ https://issues.apache.org/jira/browse/LUCENE-7241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Karl Wright updated LUCENE-7241: Attachment: LUCENE-7241.patch Another patch for safekeeping. Finally now we have everything in place for dealing effectively with the intersection point between the path legs, but I still need to write the actual logic. > 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 > Attachments: LUCENE-7241.patch, LUCENE-7241.patch > > > 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: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org
[jira] [Updated] (LUCENE-7241) Improve performance of geo3d for polygons with very large numbers of points
[ https://issues.apache.org/jira/browse/LUCENE-7241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Karl Wright updated LUCENE-7241: Attachment: LUCENE-7241.patch Attaching the current changes for safekeeping... > 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 > Attachments: LUCENE-7241.patch > > > 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: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org
[jira] [Updated] (LUCENE-7241) Improve performance of geo3d for polygons with very large numbers of points
[ https://issues.apache.org/jira/browse/LUCENE-7241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Karl Wright updated LUCENE-7241: Description: 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. was: 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. > Improve performance of geo3d for polygons with very large numbers of points > --- > > Key: LUCENE-7241 > URL:
[jira] [Updated] (LUCENE-7241) Improve performance of geo3d for polygons with very large numbers of points
[ https://issues.apache.org/jira/browse/LUCENE-7241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Karl Wright updated LUCENE-7241: Description: 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. was: 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. > Improve performance of geo3d for polygons with very large numbers of points > --- > > Key: LUCENE-7241 > URL:
[jira] [Updated] (LUCENE-7241) Improve performance of geo3d for polygons with very large numbers of points
[ https://issues.apache.org/jira/browse/LUCENE-7241?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Karl Wright updated LUCENE-7241: Description: 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. was: This ticket corresponds to the 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. > Improve performance of geo3d for polygons with very large numbers of points > --- > > Key: LUCENE-7241 > URL: