-
Notifications
You must be signed in to change notification settings - Fork 618
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Unexpected triangulation results #2247
Comments
A PR might be a good starting point to more easily understand the tests and changes you're suggesting. Thanks. I don't know enough about what should be allowed or not allowed but it seems odd to me to allow a closed loop polygon that is colinear. I wouldn't expect results to make much sense. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I came here via a napari issue, where we run into the same assertion failure (e.g.
assert (c, b) not in self._edges_lookup
) mentioned here and in #1948.@sofroniewn found a small collection of 2D points that seems to reproduce the issue. That example is extra-degenerate for a few reasons.
Here's some code that should cause the assertion:
And here's a diagram of those points (and their order) just to clarify:
The napari issue also describes a variant of the example where one of the collinear points is slightly perturbed to avoid the assertion failure, but the output includes some extra vertices and triangles that we don't expect.
I pushed a branch up to my fork of vispy that includes some test cases that cover above and some simpler examples. I'm unsure if my test assertions are correct because I'm not sure if the triangulated vertices are allowed to include extras.
That branch also includes a fix that prevents the assertion failure mentioned here (but not the unexpected output vertices) by ignoring "flat" triangles that are formed from 3 collinear points (i.e. a zero area triangles). There is some existing code that seemed to attempt that based on an implementation comment, but only captured a specific case where at least two points have equal coordinates. Let me know if you think it's worth turning that into a PR - I'd be happy to do that.
In general, the Python triangulation implementation seems to have a few quirks and maybe even some missing parts. I also couldn't easily find access to the paper mentioned in the docstring. Therefore, it might be worth reconsidering a dependency to handle triangulation rather than maintaining this code:
shapely
could be a good option as previously mentioned and @nclack (also on napari) mentioned considering earcut-like algorithms (I think there are a few Python implementations of that).Also, let me know if I should create a separate issue to track this!
Originally posted by @andy-sweet in #1847 (comment)
The text was updated successfully, but these errors were encountered: