Обнаружение групп связанных треугольников

Question

У меня есть сетка, как показано ниже, состоящая из групп связанных треугольников.Я должен обнаружить группы треугольников.Есть ли удобный инструмент или алгоритм для этой работы?Я исследую и боюсь, что может быть такая вещь, о которой я не знаю!

Answer 1

Алгоритм графа может быть использован для поиска ваших «групп связанных треугольников».

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

Ваши «группы соединенных треугольников» будут «Связанными компонентами» в терминологии графа.

Эффективный алгоритм поиска всех связанных компонентов в графике можно увидеть в этом ответе:

https://stackoverflow.com/a/21078752/9147444

, который использует структуру данных Union-Find (также известную как Disjoint-Set)

Answer 2

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

Теперь, чтобы сохранить информацию о том, какие треугольники принадлежат какой группе, вы можете использовать структуру данных union-find (* 1004).* которая имеет почти линейную сложность.