#algorithm #graph #graphics #geometry #computational-geometry
#алгоритм #График #графика #геометрия #вычислительная геометрия
Вопрос:
У меня есть примерно плоская сетка, для которой я хотел бы найти контур. Чтобы найти контур, я перебираю все треугольники сетки и подсчитываю количество вхождений каждого ребра (представленного неупорядоченной парой вершин).
После изучения всех треугольников, есть только два возможных значения для каждого ребра.
- количество ребер = 1 : ребро принадлежит одному треугольнику и поэтому является внешним ребром
- количество ребер = 2: ребро разделяется между двумя треугольниками, и поэтому оно является внутренней границей
Ребра, принадлежащие одному треугольнику (количество ребер = 1), определяют контур сетки.
Эта стратегия работает довольно хорошо, если бы не проблема, которую я попытаюсь проиллюстрировать на примере. Предположим, мы хотим найти контур следующей сетки.
Если мы применим стратегию, описанную выше, к этой сетке, она найдет семь ребер, которые определяют контур, т.е. (0,1), (1,4), (4,7), (6,7), (5,6), (2,5) и (0,2) — но он также найдет три внутренних ребра, т.Е. (2,3), (3,4) и (2,4), которые принадлежат только одному треугольнику каждый, соответственно (2,3,6), (3,4,7) и (0,2,4).
Я подумал о следующем решении для решения проблемы. Насколько я могу судить, проблема может возникнуть только тогда, когда есть три вершины, которые лежат на одной линии, как в примере выше. Два коротких ребра, которые соединяют три вершины, могут быть заменены одним более длинным ребром, которое соединяет две внешние вершины. Это новое ребро добавляется в список ребер, или, если оно уже присутствует, его счетчик будет увеличен на единицу, достигнув значения 2. Повторяя процедуру (следуя пути, определяемому ребрами), я должен упростить список ребер, и, наконец, только те, которые находятся на контуре сетки, должны иметь значение 1.
Что вы думаете о моем подходе? Спасибо.
Комментарии:
1. Самое простое решение imo — составить список из n-угольников с общими ребрами, тогда общее ребро, к которому прикреплен только 1 n-угольник, является пограничным ребром. Просто используйте n-угольники вместо треугольников.
2. Это одна из причин, по которой многие люди пытаются избегать таких т-образных переходов. Вы ограничены имеющейся сеткой или можете ее изменить (либо введя квадратики, как предложил @ Flutterish, либо разделив треугольник)?
Ответ №1:
Конфигурация 2-3-4 является «патологической», поскольку она нарушает структуру графа. Фактически, это можно рассматривать как треугольное отверстие в сетке.
Возможный способ обработки — перечислить все отдельные ребра, определить те, которые перекрываются, и игнорировать их.