Max triangles index exceeds number of vertices

[grgur-palle]

For some sets of vertices and segments, some of the triangle indices exceed the maximum allowed vertex index.

For instance:

import numpy as np
import triangle as tr

bug_arr = np.array(
[[ 0.        ,  0.        ],
 [-0.01054464, -0.11041172],
 [-0.02108927, -0.22082344],
 [-0.03163391, -0.33123515],
 [-0.04217855, -0.44164687],
 [-0.4585519 ,  0.0420809 ],
 [ 0.46661427, -0.04458542],
 [-0.47125578, -0.06724769],
 [ 0.4555808 , -0.15512749],
 [-0.48395965, -0.17657628],
 [ 0.44454733, -0.26566956],
 [-0.05272318, -0.55205859],
 [-0.49666353, -0.28590488],
 [ 0.43351386, -0.37621163],
 [-0.50936741, -0.39523347],
 [ 0.42248039, -0.48675369],
 [-0.06326782, -0.66247031],
 [ 0.41144692, -0.59729576],
 [-0.52207129, -0.50456206],
 [-0.07381246, -0.77288203],
 [ 0.40041345, -0.70783783],
 [-0.53477517, -0.61389065],
 [-0.08435709, -0.88329374],
 [ 0.38937998, -0.81837989],
 [-0.54747904, -0.72321925],
 [-0.8979827 ,  0.08051809],
 [-0.91538909, -0.02677838],
 [ 0.92957895, -0.090486  ],
 [ 0.91547002, -0.20022277],
 [-0.93279549, -0.13407485],
 [ 0.90136109, -0.30995954],
 [-0.95020188, -0.24137132]]
)

bug_segments = np.array(
[[ 8,  1],
 [26, 25],
 [13,  3],
 [ 2,  9],
 [ 5, 25],
 [10,  8],
 [ 1,  5],
 [ 3,  9],
 [ 7,  5],
 [ 6,  0],
 [13, 10],
 [10,  1],
 [ 1,  7],
 [ 2,  1],
 [ 9,  7],
 [ 7, 25],
 [ 6,  5],
 [10,  2],
 [ 0,  5],
 [ 8,  0],
 [ 7, 26],
 [13,  2],
 [ 1,  0],
 [ 3,  2],
 [ 2,  7],
 [ 9, 26]],
dtype=int)

delaunay = tr.triangulate({"vertices":bug_arr, "segments":bug_segments}, "pc")
tri = delaunay["triangles"]

print("Max triangles index {:d} exceeds number of vertices {:d}.".format(np.max(tri.ravel()), bug_arr.shape[0]))

prints "Max triangles index 33 exceeds number of vertices 32." Modifying delaunay["triangles"]
according to delaunay["triangles"] = delaunay["triangles"] % bug_arr.shape[0] appears to solve
this issue. Don't know whether this is an issue with this wrapper or the library itself.

[grgur-palle]

The issues is with the initial data. The two triangles (5,1,0) and (5,6,0) enfroced by the segment constraints are
on the same side of the (5,0) edge, although the triangle (5,6,0) has extremely small angles.

[michaeltrs]

Hi,
I was also surprised by seeing a larger triangle index than the number of vertices, could you elaborate a little further why this is caused by the initial data?
Also, is there a way to avoid getting that behaviour?

[grgur-palle]

Ok, so if you plot the points and the enforced segments:

import matplotlib.pyplot as plt
from matplotlib.collections import LineCollection

enforced_segments = [
    [(bug_arr[bug_segments[n,0],0], bug_arr[bug_segments[n,0],1]),
     (bug_arr[bug_segments[n,1],0], bug_arr[bug_segments[n,1],1])] for n in range(bug_segments.shape[0])]

plt.figure(1)
plt.scatter(bug_arr[:,0], bug_arr[:,1])
lc = LineCollection(enforced_segments, color='k', lw=2)
plt.gca().add_collection(lc)
plt.show()

it seems as if everything is fine, we're just enforcing a bunch of triangles that constitute a proper partial triangularization (= every edge neighbors only two triangles that are on the opposite side of the edge), or at least don't prevent one.

However, if you plot the problematic triangles that I mentioned:

plt.figure(2)

problematic_point_list = [0, 1, 5, 6]
plt.scatter(bug_arr[problematic_point_list,0], bug_arr[problematic_point_list,1])

problematic_triangle1 = [ [(bug_arr[5,0], bug_arr[5,1]), (bug_arr[1,0], bug_arr[1,1])],
                          [(bug_arr[1,0], bug_arr[1,1]), (bug_arr[0,0], bug_arr[0,1])],
                          [(bug_arr[0,0], bug_arr[0,1]), (bug_arr[5,0], bug_arr[5,1])] ]
lc1 = LineCollection(problematic_triangle1, color='r', lw=2)
plt.gca().add_collection(lc1)

problematic_triangle2 = [ [(bug_arr[5,0], bug_arr[5,1]), (bug_arr[6,0], bug_arr[6,1])],
                          [(bug_arr[6,0], bug_arr[6,1]), (bug_arr[0,0], bug_arr[0,1])],
                          [(bug_arr[0,0], bug_arr[0,1]), (bug_arr[5,0], bug_arr[5,1])] ]
lc2 = LineCollection(problematic_triangle2, color='b', lw=2)
plt.gca().add_collection(lc2)

plt.show()

you see that there is a blue triangle that is extremely hard to see (because it has two very small angles that make it look like a line). The red (5, 1, 0) and blue (5, 6, 0) triangles are both on the same side of the edge (5, 0), which must not be the case for a proper triangularization. So the initial data (i.e., the segments that I'm enforcing) already preclude the construction of a proper triangularization.

How to avoid this? Check that the enforced segments do not prevent the construction of a triangularization, I guess. I can imagine simpler examples where segments prevent the construction of a triangularization: e.g., a square in which we're enforcing both diagonals to be segments of a triangularization. In the documentation it should probably be emphasized that tr.triangulate does not do a consistency check on the input.