Масштабируемая петля над соседями
Хорошо известно, что если кто-то хочет выстроить квадратную сетку (или матрицу) действительных чисел, он может использовать array с мажорным порядком. Давайте нарисуем окрестность некоторого элемента i:
...................................
...|i-width-1|i-width|i-width+1|...
...| i-1 | i | i+1 |...
...|i+width-1|i+width|i+width+1|...
...................................
Давайте для простоты предположим, что я где-то посередине квадратной сетки, поэтому никаких пограничных проблем. (Мы можем добавить %(width*height) и подключайтесь по сетке границ). Поэтому, если кто-то хочет что-то сделать с каждым элементом в окрестности i-го элемента, он должен сделать:
//function which does something with element at idx
void DoSomethinWithElement(size_t idx);
//left neighbour
DoSomethinWithElement(i-1);
//right neighbour
DoSomethinWithElement(i+1);
//top neighbour
DoSomethinWithElement(i-width);
//bottom neighbour
DoSomethinWithElement(i+width);
Я хочу обобщить этот алгоритм для любой тип правильной многоугольной сетки (то есть треугольник, квадрат, пятиугольник, шестиугольник и т. д.) Обычный означает, что он построен только из одного типа многоугольника (то есть только из треугольников).
Как обобщить для любого типа многоугольной сетки:
1. Расположение другой сетки в массиве?
2. Эти N (для квадратной сетки четыре) операторов в цикле?
Задача «Как найти всех соседей плитки в многоугольной сетке?» решается быстро с помощью графиков. Но я хочу использовать массивы, чтобы я мог скопировать их на видеокарту с помощью CUDA.
Примеры сеток:
Решение
Я хочу обобщить этот алгоритм для любого типа правильной многоугольной сетки (то есть треугольника, квадрата, пятиугольника, шестиугольника и т. Д.)
Ваше определение правильной многоугольной сетки необычно. Как правило, вы не можете вращать или зеркально отображать грани сетки (мозаики), чтобы она считалась правильной. Есть только 3 правильных тайлинга (треугольник, квадрат, шестиугольник). Все пятиугольные наклоны требуют зеркального отражения или вращения или обоих.
Упростим вашу задачу до этого: «Как найти всех соседей лица в многоугольной сетке?» Как только вы выясните это, тривиально вызвать функцию для каждого соседа.
Сетки — это графики с определенными ограничениями. Можно обобщить поиск соседей, представив сетку общим графом. Вершины графа представляют грани, и у них есть ребра к соседям. График сетки является планарный график. Когда сетка представлена графом, возникает проблема: «Если в графе есть вершина, как мне найти все смежные вершины?»
Обратите внимание, что вершины и ребра графа — это не то же самое, что вершины и ребра сетки. Например, вершины сетки шестиугольной сетки имеют три соединенных ребра, в то время как грани имеют шесть соседних граней, и поэтому вершины графа имеют шесть ребер каждая.
Одним из способов представления графиков является список смежности. В этом представлении вам просто нужно посмотреть список смежности вершины, чтобы найти всех ее соседей.
Но я хочу использовать массивы
Хорошо, поскольку размер каждого списка смежности постоянен, они могут быть реализованы с массивами, как в ответе decltype_auto. Или вы можете представить график с помощью матрицы смежности.
Но если вы хотите общий алгоритм для любой табличное представление сетки, тогда я думаю, что вы загнали себя в угол с этим требованием. Каждое представление отличается, и вам понадобится отдельный алгоритм для каждого.
Другие решения
Вы можете представить смежность K-полигональной сетки числа полигонов N с помощью 1D вектора v длины N * K или двумерной матрицы NxK M. Использование std::size_t -1, nullptr или любой другой подходящий тип ссылки, который вы сохранили в v или M, чтобы указать отсутствующих соседей на границе.
Учитывая такую матрицу NxK M:
Для соседей многоугольника n вы выполняете итерацию от M [n] [0] до M [n] [K-1], выбираете соседей по любой ссылке, которую вы сохранили в M, и применяете к ним любую функцию, которую хотите.