Блог

У меня есть равносторонняя треугольная сетка, построенная следующим образом:

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

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

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

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

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

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

 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)
  

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