Введение
В рамках более крупной программы (связанной с рендерингом объемной графики) у меня есть небольшая, но сложная подзадача, в которой произвольная (но конечная) треугольная двумерная сетка должна быть помечена определенным образом. Некоторое время назад я написал решение (см. Ниже), которое было достаточно для тестовых сеток, которые у меня были в то время, хотя я понял, что этот подход, вероятно, не будет работать очень хорошо для каждой возможной сетки, о которой можно подумать. Теперь я наконец-то столкнулся с сеткой, для которой настоящее решение работает не так хорошо, и, похоже, мне следует придумать совершенно другой подход. К сожалению, мне кажется, что я не могу восстановить свои взгляды, поэтому я решил спросить здесь.
Проблема
Рассмотрите картинку ниже. (Цвета не являются частью проблемы; я просто добавил их, чтобы улучшить (?) Визуализацию. Кроме того, изменяющаяся ширина кромки - совершенно не относящийся к делу артефакт.)
Для каждого треугольника (например, оранжевой ABC и зеленой ABD) каждому из трех ребер должна быть присвоена одна из двух меток, скажем «0» или «1». Есть только два требования:
- Не все края треугольника могут иметь одинаковую метку. Другими словами, для каждого треугольника должно быть два «0» и один «1», или , два «1» и один «0».
- Если ребро разделено двумя треугольниками, оно должно иметь одинаковую метку для обоих. Другими словами, если ребро AB на рисунке помечено «0» для треугольника ABC, оно должно быть помечено и «0» для ABD.
Сетка является подлинной 2D, и она конечна: то есть она не оборачивается и имеет четко определенную внешнюю границу. Очевидно, что на границе довольно легко удовлетворить требования - но это становится сложнее внутри.
Интуитивно понятно, что, по крайней мере, одно решение должно существовать всегда, хотя я не могу это доказать. (Обычно их несколько - достаточно одного).
Текущее решение
Мое текущее решение действительно очень грубое (здесь приведено только для полноты - не стесняйтесь пропустить этот раздел ):
- Ведение четырех наборов треугольников - по одному для каждого возможного количества (0..3) ребер, оставшихся для маркировки. В начале каждый треугольник находится в наборе, где остаются три ребра для маркировки.
- Пока существуют треугольники с немаркированными ребрами:
Найдите наименьшее ненулевое число нераспределенных ребер, для которых еще остались треугольники. Другими словами: в любой момент времени мы стараемся свести к минимуму количество треугольников, для которых маркировка была частично завершена. Число оставшихся ребер будет в диапазоне от 1 до 3. Затем просто выберите один такой треугольник с этим конкретным количеством оставшихся ребер, которые нужно выделить. Для этого треугольника сделайте следующее:
- Проверьте, не наложена ли маркировка какого-либо оставшегося ребра на маркировку какого-либо другого треугольника. Если это так, присвойте ярлыки, как подразумевается в требовании № 2 выше.
- Если это приводит к тупику (т. Е. Требование № 1 больше не может быть удовлетворено для текущего треугольника), тогда начинается весь процесс с самого начала .
- Выделите все оставшиеся ребра следующим образом:
- Если до сих пор не было помечено ни одного ребра, назначьте первое случайным образом.
- Когда одно ребро уже выделено, назначьте второе, чтобы оно имело противоположную метку.
- Когда выделены два ребра: если они имеют одинаковую метку, назначьте третьему ребру противоположную метку (очевидно); если два имеют разные метки, назначьте третий случайным образом.
- Обновите наборы треугольников для различного количества нераспределенных ребер.
- Если мы когда-нибудь попадем сюда, у нас есть решение - ура!
Обычно этот подход находит решение всего за пару итераций, но недавно я столкнулся с сеткой, для которой алгоритм имеет тенденцию завершаться только после одной или двух тысяч попыток ... Что, очевидно, предполагает, чтомогут быть ячейки, для которых никогда не заканчивается.
Теперь я хотел бы иметь детерминированный алгоритм, который гарантированно всегда найдет решение.Сложность вычислений не такая большая проблема, потому что сетки не очень большие, и маркировка в основном должна выполняться только при загрузке новой сетки, что не происходит постоянно - так что алгоритм с (например) экспоненциальнойсложность должна быть в порядке, пока она работает.(Но, конечно: чем эффективнее, тем лучше.)
Спасибо, что прочитали это далеко.Теперь любая помощь будет принята с благодарностью!
Редактировать: Результаты, основанные на предложенных решениях
К сожалению, я не могу заставить подход, предложенный Диалектиком , работать.Может быть, я не правильно понял ... Во всяком случае, рассмотрим следующую сетку с начальной точкой, обозначенной зеленой точкой: 
Давайте немного увеличим масштаб ... 
Теперь давайте запустим алгоритм.После первого шага маркировка выглядит следующим образом (красный = "помеченные пути", синий = "окруженные пути"): 
Пока все хорошо.После второго шага: 
И третьего: 
... четвертого: 
Но теперь у нас проблема!Давайте сделаем еще один раунд - но, пожалуйста, обратите внимание на треугольник, нанесенный пурпурным цветом: 
Согласно моей текущей реализации, все края пурпурного треугольника находятся на кольцевой траектории, поэтому они должны быть синего цвета - что эффективно делает этоконтрпример.Теперь, может быть, я как-то ошибся ... Но в любом случае два ребра, которые находятся ближе всего к начальному узлу, очевидно, не могут быть красного цвета;а если третий помечен красным, то кажется, что решение на самом деле больше не соответствует идее.
Кстати, вот данные, используемые .Каждая строка представляет одно ребро, и столбцы должны интерпретироваться следующим образом:
- Индекс первого узла
- Индекс второго узла
- x координата первого узла
- y координата первого узла
- x координата второго узла
- y координата второго узла
Начальный узел - это узел с индексом 1.
Полагаю, что в следующий раз я должен попробовать метод, предложенный Рафалем Доугирдом ... Но, возможно, мне следует какое-то время сделать совсем другое:)