Unexpected triangulation results

[djhoese]

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.

• There are three collinear points.
• There is a repeated point in the middle.
• Traversing the points in the given order creates a polygon with no area.

Here's some code that should cause the assertion:

from vispy.geometry import PolygonData
data = np.array([
        [4, 4],
        [3, 4],
        [1, 4],
        [4, 4],
        [1, 2],
])
vertices, triangles = PolygonData(vertices=data).triangulate()

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 https://github.com/vispy/vispy/issues/1847#issuecomment-958181091

[djhoese]

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.

[andy-sweet]

Thanks for creating a separate issue for this @djhoese.

I created PR #2248 and described some of my thoughts about those changes. I hope the tests can help clarify what the expected behavior of triangulation.