Чередование триангуляции на квадратной решетке
У меня есть массив точек в Python, делающий квадратную решетку. Я хочу триангулировать это так: 
так что фигурные скобки чередуются в шахматном порядке от квадрата к квадрату. Мои попытки были основаны на деформации до триангуляции. Например, сдвиг решетки перед триангуляцией через
xy_skew = np.dstack((xypts[:,0]+ 0.1*xypts[:,1], xypts[:,1]))[0]
tri = scipy.spatial.Delaunay(xy_skew)
TRI = tri.vertices
может дать мне все "правые" диагонали или все "левые" диагонали, но я не нашел деформации, которая могла бы привести к желаемой триангуляции.
Как я могу сделать это эффективно (для решеток ~ миллионов точек)?
Если это уместно, индексы моих очков сначала растут в Y, а затем в X.
Спасибо!