Я пытаюсь написать алгоритм для триангуляции двумерной выборки точек сетки. Идея аналогична триангуляции Делоне, но с несколькими пользовательскими правилами.
Для представления вершин и их координат входными данными является разреженный двумерный массив нулей и единиц. Данный элемент равен 1, если это вершина, и 0, если нет. Таким образом, в основном, если это 1, это означает, что точка была выбрана, и триангуляция должна включить ее в триангуляцию; если это 0, он не должен участвовать в триангуляции.
1) В отличие от Делоне, в моем случае все треугольники должны быть прямоугольными с горизонтальной или вертикальной ориентацией, например:
0 0 0 0
0 1 0 1
0 1 0 0
имеет прямоугольный треугольник, который можно составить, соединив единицы. И он имеет вертикальную/горизонтальную ориентацию, поскольку 2 ребра, не являющиеся гипотенузами, горизонтальны и вертикальны.
2) Никакие 2 треугольника не могут иметь общую гипотенузу, но это нормально, если они имеют общее ребро, которое не является гипотенузой.
3) Никакая вершина не может быть вершиной прямоугольного треугольника, а также не вершиной другого прямоугольного треугольника. Другими словами,
0 1 0
0 (1) 1
0 1 0
это нормально, потому что центральная точка a, отмеченная внутри a (), является вершиной обоих прямоугольных треугольников. Но в следующем случае:
0 0 0 1 1
1 0 0 1 1
было бы нормально сделать:
0 0 0 X B
A 0 0 A B
что означает 2 треугольника (AAX и BBX), но следующее не допускается:
0 0 0 A B
A 0 0 X B
так как теперь вершина «X» будет вершиной в треугольнике A, но не будет вершиной в треугольнике B.
Меня интересуют любые мысли/схемы разработки этого алгоритма. Матрицы довольно большие, но очень разреженные, поэтому алгоритм не должен быть слишком эффективным; любой концептуально простой подход должен работать нормально. На выходе должен быть список списков:
[[(x1a,y1a),(x1b,y1b),(x1c,y1c)], [(x2a,y2a),(x2b,y2b),(x2c,y2c)], ..., [(xNa,yNa),(xNb,yNb),(xNc,yNc)]]
для координат 3 вершин всех N различных треугольников.
