Adrien Grand created LUCENE-8615:
------------------------------------
Summary: Can LatLonShape's tessellator create more
search-efficient triangles?
Key: LUCENE-8615
URL: https://issues.apache.org/jira/browse/LUCENE-8615
Project: Lucene - Core
Issue Type: Improvement
Reporter: Adrien Grand
Attachments: 2-tessellations.png, re-tessellate-triangle.png
The triangular mesh produced by LatLonShape's Tessellator creates reasonable
numbers of triangles, which is helpful for indexing speed. However I'm
wondering that there are conditions when it might be beneficial to run
tessellation slightly differently in order to create triangles that are more
search-friendly. Given that we only index the minimum bounding rectangle for
each triangle, we always check for intersection between the query and the
triangle if the query intersects with the MBR of the triangle. So the smaller
the area of the triangle compared to its MBR, the higher the likeliness to have
false positive when querying.
For instance see the following shape, there are two ways that it can be
tessellated into two triangles. LatLonShape's Tessellator is going to return
either of them depending on which point is listed first in the polygon. Yet the
first one is more efficient that the second one: with the second one, both
triangles have roughly the same MBR (which is also the MBR of the polygon), so
both triangles will need to be checked all the time whenever the query
intersects with this shared MBR. On the other hand, with the first way, both
MBRs are smaller and don't overlap, which makes it more likely that only one
triangle needs to be checked at query time.
!2-tessellations.png!
Another example is the following polygon. It can be tessellated into a single
triangle. Yet at times it might be a better idea create more triangles so that
the overall area of MBRs is smaller and queries are less likely to run into
false positives.
!re-tessellate-triangle.png!
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
