Определите развернутые сетчатые УФ области

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

Создание графика

Сделайте идентификаторы для вершин и граней (пронумеруйте их). Но убедитесь, что одни и те же вершины получают одинаковые идентификаторы, сравните их по УФ или положению.

Создать вектор: std::vector<int> vertexToFace;

vertexToFace[i]==j означает, что i-я вершина находится на лице j.

Тогда две вершины являются соседями, если они находятся на одной грани.

Затем создайте std::vector<std::forward_list<int> > graph; Сохраните вершины как векторный индекс и добавьте соседей. (O (n ^ 2) сложность)

Чтобы сделать это, вы должны взять i-ую вершину, и для каждого j вам нужно проверить погоду, они на одном лице. Немного оптимизированная версия:

for(int i=0; i<n; ++i) for(int j=i+1; j <n ++j)
if (vertexToFace[i] == vertexToFace[j])
{
graph[i].push_front(j);
graph[j].push_front(i);
}

Это O (n ^ 2), но его легко реализовать. Тяжелее, но быстрее требуется еще один вектор: std::vector<std::array<int,3>> faceToVertex;Таким образом, из i-й вершины вы можете получить доступ к ее соседям в постоянное время. В любом случае, мы построили график, в котором мы ищем подключенные компоненты, что легко с поиск в глубину.

Реализация алгоритма связанных компонентов

Чтобы реализовать это, вы должны сделать еще один вектор: std::vector<bool> visited(n,false);, и еще один std::vector<int> component(n), Решение вашей проблемы будет в этом последнем.

Алгоритм прост, начать с вершины 0 и установить visited[0] = true; а также component[0]=0;, Затем для каждого невидимого соседа сделайте точно так же, как и для соседа i (некоторый элемент forward_list) if (!visited[i]) component[i] = 0;затем сделайте то же самое. Он останавливается, когда все элементы компонента становятся посещенными. Итак, вам нужно найти не посещенный элемент и повторить вышеописанное, но знать, что вы делаете компонент 1 и так далее. Пример:

int l, k=0;
while(l!=n)
{
l=0;
while(visited[l]) l++;
fill_from(graph, visited, component, l, k);
++k;
}

Я думаю, вы поняли, так что: (псевдокод)

void fill_from(graph, visited, component, l, k)
{
if(visited[l]) return;
component[l] = k;
for(auto &i : graph[l])
fill_from(graph,visited,component,i,k);
}

Тогда мы закончили с задачей, но это еще не самое быстрое решение.

Более быстрый алгоритм

Чтобы получить еще быстрее, мы должны избавиться от рекурсии, и нам не нужен график впоследствии, используйте std::forward_list<int> для стека. Вставьте первую вершину в стек. Затем вытолкните одну вершину, установите ее компонент на k. От себя все его соседи в стек, затем удалите соседей. Другими словами, добавьте список соседей в стек (очень быстрая операция). Повторяйте до тех пор, пока стек не станет пустым.

Таким образом, мы не будем делать бесконечный цикл, потому что если мы вернемся к той же вершине, у нее не будет соседей, и мы уже посетили их. Поэтому нет необходимости в посещаемом векторе. Мы можем установить элемент вектора компонента несколько раз, но всегда на одно и то же значение, так зачем проверять его?

Однако, если у нас нет посещенного вектора, тогда будет сложнее искать другую вершину, которую мы не посетили. Хотя мы могли бы искать некоторую вершину в графе, у которой все еще есть соседи, есть лучшее решение.

Создайте std::set<int> notvisited(); Для тех точек, которые еще не посещены. Сначала он должен содержать все идентификаторы вершин, а затем каждый раз, когда мы устанавливаем идентификатор компонента, мы пытаемся удалить вершину из notvisited задавать. Мы повторяем получение вершины из набора и запускаем алгоритм fill_from (), пока набор не станет пустым, в то же время у нас будут все идентификаторы компонентов.

ОБНОВЛЕНИЕ: Использование обновленной информации о том, как хранится сетка.

Если у вас нет равных элементов в «списке вершин» (зачем вам), то индекс вершины — это ее позиция в массиве. Таким образом, идентификаторы для вершин сделаны.

Идентификаторы для треугольников или граней находятся в «списке индексов», позвольте мне назвать этот массив int listOfIndices[];для j-й грани связанные с ним вершины listOfIndices[3*j + 0], listOfIndices[3*j + 1] а также listOfIndices[3*j + 2], Чтобы сделать первый вектор, вам нужно сделать следующее:

std::vector<int> vertexToFace(num_of_verteces); //previously n
for(int j = 0; j < num_of_faces; ++j)
{
vertexToFace[listOfIndices[3*j + 0]]=j;
vertexToFace[listOfIndices[3*j + 1]]=j;
vertexToFace[listOfIndices[3*j + 2]]=j;
}

(Алгоритм построения обратной зависимости); Обратите внимание, что в этом случае вам даже не нужен другой faceToVertex массив, потому что у вас уже есть (listOfIndices), вы просто должны индексировать его по-разному (делить на 3 каждый раз).