vispy / vispy / 12913396666

75%

push

github

Ignore all flat triangles in triangulation (#2248)

This partially fixes #2247. By ignoring flat/zero-area triangles (i.e.
where all three points are collinear), we avoid the assertion failure
associated with overwriting the entry in `_edges_lookup`. But there is
still an unexpected triangle and vertex in the output.

I added a few simple and similar tests to capture what I expect from the
output, and where the behavior breaks down. Before the change both
`test_triangulate_collinear_path` and
`test_triangulate_collinear_path_with_repeat` fail with the assertion
failure. After the change, only
`test_triangulate_collinear_path_with_repeat` fails, not due to the
assertion, but because a triangle is found, which also contains a vertex
that is not in the input - instead I would expect no triangles to be
returned.

I think this PR represents a small improvement from `main` for two
reasons.
1. The original assertion failure makes me think that the triangulation
algorithm assumed that it would never see duplicate edges based on the
way it was implemented (i.e. the state is not just exceptional, it
should be impossible). This PR prevents one way of reaching that state.
2. Before this change there was an implementation comment `# ignore flat
tris`, which suggested that the `_add_tri` was trying to skip zero-area
triangles. But the implementation only ignored triangles with at least 2
points that have duplicate coordinates. This PR adds a proper check for
that condition.

However, I have some reservations about this PR in its current state.
- I'm not exactly sure what to expect from the output of triangulation.
It looks like we always get some vertices that weren't in the input, but
in most cases they are not actually used in any of the output triangles,
so that seems fine (as reflected by the tests).
- It doesn't fix all the issues described in #2247 (i.e. there is still
an unexpected triangle and vertex).
- It does a little re... (continued)

5801 of 10530 branches covered (55.09%)

44 of 45 new or added lines in 2 files covered. (97.78%)

24017 of 32111 relevant lines covered (74.79%)

2.45 hits per line