Индексация в равносторонней треугольной сетке с учетом простых двумерных декартовых координат

Question

У меня есть равносторонняя треугольная сетка, построенная так:

Теперь, учитывая, что исходной точкой 2D-координаты является красная точка в самом нижнем левом углу изображения, мне нужно найти индекс в этой треугольной сетке.

С учетом входных данных : координаты X и Y для интересующей точки (с плавающей точкой), длины и высоты стороны треугольника

Нужен вывод : X и Y индекс треугольника. (примерные индексы на рисунке)

Получение координаты Y (строки) треугольника просто, поскольку это просто целочисленная часть (GivenY / TRIANGLE_HEIGHT), но я не могу обойтись, чтобы вычислить необходимую координату X без выполнения большинства операций.

Answer 1

Вот более четкий ответ для людей, имеющих проблемы (или слишком ленивые), чтобы выяснить геометрию.

Сначала масштабируйте ваши координаты на удобной основе

vec2 pos=(input-origin)/vec2(edge/2,median);

Разделите ваши координаты на целые и дробные части

int x=pos.x, y=pos.y; float u=pos.x-x, v=pos.y-y;

Проверка диагонали (x, y разной четности) или антидиагональной кромки (x, y одинаковой четности)

if(x%2 ^ y%2) { if(v+u<1) x--; } else { if(v-u>0) x--; }

Вот и все (x, y) теперь ваш индекс лица.

Поиск индекса вершины для каждой грани немного сложнее.

У вас есть четыре случая. Вот список индексов вершин CCW для каждой грани:

face  vertices
xy    xy xy xy
00 -> 00 10 01
10 -> 11 01 10
01 -> 01 12 02
11 -> 12 01 11

Шаблон легче увидеть, если вы не добавите 1 к индексам вершин y, поэтому ваша финальная таблица:

00 -> 00 10 01
10 -> 11 01 10
01 -> 00 11 01
11 -> 11 00 10

Каждый столбец соответственно: x, x,! X, x ^ y, x,! X. Кроме того, вы можете просто использовать справочную таблицу.

Он работает с произвольными индексами лица, вам просто нужно добавить (x / 2, y) и выполнить поиск (x% 2, y% 2).

В итоге индексы вершин треугольника:

x/2 + x%2, y + x%2; x/2 + !(x%2), y + (x%2^y%2); x/2 + (x%2), y + !(x%2)

с координатами вершины в исходном декартовом пространстве:

origin+vec2(2*x+y%2),y)*vec2(edge/2,median)

Answer 2

больше треугольников Если вы рисуете линию от нижнего левого 0,0, до верхнего правого от 1,0, затененные два треугольника теперь состоят из четырех прямоугольных треугольников. Опустив линию вниз от правого верхнего угла 1,0, вы получите еще один прямоугольный треугольник, а треугольник, состоящий из трех прямоугольных треугольников. Высота - это исходная высота треугольника, ширина 1,5 * длина треугольника, гипотенуза. Я оставляю для упражнения для класс. Итак, находится ли он в левом или правом треугольнике, где ваша точка пересекает эту линию. Вы можете заранее определить большую часть этого, основываясь на длине треугольника. Другой вариант - выстроить параллелограмм, вычислить его центр, переместить его в начало координат, повернуть на 30 градусов по часовой стрелке, переместиться назад, выполнить предварительное вычисление преобразования, у вас есть ромб с шириной вышеупомянутого гипотенузы, какая сторона середины которого является какой треугольник, высота ромба равна длине треугольника, вам все равно нужно будет работать, или параллелограмм, так как 1,0 и 2,0 будут перекрываться.