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

Question

У меня есть триангулированная изометрическая сетка, например:
_{(источник: mathforum.org )}

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

Answer 2

Это похоже на то, что сказал Клэтус, но я полагаю, что это другой взгляд на это.

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

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

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

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

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

Если i - единичный вектор вдоль x, а j - ортогональный вдоль y, то имеем

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

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

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

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

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

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

Предположим, что x и y положительны.

Теперь, если c = [x '], целая часть x'

и r = [y '], целая часть y'

тогда в (угловой) сетке точка лежит в c-м столбце и в r-й строке. (Считайте вправо и вверх и начинайте считать с 0).

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

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

Теперь, чтобы узнать, в каком треугольнике он находится, вы можете рассмотреть дробные части x 'и y'.

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

Теперь

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

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