You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "Yixun Xu (Jira)" <ji...@apache.org> on 2022/03/21 04:29:00 UTC
[jira] [Comment Edited] (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 edited comment on LUCENE-10470 at 3/21/22, 4:28 AM:
-------------------------------------------------------------
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|#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.
was (Author: JIRAUSER286707):
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-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org