You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Robert Muir (JIRA)" <ji...@apache.org> on 2016/04/21 22:24:12 UTC
[jira] [Updated] (LUCENE-7239) Speed up LatLonPoint's polygon
queries when there are many vertices
[ https://issues.apache.org/jira/browse/LUCENE-7239?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Robert Muir updated LUCENE-7239:
--------------------------------
Attachment: LUCENE-7239.patch
Here is a patch for the sandbox. Ultimately, I think we should just yank the slower polygon support out of Polygon.java, make it a pure holder class. Feels wrong to do stuff like this when e.g. spatial3d does not care.
But for now lets improve it here.
Synthetic polygons from luceneUtil
||vertices||old QPS||new QPS|
|5|24.4|38.4|
|50|21.7|29.7|
|500|14.4|27.5|
|5000|3.3|18.8|
Real polygons (33 london districts: http://data.london.gov.uk/2011-boundary-files)
||vertices||old QPS||new QPS|
|avg 5.6k|8.6|73.0|
Since relations are much faster, startup cost is reduced substantially: e.g. for those real polygons it drops from 85ms to 3ms. We keep our grid for now (its still a decent speedup and now has a cheap cost). Less complex polygons get a nice speedup too since we are less trappy and the two-phase iteration doesn't buy us stuff anymore (similar to distance case).
> 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: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org