Геометрическая задачка - определить принадлежность точки к треугольнику в гексагоне, Подскажите алгоритм, а то запутался Опции

[syoma]

Народ подскажите пожалуйста, может кто с геометрией на "ты", как проще решить следующую задачу.
Есть правильный шестиугольник разбитый на равносторонние треугольники как на рисунке.

Координаты некоторых точек я указал. Все пляшет от величины а - расстояния от центра до удаленной вершины.
И есть точка с координатами x,y которая находится где-то в гексагоне. Задача - определить, в каком треугольнике 1-24 она находится.
Возможно Вы скажете "просто", но есть ограничения - задача будет решаться на микроконтроллере, поэтому просто "взять тангенс от x/y" и т.д. не получится. Умножать на любое число и делить на константу можно, но корень, тригонометр функции и деление на число - нельзя. Число а - сравнительно медленно измеряемая величина, поэтому от нее корень и деление можно использовать.
Пока есть и работает алгоритм определения треугольников 1-18, но с добавлением внутренних треугольников - проблема.
Вот как я делаю:

Код

%% Quarter calculation and rotation
if X<0
    X=-X;
    Xinv=1;
else
    Xinv=0;
end
if Y<0
    Y=-Y;
    Yinv=1;
else
    Yinv=0;
end


%% Triangle calculation

Xshift=X-a/4;

if (Y<(a*sqrt(3)/4)) %If Y less than half height then point is in triangle 1 or 2
    Yshift=Y+a*sqrt(3)/4;
    if (Yshift>sqrt(3)*Xshift)
        triangle=2;
    else
        triangle=1;
    end
else %otherwise it is in triangles 3, 4 or 5
    Yshift=Y-a*sqrt(3)/4;
    if (Xshift==0)
        triangle=4;
    else
        if (Xshift<0)
            if Yshift>(-sqrt(3))*Xshift
                triangle=4;
            else
                triangle=5;
            end
        else
            if (Yshift>sqrt(3)*Xshift)
                triangle=4;
            else
                triangle=3;
            end
        end
    end
end

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

[Миша Т]

Подобную задачу принадлежности точки треугольника решал следующим образом.
любую точку в плоскости треугольника можно выразить симплексные координаты (a,b,c), как это сделать можно найти почни в люьой книге по МКЭ. Если точка принадлежит треугольнику, то |a|+|b|+|c|=1.

Любопытно. Так, видимо, проще всего.

Вариант реализации:
если (Xa,Ya) (Xb,Yb) (Xc, Yc) --- координаты точек A, B, C, (X,Y) координаты точки, то
a=( (Yb-Yc)*(X-Xc)+(Xc-Xb)*( Y-Yc) )/ ( (Yb-Yc)*(Xa-Xc)+(Xc-Xb)*( Ya-Yc) )
b =( (Yc-Ya)*(X-Xc)+(Xa-Xb)*( Y-Yc) )/ ( (Yb-Yc)*(Xa-Xc)+(Xc-Xb)*( Ya-Yc) )
c = 1 - a - b
условие принадлежности треугольнику a >= 0, b >= 0, c>= 0 (ноль, если оказались на границе).

для ускорения работы программы, можно задать 6 массивов: Xa[24], Ya[24], Xb[24], ... --- координаты вершин треугольника (это, конечно занудно), и массив C[24][4] в котором для каждого из треугольников задать константы:

Код

    for(i=0; i < 24; i++)
    {
        C[i][0]= (Yb[i]-Yc[i])/( (Yb[i]-Yc[i])*(Xa[i]-Xc[i])+(Xc[i]-Xb[i])*( Ya[i]-Yc[i]) );
        C[i][1]= (Xc[i]-Xb[i])/( (Yb[i]-Yc[i])*(Xa[i]-Xc[i])+(Xc[i]-Xb[i])*( Ya[i]-Yc[i]) );
        C[i][2]= (Yc[i]-Ya[i])/( (Yb[i]-Yc[i])*(Xa[i]-Xc[i])+(Xc[i]-Xb[i])*( Ya[i]-Yc[i]) );
        C[i][3]= (Xa[i]-Xb[i])/( (Yb[i]-Yc[i])*(Xa[i]-Xc[i])+(Xc[i]-Xb[i])*( Ya[i]-Yc[i]) );
    }

И в цикле проверить

Код

    i=0;
    do {
        a = C[i][0]*(X-Xc[i])+C[i][1]*(Y-Yc[i]);
        b = C[i][2]*(X-Xc[i])+C[i][3]*(Y-Yc[i]);
        c = 1 - a - b;
        i++;
    }while ( !( (a >= 0) && (b >=0) && (c>=0) ) )
    return i;

PS Исходные коды на С
PPS В арифметике мог лажануться))) (хотя, вряд ли)