You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Karl Wright (JIRA)" <ji...@apache.org> on 2016/04/10 15:04:25 UTC
[jira] [Resolved] (LUCENE-7199) Improve algorithm for randomly
finding an interior point for Geo3D polygons
[ https://issues.apache.org/jira/browse/LUCENE-7199?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Karl Wright resolved LUCENE-7199.
---------------------------------
Resolution: Fixed
Fix Version/s: 6.x
master
Committed a change to address this. For most polygons, a correct pole is now chosen in between 1 and 5 iterations. Some rare ones need up to 23 iterations. Still, far better than before, which sometimes went through 500 iterations to find the pole.
[~mikemccand], if you are so inclined, it would be great to perf test the polygon non-pre-built query case again to see if this made a substantial difference.
> Improve algorithm for randomly finding an interior point for Geo3D polygons
> ---------------------------------------------------------------------------
>
> Key: LUCENE-7199
> URL: https://issues.apache.org/jira/browse/LUCENE-7199
> Project: Lucene - Core
> Issue Type: Improvement
> Components: modules/spatial3d
> Affects Versions: master
> Reporter: Karl Wright
> Assignee: Karl Wright
> Fix For: master, 6.x
>
>
> [~mikemccand]'s benchmark for polygon search shows that constructing Geo3D polygon queries is quite expensive compared to other technologies. My belief is that this is due largely to how an interior point for determination of clockwise/counterclockwise are found: this is currently searched for randomly across the entire globe.
> I suspect that we could replace this algorithm with a random algorithm that uses one of the polygon's edge points and looks randomly within a small distance of that point. This would greatly reduce the number of failed attempts to find a "pole" (as I call it).
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org