You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by GitBox <gi...@apache.org> on 2022/09/15 14:56:46 UTC
[GitHub] [lucene] llermaly opened a new issue, #11776: Non self intersecting polygons can't be indexed
llermaly opened a new issue, #11776:
URL: https://github.com/apache/lucene/issues/11776
### Description
The following polygons are valid, but considered self intersecting by Lucene :
```
POLYGON ((8.8970989818779 54.4134906575883, 8.90042774485873 54.4146874897743, 8.90594809529893 54.4171621281855, 8.91004327482905 54.4202335124536, 8.90936000005425 54.4216600000818, 8.9234299997357 54.4292900002006, 8.8925999997461 54.4125699999037, 8.88701999937444 54.4128200006828, 8.88024999984759 54.4117399999775, 8.87049000011837 54.407389999926, 8.85725999978773 54.4065399997888, 8.8324600004316 54.4108700007071, 8.83028999859022 54.4107799999813, 8.83010999956348 54.4097399998029, 8.83542087096422 54.4081201758963, 8.8434158599249 54.4059310703591, 8.8498879933749 54.4038371457592, 8.85426620240666 54.4029805394939, 8.85731191163137 54.4032660762063, 8.86483100908713 54.4043130389967, 8.87230838608615 54.4060266046257, 8.88148723601366 54.4091671397265, 8.88577026584612 54.4101189229804, 8.89195686439317 54.4116417778086, 8.8970989818779 54.4134906575883))
POLYGON ((7.89437024403906 47.5862590252318, 7.89312177803361 47.5869704801294, 7.89281574806746 47.5870946189537, 7.89525097569983 47.5857177586665, 7.89806367361792 47.5841274339808, 7.90068804512661 47.5825559862467, 7.89998956367071 47.5830121477752, 7.89515885167079 47.585809621127, 7.89437024403906 47.5862590252318))
POLYGON ((11.0774300000168 54.2984399992536, 11.0827805841396 54.2829539912519, 11.0830386027471 54.2818703102967, 11.0832788032709 54.2797565892852, 11.0832799998269 54.2798199998029, 11.0830099985918 54.2822900002149, 11.0774300000168 54.2984399992536))
```
@craigtaverner made some research and noted the following :
_all have a feature in common, a very narrow constriction, causing one side of the polygon to touch (almost) the other side. This is likely the source of the issue, and in-line with your theory regarding numerical errors._
_I've just written tests for these polygons in the latest version of lucene, and all three fail triangulation (a necessary step for indexing the polygons). So this is, I believe, the lucene tessellator (triangulator) code not being able to handle these points being so close to the other edge of the polygon._
_I think it is the indexing that is failing, since triangulation is only needed for indexing, So until you import it to the index, it is fine. I was reading the code in this area, and found an interesting comment about it not including some special floating point tricks to be more accurate. So it could be that we just have to implement those tricks. I saw a link to this page which might cover those needs. https://www.cs.cmu.edu/~quake/robust.html_
### Version and environment details
_No response_
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org