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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вот еще проще способ.
координаты 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

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


Пусть:

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].

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