Алгоритм маркировки края треугольной сетки

Question

Алгоритм маркировки края треугольной сетки

Введение
В рамках более крупной программы (связанной с визуализацией объемной графики), У меня есть небольшая, но сложная подзадача, в которой произвольная (но конечная) треугольная 2D-сетка должна быть помечена определенным образом. Уже некоторое время назад я написал решение (см. Ниже), которое было достаточно хорошим для тестовых сеток, которые у меня были в то время, хотя я понимал, что этот подход, вероятно, не будет работать очень хорошо для каждой возможной сетки, о которой можно было подумать. Теперь я наконец столкнулся с сеткой, для которой настоящее решение не работает так хорошо, и похоже, что я должен предложить совершенно другой подход. К сожалению, мне кажется, что я не могу полностью изменить свое мышление, поэтому я подумал, что спрошу здесь.

Проблема

Рассмотрим картинку ниже. (Цвета не являются частью проблемы; я просто добавил их, чтобы улучшить (?) Визуализацию. Кроме того, различная ширина кромки является совершенно несущественным артефактом.)

Для каждого треугольника (например, оранжевого ABC и зеленого ABD) каждому из трех ребер нужно присвоить одну из двух меток, например «0» или « 1 ". Есть всего два требования:

Не все стороны треугольника могут иметь одинаковую метку. Другими словами, для каждого треугольника должно быть два «0» и одна «1», или , две «1» и один «0».
Если ребро является общим для двух треугольников , он должен иметь одинаковый ярлык для обоих. Другими словами, если ребро AB на картинке помечено «0» для треугольника ABC, оно должно быть помечено «0» и для ABD.

Сетка является настоящей 2D-сеткой, и она конечна: т.е. , он не оборачивается и имеет четко определенную внешнюю границу. Очевидно, на границе удовлетворить требования довольно легко, но внутри становится все труднее.

Интуитивно кажется, что по крайней мере одно решение всегда должно существовать, хотя я не могу это доказать. (Обычно их несколько - любого из них достаточно.)

Текущее решение

Мое текущее решение является действительно методом грубой силы (предоставлено здесь только для полноты - не стесняйтесь пропустить этот раздел ):

Обычно этот подход находит решение всего за пару итераций, но недавно я столкнулся с сеткой, для которой алгоритм имеет тенденцию завершаться только после одной или двух тысяч повторных попыток ... Что, очевидно, предполагает, что может быть сети, для которых он никогда не завершается.

Теперь, Я бы хотел иметь детерминированный алгоритм, который гарантированно всегда найдет решение. Вычислительная сложность не является такой большой проблемой, потому что сетки не очень большие, и маркировка в основном должна выполняться только при загрузке новой сетки, что не происходит постоянно - поэтому алгоритм с (например) экспоненциальным сложность должна быть в порядке, пока она работает. (Но, конечно: чем эффективнее, тем лучше.)