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

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

Проблема

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

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

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

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

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

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

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

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

Спасибо, что прочитали это. Теперь любая помощь будет принята с благодарностью!

Изменить: результаты, основанные на предлагаемых решениях

К сожалению, я не могу получить подход, предложенный Dialecticus для работы. Может быть, я не понял это правильно. Во всяком случае, рассмотрим следующую сетку, с начальной точкой, обозначенной зеленой точкой:

Позвольте немного увеличить масштаб...

Теперь давайте запустим алгоритм. После первого шага маркировка выглядит следующим образом (red = "starred paths", blue = "ringed paths" ):

Все идет нормально. После второго шага:

И третье:

... четвертый:

Но теперь у нас есть проблема! Позвольте сделать еще один раунд, но обратите внимание на треугольник, нанесенный на пурпурный цвет:

Согласно моей текущей реализации, все края пурпурного треугольника находятся на кольцевом пути, поэтому они должны быть синими, что эффективно делает это контрпримером. Теперь, может быть, я как-то ошибся... Но в любом случае два края, которые ближе всего к началу node, очевидно, не могут быть красными; и если третий помечается красным, то кажется, что решение больше не подходит к идее.

Btw, здесь используются данные. Каждая строка представляет одно ребро, а столбцы должны интерпретироваться следующим образом:

Я предполагаю, что в следующий раз я должен попробовать метод, предложенный Rafał Dowgird... Но, возможно, я должен сделать что-то совершенно другое на некоторое время:)

Ответы

Ответ 1

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

Такой порядок существует и может быть построен следующим образом:

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

Ответ 2

При любом node в сетке сетка может рассматриваться как набор концентрических колец вокруг этого node (например, паутина). Дайте всем ребрам, которые не находятся в кольце (отмеченные пути) значение 0, и дайте всем ребрам, которые находятся в кольце (кольчатые пути) значение 1. Я не могу это доказать, но я уверен, что вы получите правильную маркировку. Каждый треугольник будет иметь ровно одно ребро, которое является частью некоторого кольца.