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

[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

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

[Tanya]

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

Один из вариантов. Рассмотрим приведение в 1-ю четверть.
Находите квадраты расстояния от центров правильных треугольничков до Вашей точки - их всего 7.
Минимум определяет искомое.

[ukpyr]

http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/
http://www.ecse.rpi.edu/Homepages/wrf/Rese...tes/pnpoly.html

[scifi]

Мне кажется, тут нужно перейти от прямоугольного базиса к "косому" (вдоль сторон треугольников) - это простое линейное преобразование координат. В новых координатах задача будет значительно проще: треугольники превратятся в половинки квадратов.

[тау]

Умножаем все по оси Х на sqrt(3). В том числе координату "x" искомой точки.
Получаем систему координат где треугольники превратились в прямоугольные. Приводим все в 1-й квадрант .
Нормализуем размеры фигуры к разрядности вычислений и координаты точки тоже .

Старшие 2 разряда по Х и 1 разряд по Y определяют большой квадрат (например зеленый).
следующие 2 бита после них по одному разряду от Х и Y определяют квадрант внутри зеленого квадрата. При 00 или 11 ответ сразу виден. Иначе повторяем еще по одному разряду, пока те не кончатся .

Сообщение отредактировал тау - Feb 5 2010, 16:44

Эскизы прикрепленных изображений

 

[syoma]

Умножаем все по оси Х на sqrt(3). В том числе координату "x" искомой точки.
Получаем систему координат где треугольники превратились в прямоугольные.
Нормализуем размеры фигуры к разрядности вычислений одновременно с координатой Х.

Этот прикол мне нравится - что-то интересненькое уже вырисовывается.
Но

Иначе повторяем еще по одному разряду, пока те не кончатся

Не подойдет - итерации мне не подходят. Надо чтобы раз и все.

Вот в IEEE нашел статейку, где все предлагают перевести в X'=3*X/2, a Y'=sqrt(3)*Y. Помоему идея та же, но не пойму, что получится.

[тау]

IF-ы ничем не лучше итераций, суть одна. Можете развернуть итерации в IF-ы,
Бэйсик непонятно зачем используете. Тут бы си/асм для быстроты

[Guest_@Ark_*]

Я бы так решил эту задачу: Провел бы через все вершины треугольников горизонтальные и вертикальные линии (горизонтальные уже проведены). В итоге - получится 28 прямоугольников. Принадлежность точки к конкретному прямоугольнику определяется по ее координатам X и Y. Такой прямоугольник всегда делится диагональю на две области, принадлежащие двум треугольникам. Остается определить по специально составленной таблице тип прямоугольника - из частей каких треугольников он состоит, как идет его диагональ и установить расположение точки относительно ее...
P.S. Может, не совсем понятно объяснил, но программно все это можно выполнить с помощью только табличных функций, сложений и сравнений, не пребегая даже к умножению...

[ReAl]

Имеем три системы прямых - горизонтальные, наклонные "левые" и "правые".
Если в каноническое уравнение прямой A*x + B*y + C = 0 подставить координаты конкретной точки (x,y), то по результату A*x + B*y + C можно выяснить, лежит точка на прямой (0), под ней (>0) или над ней (<0).

Для каждой системы прямых можно идти сверху от прямой к прямой и искать смену знака - т.е. искать прямую, "как раз над которой" находится точка. По трём номерам прямых однозначно определяетя где находится точка (ну тм с нулями, конгда точка на прямой - нужно просто решить заранее, как это интерпретировать, вылбется в > или >= при сравнениях с 0).
Например, если взять только "косые" прямые, то определяется "вертикальный" ромб, в котором лежит точка, по горизонтальной прямой выясняется в каком из двух треугольников точка.

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

Ха - как вариант - int(y/шаг) - это номер прямой для горизонтальных линий.
Теперь поворачиваем точку на 60 градусов влево и вправо и для y-ка новой точки так же делением на шаг выясняем номер. Дальше при помощи этих трёх номеров из фикисрованного 3-мерного массива вынимаем номер треугольника.

[ALEKSIU]

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

[Миша Т]

Подобную задачу принадлежности точки треугольника решал следующим образом.
любую точку в плоскости треугольника можно выразить симплексные координаты (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 В арифметике мог лажануться))) (хотя, вряд ли)

[ALEKSIU]

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

Именно так когда-то и делал

[syoma]

Бэйсик непонятно зачем используете. Тут бы си/асм для быстроты

Это не бейсик, а матлаб - я в нем моделирую сперва, а потом переношу на МК. Так можно все проверить а потом быстрее отлаживать.

[тау]

Вот еще проще способ.
координаты X точки модифицируете
X'=X+Y/sqrt(3)
Y'=Y*2/sqrt(3)
или , что то-же самое , если есть куда расти:
X''=X*sqrt(3) +Y
Y'"=Y*2
Образуется наклоненная фигура в прямоугольной системе отсчета, как на рисунке.
Переносите начало системы координат в левый нижний угол фигуры , добавлением (а) к X'' и Y''
Теперь пронормализовать X'' и Y'' к размеру всей фигуры (2*а) относительно новой системы координат
и старшие разряды (по два разряда от X'' и Y'' ) будут определять номер квадратика во всей фигуре ( а не только в четверти)
Останется определить к какому треугольнику внутри квадратика относится точка. Для этого накладываете нулевую маску на 2 старших разряда X'' и Y'' (которые определяли номер квадратика). Оставшиеся величины при сравнении покажут к верхнему (X'' < Y'') или нижнему (X''>Y'') треугольнику относится точка.

Впрочем, этом метод и был предложен scifi

Сообщение отредактировал тау - Feb 6 2010, 21:32

Эскизы прикрепленных изображений

 

[blackfin]

Не подойдет - итерации мне не подходят. Надо чтобы раз и все.

Если нужно, чтобы "раз и все", можно воспользоваться трехмерным массивом:

Код

TRIANGLES[2][4][4] =
{
    {
        { 9,12,13, 0},
        { 8,21,14,15},
        { 0,20,19,16},
        { 0, 0, 2, 1}
    },
    {
        {10,11, 0, 0},
        { 7,22,23, 0},
        { 6, 5,24,17},
        { 0, 4, 3,18}
    }
};

Пусть:

P - точка на плоскости в координатах X,Y.

A - вектор направленный вдоль оси Y и имеющий длину равную 1/H.
B - вектор направленный под углом плюс 30° к оси X и имеющий длину равную 1/H.
C - вектор направленный под углом минус 30° к оси X и имеющий длину равную 1/H.

где, H - высота треугольника равная H = a*cos(30°)/2.

Вычисляем целое значение для трех скалярных произведений:

COMPA = (int)<P,A> = (int)(X*0+Y*(1/H)) = (int)(Y*(2/a)/cos(30°)).
COMPB = (int)<P,B> = (int)(X*cos(30°)*(1/H)+Y*sin(30°)*(1/H)) = (int)(X*(2/a)+Y*(2/a)*tg(30°)).
COMPC = (int)<P,C> = (int)(X*cos(30°)*(1/H)-Y*sin(30°)*(1/H)) = (int)(X*(2/a)-Y*(2/a)*tg(30°)).

Вычисляем значение индексов массива:

INDEXA = COMPA & 1;
INDEXB = COMPB + 2;
INDEXC = COMPC + 2;

Тогда номер треугольника:

N = TRIANGLES[INDEXA][INDEXB][INDEXC].

На Си это можно записать так:

Код

#define a 1.0

TRIANGLES[2][4][4] =
{
    {
        { 9,12,13, 0},
        { 8,21,14,15},
        { 0,20,19,16},
        { 0, 0, 2, 1}
    },
    {
        {10,11, 0, 0},
        { 7,22,23, 0},
        { 6, 5,24,17},
        { 0, 4, 3,18}
    }
};

int
num(double X,double Y)
{
    int COMPA = (int)(Y*(2/a)/cos(30°));
    int COMPB = (int)(X*(2/a)+Y*(2/a)*tg(30°));
    int COMPC = (int)(X*(2/a)-Y*(2/a)*tg(30°));

    int INDEXA = COMPA & 1;
    int INDEXB = COMPB + 2;
    int INDEXC = COMPC + 2;

    return TRIANGLES[INDEXA][INDEXB][INDEXC];
}

[syoma]

Спасибо всем и особенно blackfin.
Ваше решение оказалось самым простым в реализации.
Мне даже не понадобился массив - получившиеся индексы однозначно идентифицируют координаты треугольника - это даже еще лучше. Более того сумма индексов, а именно четность или нечетность определяют куда направлен конкретный треугольник - вверх или вниз - мне это тоже нужно было знать.

[blackfin]

Спасибо всем и особенно blackfin.
Ваше решение оказалось самым простым в реализации.

Решение, на самом деле, предложил ReAl:

Ха - как вариант - int(y/шаг) - это номер прямой для горизонтальных линий.
Теперь поворачиваем точку на 60 градусов влево и вправо и для y-ка новой точки так же делением на шаг выясняем номер. Дальше при помощи этих трёх номеров из фикисрованного 3-мерного массива вынимаем номер треугольника.

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

[scifi]

Заранее извиняюсь за оффтопик.
Просто грустно стало: решаем тут задачки уровня 8-го класса средней школы.
Неужели масштаб деградации так велик?
:-(

[syoma]

Просто грустно стало: решаем тут задачки уровня 8-го класса средней школы.
Неужели масштаб деградации так велик?

Возможно. Просто у меня мозг так устроен - информация которая долго не используется и не нужна по профессии - забывается.
А Вы, наверное, помните всю биологию за 8 класс?

+ Деградация в этой области мне не мешает решать все поставленные задачи. А для этого случая и есть Форум.

[scifi]

А Вы, наверное, помните всю биологию за 8 класс?

Да, помню - с помощью гугла и Википедии :-)

Пардон, я не хотел, чтобы звучало, как личный наезд. Мысль была типа" "Вот раньше - огого! А вот сейчас - не очень..." Про общий упадок в наши времена...

[syoma]

Сорри. Еще раз я.
Вот теперь другой вопрс назрел - а что делать, если исходная точка и соответственно вектор находятся за пределами гексагона? Конкретно как найти координаты x',y' точки которая лежит на заданной прямой в пределах гексагона?
В данный момент я делаю просто ограничение по координате y, а затем вычисляю максимальное значение координаты x по формуле xmax=a - y*(1/sqrt(3)).
Проблема в том, что если координата y обрезается, то я всегда попадаю в точку 1 независимо от того насколько большая координата x, что мне совсем не нравится. Хотелось бы, чтобы алгоритм также выдавал точки 2 и 3 если x намного больше y.
Пардон - последний абзац я и сам вычислю, надо бы точные координаты.

Эскизы прикрепленных изображений

 

[singlskv]

Пардон - последний абзац я и сам вычислю, надо бы точные координаты.

Дык просто же пересечение 2 прямых на плоскости
(0,0) - (x,y) и
точка1 - точка3

[syoma]

Дык просто же пересечение 2 прямых на плоскости
(0,0) - (x,y) и
точка1 - точка3

Это то легко. Только формула для нахождения координат этой точки не очень легкая:

Тут как раз есть деление, которое я делать не могу.

[Tanya]

Тут как раз есть деление, которое я делать не могу.

А Вы думаете, что существует чудесная альтернативная формула, дающая тот же ответ, но без деления?
Если же интересует только с какой стороной пересекается прямая, то это возможно. Вариант - рассмотрите векторные произведения...

[syoma]

А Вы думаете, что существует чудесная альтернативная формула, дающая тот же ответ, но без деления?

Ага. Надеюсь, что что-то проспал по геометрии. Но похоже, что нет.

Если же интересует только с какой стороной пересекается прямая, то это возможно. Вариант - рассмотрите векторные произведения...

Ок. Спасибо, посмотрю.

[syoma]

Блин, единственное что придумал - в цикле уменьшать координаты x,y каждый раз в 2 раза и вычислять попадают они в гексагон или еще нет.
Но, елки-палки, тогда количество итераций неопределенная величина.
По векторным произведениям не нашел применения в моем случае.

[blackfin]

Блин, единственное что придумал - в цикле уменьшать координаты x,y каждый раз в 2 раза и вычислять попадают они в гексагон или еще нет.

Для тех, кто "забыл биологию за 8 класс":

Код

if ((abs(COMPA)<=2)&&(abs(COMPB)<=2)&&(abs(COMPC)<=2)) printf("Inside Hexagone");
else printf("Outside Hexagone");

[syoma]

Для тех, кто "забыл биологию за 8 класс":

Код

if ((abs(COMPA)<=2)&&(abs(COMPB)<=2)&&(abs(COMPC)<=2)) printf("Inside Hexagone");
else printf("Outside Hexagone");

Под словом "вычислять" я понимал именно это. Нужна конкретная точка, желательно на границе, а не условие принадлежности к гексагону.

[blackfin]

Под словом "вычислять" я понимал именно это. Нужна конкретная точка, желательно на границе, а не условие принадлежности к гексагону.

Сформулируйте точнее, что "дано", а что нужно "вычислить"..

[syoma]

Сформулируйте точнее, что "дано", а что нужно "вычислить"..

В этом сообщении я написал, что нужно вычислить.
Даны координаты точки X,Y, которая лежит где-то за пределами гексагона. Надо найти координаты точки X',Y', которая должна находиться в гексагоне, желательно, на границе и которая должна быть как можно ближе или лежать на прямой 0,0 - X,Y.
Пока я пользуюсь обрезками, но они дают совсем искаженный результат.
Я уже думаю, бог с ним - с делением, можно попробовать использовать. То есть если обрезаю одну координату, то скалирую другую, но все равно получается фигня с косыми сторонами, тогда происходит передоз и точка получается внутри гексагона далеко от внешних сторон.

[Tanya]

По векторным произведениям не нашел применения в моем случае.

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

[Tanya]

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

А можно итерациями с наперед заданной точностью найти координаты искомой точки.

[blackfin]

Даны координаты точки X,Y, которая лежит где-то за пределами гексагона. Надо найти координаты точки X',Y', которая должна находиться на границе и которая должна лежать на прямой 0,0 - X,Y.

Три прямых Y = 0; Y = X*tg(60°); Y = -X*tg(60°) разбивают плоскость на шесть равных секторов:

sector0: (X*tg(60°) <= Y)&&(-X*tg(60°) < Y)
sector1: (0 <= Y)&&(Y < X*tg(60°))
sector2: (-X*tg(60°) <= Y)&&(Y < 0)
sector3: (Y <= X*tg(60°))&&(Y < -X*tg(60°))
sector4: (Y <= 0)&&(X*tg(60°) < Y)
sector5: (0 < Y)&&(Y <= -X*tg(60°))

В прежних обозначениях:

находим:

Код

void
scale(double X,double Y,double *X',double *Y')
{
    double PA = (Y*(2/a)/cos(30°)).
    double PB = (X*(2/a)+Y*(2/a)*tg(30°)).
    double PC = (X*(2/a)-Y*(2/a)*tg(30°)).

    double S0;
    double S1;
    double S2;
    double S3;
    double S4;
    double S5;

    if ((2.0 < abs(PA))||(2.0 < abs(PB))||(2.0 < abs(PC)))
    {
        if ((X*tg(60°) <= Y)&&(-X*tg(60°) < Y))
        {S0 = 2.0/PA;  *X' = S0*X; *Y' = S0*Y;}
        else if ((0 <= Y)&&(Y < X*tg(60°)))
        {S1 = 2.0/PB;  *X' = S1*X; *Y' = S1*Y;}
        else if ((-X*tg(60°) <= Y)&&(Y < 0))
        {S2 = 2.0/PC;  *X' = S2*X; *Y' = S2*Y;}
        else if ((Y <= X*tg(60°))&&(Y < -X*tg(60°)))
        {S3 = -2.0/PA; *X' = S3*X; *Y' = S3*Y;}
        else if ((Y <= 0)&&(X*tg(60°) < Y))
        {S4 = -2.0/PB; *X' = S4*X; *Y' = S4*Y;}
        else if ((0 < Y)&&(Y <= -X*tg(60°)))
        {S5 = -2.0/PC; *X' = S5*X; *Y' = S5*Y;}
        else printf("NAN error?");
    }
    return;
}

[syoma]

Спасибо опять blackfin.
Опять упростилось и стало вообще без секторов. Просто тупо нахожу SX, которое минимально по модулю, да умножаю его на X,Y.
Теперь еще бы деление упразднить...

[Tanya]

Теперь еще бы деление упразднить...

А я Вам что предлагала?
Пусть для простоты Ваш вектор R лежит между двумя базисными векторами A и B.
Мы знаем (уже вычислили) два векторных произведения Вашего вектора и базисных. Искомая точка (вектор) выражается в виде A + a(B-A), при этом векторное произведение с R должно равняться нулю. (0<a<1)
Раз мы (Вы) не хотим использовать деление, то можем найти приближенное решение методом деления отрезка пополам - найдем a.
При этом, векторные произведения уже не нужно повторно искать - мы их помним.