В триангулированной изометрической сетке, какой треугольник является заданной точкой?

Question

У меня есть триангулированная изометрическая сетка, как это:

В моем коде, треугольники группируются по столбцам.

Как я наводил указатель мыши, я хочу рассчитать, какой треугольник находится в координатах мыши. Есть ли простой алгоритм для этого?

Answer 1

Что вы хотите сделать, это превратить это в сетку как можно больше, потому что сетки намного легче работать.

Первое, что вы делаете, это выяснить, в каком столбце он находится. Вы говорите, что сохранили это так, чтобы это было проще, выполнив простое целочисленное деление по координате x по смещению ширины столбца при запуске коробки. Легко.

После этого вы хотите определить, какой треугольник он находится (очевидно). Как вы частично превращаете это в сетку, вы притворяетесь, что у вас есть стопка прямоугольных треугольников вместо стека изометрических треугольников.

Треугольники имеют длину вдоль оси y (сторона колонны). Разделите это число пополам и определите, сколько шагов вам нужно. На основании числа шагов вниз и, если столбец является четным или нечетным сообщит вам, если вы смотрите на:

+--------+ 
|-_  | 
| -_ | 
| -_ | 
|  -_| 
+--------+ 

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

У вас есть несколько вариантов для этого.

1. Вы можете использовать что-то вроде линейного алгоритма Брешенема, чтобы растрировать гипотенузу и когда вы попадаете в столбец, в котором вы работаете, если вы находитесь выше или ниже этой линии;
2. Потому что здесь у вас есть только две возможные решетки (одна из них обращена к другой, так что это действительно только одна). Вы можете сохранить массив значений строк, указав, что для столбца 3 гипотенуза находится в смещении 2, тогда как для 6 она равна 4 и так далее.

Вы можете использовать (1) для генерации (2) для быстрого поиска.

Единственное, что нужно учитывать, это то, что происходит, если курсор мыши находится на краю?

Answer 2

Это похоже на то, что сказал cletus, но по-другому взглянуть на него, я полагаю.

Я предполагаю, что стороны треугольника равен 1.

Предположим, у вас есть сетки, как показано ниже:

 y' 
    /
    /__/__/__/__/__/__/ 
    /__/__/__/__/__/__/ 
    /__/__/__/__/__/__/____ x' 
(0,0) 

Если рассматривать сетки в системе координат, в которой оси у х & находятся под углом 60 градусов, точка, координата которой в угловой системе (x ', y') будет соответствовать координате в ортогональной системе (с тем же началом и общим направлением осей) до (x, y) ,

В вашей задаче вам заданы (x, y), нам нужно найти (x ', y'), а затем вычислить треугольник.

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

x'* i + y'(i/2 + sqrt(3) * j /2) = xi + yj. 

(В основном единичный вектор вдоль «под углом» у оси я/2 + SQRT (3)/2 * j. Единичный вектор вдоль оси x совпадает с нормальной осью х, т. Е. I).

Таким образом

x' + y'/2 = x 
y' * sqrt(3)/2 = y 

Решение дает:

y' = 2*y/sqrt(3) 
x' = x - y/sqrt(3) 

Предположим теперь, что х 'и у' положительны.

Теперь, если с = [х «], целая часть х»

и г = [у «], целая часть у»

затем в (угловой) сетке, тем точка лежит в c-й колонке и r-й строке. (Подсчитывание вправо и вверх и начало отсчета на 0).

Таким образом, мы сузили точку параллелограмма

 ____ 
     /\ */ 
    /___\/ 
    (c,r) 

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

{x} = x' - [x'] = x' - c. 
{y} = y' - [y'] = y' - r. 

Теперь

если {x} + {y} > 1, то точка лежит в треугольнике, отмеченные *. , если {x} + {y} < 1, то точка лежит в другом треугольнике. , если {x} + {y} = 1, то точка лежит на линии, общей для двух треугольников.

Надеюсь, что это поможет.