[jira] [Created] (LUCENE-8615) Can LatLonShape's tessellator create more search-efficient triangles?

["Adrien Grand (JIRA)" <ji...@apache.org>]

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: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org