[jira] [Commented] (LUCENE-10470) Unable to Tessellate polygon
[ https://issues.apache.org/jira/browse/LUCENE-10470?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17561368#comment-17561368 ] ASF subversion and git services commented on LUCENE-10470: -- Commit 41ffac45b49dfc9e4ed6979c95ca9a8c14617a54 in lucene-solr's branch refs/heads/branch_8_11 from Ignacio Vera [ https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=41ffac45b49 ] LUCENE-10470: [Tessellator] Fix some failing polygons due to collinear edges (#756) (#2665) Check if polygon has been successfully tessellated before we fail (we are failing some valid tessellations) and allow filtering edges that fold on top of the previous one > Unable to Tessellate polygon > > > Key: LUCENE-10470 > URL: https://issues.apache.org/jira/browse/LUCENE-10470 > Project: Lucene - Core > Issue Type: Bug > Components: core/index >Affects Versions: 9.0 >Reporter: Yixun Xu >Assignee: Ignacio Vera >Priority: Major > Fix For: 9.2 > > Attachments: image-2022-03-16-18-12-43-411.png, > image-2022-03-31-16-06-33-051.png, image-2022-04-04-17-33-52-454.png, > image-2022-04-04-17-34-41-971.png, polygon2.geojson, polygon3.geojson, > vertices-latest-lucene.txt, vertices-lucene-820.txt > > Time Spent: 2h 50m > Remaining Estimate: 0h > > I have a polygon that causes {{Tessellator.tessellate}} to throw an "Unable > to Tessellate shape" error. I tried several versions of Lucene, and the issue > does not happen with Lucene 8.2.0, but seems to happen with all Lucene > versions >=8.3.0, including the latest main branch. > I created a branch that reproduces the issue: > [https://github.com/apache/lucene/compare/main...yixunx:yx/reproduce-tessellator-error?expand=1] > This is the polygon rendered on geojson.io: > !image-2022-03-16-18-12-43-411.png|width=379,height=234! > Is this a bug in the Tesselator logic, or is there anything wrong with this > polygon that maybe wasn't caught by Lucene 8.2.0? -- This message was sent by Atlassian Jira (v8.20.10#820010) - To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
[jira] [Commented] (LUCENE-10470) Unable to Tessellate polygon
[ https://issues.apache.org/jira/browse/LUCENE-10470?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17561362#comment-17561362 ] ASF subversion and git services commented on LUCENE-10470: -- Commit 4f67eabb3c08501d4691beee731f8f7dba1262f0 in lucene-solr's branch refs/heads/LUCENE-10470 from Ignacio Vera [ https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=4f67eabb3c0 ] LUCENE-10470: [Tessellator] Fix some failing polygons due to collinear edges (#756) Check if polygon has been successfully tessellated before we fail (we are failing some valid tessellations) and allow filtering edges that fold on top of the previous one # Conflicts: # lucene/CHANGES.txt # lucene/core/src/java/org/apache/lucene/geo/Tessellator.java # lucene/core/src/test/org/apache/lucene/geo/TestTessellator.java # lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470-2.geojson.gz # lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470-3.geojson.gz # lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470.geojson.gz # lucene/test-framework/src/resources/org/apache/lucene/geo/lucene-10470.wkt.gz > Unable to Tessellate polygon > > > Key: LUCENE-10470 > URL: https://issues.apache.org/jira/browse/LUCENE-10470 > Project: Lucene - Core > Issue Type: Bug > Components: core/index >Affects Versions: 9.0 >Reporter: Yixun Xu >Assignee: Ignacio Vera >Priority: Major > Fix For: 9.2 > > Attachments: image-2022-03-16-18-12-43-411.png, > image-2022-03-31-16-06-33-051.png, image-2022-04-04-17-33-52-454.png, > image-2022-04-04-17-34-41-971.png, polygon2.geojson, polygon3.geojson, > vertices-latest-lucene.txt, vertices-lucene-820.txt > > Time Spent: 2.5h > Remaining Estimate: 0h > > I have a polygon that causes {{Tessellator.tessellate}} to throw an "Unable > to Tessellate shape" error. I tried several versions of Lucene, and the issue > does not happen with Lucene 8.2.0, but seems to happen with all Lucene > versions >=8.3.0, including the latest main branch. > I created a branch that reproduces the issue: > [https://github.com/apache/lucene/compare/main...yixunx:yx/reproduce-tessellator-error?expand=1] > This is the polygon rendered on geojson.io: > !image-2022-03-16-18-12-43-411.png|width=379,height=234! > Is this a bug in the Tesselator logic, or is there anything wrong with this > polygon that maybe wasn't caught by Lucene 8.2.0? -- This message was sent by Atlassian Jira (v8.20.10#820010) - To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
[jira] [Commented] (LUCENE-10470) Unable to Tessellate polygon
[ https://issues.apache.org/jira/browse/LUCENE-10470?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17528640#comment-17528640 ] ASF subversion and git services commented on LUCENE-10470: -- Commit 78ad4f7fa6b9da0d0ad1d96c4824f330a30a75b6 in lucene's branch refs/heads/branch_9x from Ignacio Vera [ https://gitbox.apache.org/repos/asf?p=lucene.git;h=78ad4f7fa6b ] LUCENE-10470: [Tessellator] Fix some failing polygons due to collinear edges (#756) Check if polygon has been successfully tessellated before we fail (we are failing some valid tessellations) and allow filtering edges that fold on top of the previous one > Unable to Tessellate polygon > > > Key: LUCENE-10470 > URL: https://issues.apache.org/jira/browse/LUCENE-10470 > Project: Lucene - Core > Issue Type: Bug > Components: core/index >Affects Versions: 9.0 >Reporter: Yixun Xu >Priority: Major > Attachments: image-2022-03-16-18-12-43-411.png, > image-2022-03-31-16-06-33-051.png, image-2022-04-04-17-33-52-454.png, > image-2022-04-04-17-34-41-971.png, polygon2.geojson, polygon3.geojson, > vertices-latest-lucene.txt, vertices-lucene-820.txt > > Time Spent: 2h 20m > Remaining Estimate: 0h > > I have a polygon that causes {{Tessellator.tessellate}} to throw an "Unable > to Tessellate shape" error. I tried several versions of Lucene, and the issue > does not happen with Lucene 8.2.0, but seems to happen with all Lucene > versions >=8.3.0, including the latest main branch. > I created a branch that reproduces the issue: > [https://github.com/apache/lucene/compare/main...yixunx:yx/reproduce-tessellator-error?expand=1] > This is the polygon rendered on geojson.io: > !image-2022-03-16-18-12-43-411.png|width=379,height=234! > Is this a bug in the Tesselator logic, or is there anything wrong with this > polygon that maybe wasn't caught by Lucene 8.2.0? -- This message was sent by Atlassian Jira (v8.20.7#820007) - To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
[jira] [Commented] (LUCENE-10470) Unable to Tessellate polygon
[ https://issues.apache.org/jira/browse/LUCENE-10470?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17528637#comment-17528637 ] ASF subversion and git services commented on LUCENE-10470: -- Commit 5d3ab09676a90bb143be711d568782cbec06fb4d in lucene's branch refs/heads/main from Ignacio Vera [ https://gitbox.apache.org/repos/asf?p=lucene.git;h=5d3ab09676a ] LUCENE-10470: [Tessellator] Fix some failing polygons due to collinear edges (#756) Check if polygon has been successfully tessellated before we fail (we are failing some valid tessellations) and allow filtering edges that fold on top of the previous one > Unable to Tessellate polygon > > > Key: LUCENE-10470 > URL: https://issues.apache.org/jira/browse/LUCENE-10470 > Project: Lucene - Core > Issue Type: Bug > Components: core/index >Affects Versions: 9.0 >Reporter: Yixun Xu >Priority: Major > Attachments: image-2022-03-16-18-12-43-411.png, > image-2022-03-31-16-06-33-051.png, image-2022-04-04-17-33-52-454.png, > image-2022-04-04-17-34-41-971.png, polygon2.geojson, polygon3.geojson, > vertices-latest-lucene.txt, vertices-lucene-820.txt > > Time Spent: 2h 20m > Remaining Estimate: 0h > > I have a polygon that causes {{Tessellator.tessellate}} to throw an "Unable > to Tessellate shape" error. I tried several versions of Lucene, and the issue > does not happen with Lucene 8.2.0, but seems to happen with all Lucene > versions >=8.3.0, including the latest main branch. > I created a branch that reproduces the issue: > [https://github.com/apache/lucene/compare/main...yixunx:yx/reproduce-tessellator-error?expand=1] > This is the polygon rendered on geojson.io: > !image-2022-03-16-18-12-43-411.png|width=379,height=234! > Is this a bug in the Tesselator logic, or is there anything wrong with this > polygon that maybe wasn't caught by Lucene 8.2.0? -- This message was sent by Atlassian Jira (v8.20.7#820007) - To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
[jira] [Commented] (LUCENE-10470) Unable to Tessellate polygon
[ https://issues.apache.org/jira/browse/LUCENE-10470?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17517128#comment-17517128 ] Yixun Xu commented on LUCENE-10470: --- [~ivera] Here is another shape that still fails after the latest fix: [^polygon3.geojson] Similar to the first one I reported, this shape can be tessellated with Lucene 8.2.0, but fails with Lucene >= 8.3.0, including the main branch and the branch of [https://github.com/apache/lucene/pull/756.] > Unable to Tessellate polygon > > > Key: LUCENE-10470 > URL: https://issues.apache.org/jira/browse/LUCENE-10470 > Project: Lucene - Core > Issue Type: Bug > Components: core/index >Affects Versions: 9.0 >Reporter: Yixun Xu >Priority: Major > Attachments: image-2022-03-16-18-12-43-411.png, > image-2022-03-31-16-06-33-051.png, polygon2.geojson, polygon3.geojson, > vertices-latest-lucene.txt, vertices-lucene-820.txt > > Time Spent: 50m > Remaining Estimate: 0h > > I have a polygon that causes {{Tessellator.tessellate}} to throw an "Unable > to Tessellate shape" error. I tried several versions of Lucene, and the issue > does not happen with Lucene 8.2.0, but seems to happen with all Lucene > versions >=8.3.0, including the latest main branch. > I created a branch that reproduces the issue: > [https://github.com/apache/lucene/compare/main...yixunx:yx/reproduce-tessellator-error?expand=1] > This is the polygon rendered on geojson.io: > !image-2022-03-16-18-12-43-411.png|width=379,height=234! > Is this a bug in the Tesselator logic, or is there anything wrong with this > polygon that maybe wasn't caught by Lucene 8.2.0? -- This message was sent by Atlassian Jira (v8.20.1#820001) - To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
[jira] [Commented] (LUCENE-10470) Unable to Tessellate polygon
[ https://issues.apache.org/jira/browse/LUCENE-10470?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17515567#comment-17515567 ] Yixun Xu commented on LUCENE-10470: --- As mentioned in Github comment I ran into another error after picking up the fixes. Here is the geojson that reproduces the error [^polygon2.geojson] And the rendered shape: !image-2022-03-31-16-06-33-051.png|width=410,height=379! > Unable to Tessellate polygon > > > Key: LUCENE-10470 > URL: https://issues.apache.org/jira/browse/LUCENE-10470 > Project: Lucene - Core > Issue Type: Bug > Components: core/index >Affects Versions: 9.0 >Reporter: Yixun Xu >Priority: Major > Attachments: image-2022-03-16-18-12-43-411.png, > image-2022-03-31-16-06-33-051.png, polygon2.geojson, > vertices-latest-lucene.txt, vertices-lucene-820.txt > > Time Spent: 20m > Remaining Estimate: 0h > > I have a polygon that causes {{Tessellator.tessellate}} to throw an "Unable > to Tessellate shape" error. I tried several versions of Lucene, and the issue > does not happen with Lucene 8.2.0, but seems to happen with all Lucene > versions >=8.3.0, including the latest main branch. > I created a branch that reproduces the issue: > [https://github.com/apache/lucene/compare/main...yixunx:yx/reproduce-tessellator-error?expand=1] > This is the polygon rendered on geojson.io: > !image-2022-03-16-18-12-43-411.png|width=379,height=234! > Is this a bug in the Tesselator logic, or is there anything wrong with this > polygon that maybe wasn't caught by Lucene 8.2.0? -- This message was sent by Atlassian Jira (v8.20.1#820001) - To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
[jira] [Commented] (LUCENE-10470) Unable to Tessellate polygon
[ https://issues.apache.org/jira/browse/LUCENE-10470?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17509783#comment-17509783 ] Ignacio Vera commented on LUCENE-10470: --- Thanks [~yixunx] fro reporting. Indeed this is a bug and your analysis sounds correct. This reminded me to another issue (LUCENE-9580) where collinearity was happening when splitting polygons. I think the fix is similar, we need to prevent creating collinear lines when isNextEdgeFromPolygon flag is different between edges. I open a PR (attached in the ticket) with the fix. > Unable to Tessellate polygon > > > Key: LUCENE-10470 > URL: https://issues.apache.org/jira/browse/LUCENE-10470 > Project: Lucene - Core > Issue Type: Bug > Components: core/index >Affects Versions: 9.0 >Reporter: Yixun Xu >Priority: Major > Attachments: image-2022-03-16-18-12-43-411.png, > vertices-latest-lucene.txt, vertices-lucene-820.txt > > Time Spent: 10m > Remaining Estimate: 0h > > I have a polygon that causes {{Tessellator.tessellate}} to throw an "Unable > to Tessellate shape" error. I tried several versions of Lucene, and the issue > does not happen with Lucene 8.2.0, but seems to happen with all Lucene > versions >=8.3.0, including the latest main branch. > I created a branch that reproduces the issue: > [https://github.com/apache/lucene/compare/main...yixunx:yx/reproduce-tessellator-error?expand=1] > This is the polygon rendered on geojson.io: > !image-2022-03-16-18-12-43-411.png|width=379,height=234! > Is this a bug in the Tesselator logic, or is there anything wrong with this > polygon that maybe wasn't caught by Lucene 8.2.0? -- This message was sent by Atlassian Jira (v8.20.1#820001) - To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
[jira] [Commented] (LUCENE-10470) Unable to Tessellate polygon
[ https://issues.apache.org/jira/browse/LUCENE-10470?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17509596#comment-17509596 ] Yixun Xu commented on LUCENE-10470: --- Looks like it's due to the changes to the \{{filterPoints}} logic in [this PR]([https://github.com/apache/lucene-solr/pull/771/files#diff-d56e36a4e0e7183471b2982cc1127c678f2a414280a21064b3da1e293cead562R920).] I printed the linked list of vertices before the call to [earcutLinkedList|[https://github.com/apache/lucene/blob/a4b30b4cf4c0c9b4de0c27893ea2350af498b1c0/lucene/core/src/java/org/apache/lucene/geo/Tessellator.java#L134],] and the list contains some sets of 3 or more colinear vertices where the middle vertex was not removed by \{{filterPoints}} due to the check on \{{isNextEdgeFromPolygon}}. If I filter those middle vertices out then the tessellation can finish successfully. I think the colinear vertices were probably introduced when \{{eliminateHoles}} added edges to connect the holes with the outer polygon, and some added edges happened to be colinear with an existing edge on the outer polygon (you can see from the visualization that some vertices on the holes share the same latitude as vertices on the outer polygon). I'm not sure what's the best way to fix it yet, will need to look a bit more into how the isNextEdgeFromPolygon flag is being set and used. > Unable to Tessellate polygon > > > Key: LUCENE-10470 > URL: https://issues.apache.org/jira/browse/LUCENE-10470 > Project: Lucene - Core > Issue Type: Bug > Components: core/index >Affects Versions: 9.0 >Reporter: Yixun Xu >Priority: Major > Attachments: image-2022-03-16-18-12-43-411.png > > > I have a polygon that causes {{Tessellator.tessellate}} to throw an "Unable > to Tessellate shape" error. I tried several versions of Lucene, and the issue > does not happen with Lucene 8.2.0, but seems to happen with all Lucene > versions >=8.3.0, including the latest main branch. > I created a branch that reproduces the issue: > [https://github.com/apache/lucene/compare/main...yixunx:yx/reproduce-tessellator-error?expand=1] > This is the polygon rendered on geojson.io: > !image-2022-03-16-18-12-43-411.png|width=379,height=234! > Is this a bug in the Tesselator logic, or is there anything wrong with this > polygon that maybe wasn't caught by Lucene 8.2.0? -- This message was sent by Atlassian Jira (v8.20.1#820001) - To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org