На самом деле ваш вопрос состоит из трех частей, а не двух:
- Какие структуры данных следует использовать для представления сетки?
- Какой алгоритм следует использовать для извлечения ребер из структур данных сетки?
- Как должен быть представлен результирующий набор ребер?
Вы должны задать дополнительные вопросы, чтобы найти соответствующие ответы.
Какие структуры данных следует использовать для представления сетки?
Какие типы элементов вам нужно обрабатывать?
Если вам нужно обрабатывать только многоугольники (замкнутые циклы) и симплициалы (каждый узел связан с каждым другим узлом в элементе, таким как тетраэдр), тогда упорядоченный список узлов достаточен, поскольку из списка могут быть выведены ребра узлов. Если, с другой стороны, вам нужно обрабатывать типы элементов, такие как шестигранники, призмы или общие многогранники, вам потребуется дополнительная информация о топологии элементов. Простого массива отображений ребер часто бывает достаточно. Это просто массив [] [2] индексов в списке узлов элемента, который говорит вам, как соединить точки для данного типа элемента.
Полуголовая структура, описанная Крисом, является хорошим выбором только для 2D. В 3D может быть произвольное количество элементов, прикрепленных к каждому ребру, а не только два. Существует трехмерное расширение для представления половинного ребра, которое, я думаю, называется структурой вертушки.
Если вам нужно поддерживать произвольные типы элементов, я предпочитаю более полную структуру данных для представления топологии элементов. Распространенным вариантом является использование ребер и ребер. Существует структура ребер для каждой пары соединенных узлов, а также ребро для каждого использования этого ребра в элементе. Это похоже на подход с вертушкой, но немного более явно.
Какой алгоритм использовать для извлечения ребер из элементов?
Насколько важны скорость или память? Должен ли результат включать каждое ребро один раз на элемент или только один раз, независимо от того, сколько элементов его используют? Имеет ли значение порядок ребер в результате? Имеет ли значение порядок узлов каждого ребра?
Довольно сложно придумать алгоритм для произвольных типов элементов, который будет посещать каждое ребро только один раз. Чтобы гарантировать, что каждое ребро появляется только один раз, вы можете либо отфильтровать результат, либо вы можете быть немного хакерским и оставить бит «посещен» на каждом ребре, чтобы гарантировать, что вы не вставите его в результат дважды.
Как мне представить результаты?
Какое значение имеет то, как я буду использовать результат?
Если вы собираетесь использовать результат в вычислениях, требующих большого объема вычислений, лучшим вариантом может быть большой массив координат. Вы не хотите повторно получать координаты узла снова и снова во время вычислений. Однако, если вы фильтруете результаты для удаления повторяющихся ребер, сравнение координат (6 двойных для пары узлов) не является подходящим способом. Если вы выполняете фильтрацию, сначала создайте список указателей на граничные структуры, затем отфильтруйте дубликаты, а , а затем создайте список координат. Вы также можете использовать этот подход с парами узлов, но тогда вам придется фильтровать оба возможных порядка узлов на ребро, удваивая время, необходимое для фильтрации.
Список указателей на края также полезен, если память важнее, чем производительность. Однако вместо преобразования списка ребер в список координат вы ищите координаты во время расчета. Таким образом, получение координат узла происходит медленнее, но вы избегаете составления огромного списка координат - вы сохраняете один указатель на ребро вместо 6 двойных на ребро.
Многие сетчатые приложения хранят все координаты в большом глобальном массиве, причем каждый узел имеет индекс в массиве. Если это так, вместо преобразования списка ребер в массив координат преобразуйте его в список индексов в глобальный массив координат. Производительность не должна сильно отличаться от локального координатного массива, но без затрат памяти и заполнения.