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

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.


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.


---
Migrated from [LUCENE-8615](https://issues.apache.org/jira/browse/LUCENE-8615) by Adrien Grand (@jpountz), updated Jan 17 2020
Attachments: [2-tessellations.png](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-8615/2-tessellations.png), [re-tessellate-triangle.png](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-8615/re-tessellate-triangle.png), [screenshot-1.png](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-8615/screenshot-1.png)

The issue names LatLonShape's Tessellator but no file or test; locate that entry point and inspect its current triangulation behavior alongside the attached examples. Define how search efficiency and correctness will be measured, then confirm the resulting tessellation improves MBR selectivity without changing shape coverage.

Written by the indexing model from the issue text.