Учитывая треугольник с вершинами (a, b, c):
c
/ \
/ \
/ \
a - - - - b
, который затем делится на четыре треугольника путем деления пополам каждого из ребер:
c
/ \
/ \
ca / \ bc
_ _ _
/\ /\
/ \ / \
/ \ / \
a - - - - ab - - - -b
Какие результатыв четырех треугольниках (a, ab, ca), (b, bc, ab), (c, ca, bc), (ab, bc, ca).
Теперь задана точка p.Как определить, в каком треугольнике p лежит, учитывая, что p находится внутри внешнего треугольника (a, b, c)?
В настоящее время я намерен использовать ab в качестве источника.Проверьте, находится ли он слева от правой части строки «ca - ab», используя perp «ca - ab» и проверив знак по отношению к точечному произведению «ab - a» и вектору perp и вектору «p -».аб».Если оно одинаковое или скалярное произведение равно нулю, то оно должно быть в (a, ab, ca) ... Продолжите эту процедуру с другими внешними треугольниками (b, ba, ab) & (c, ca, ba),В конце концов, если он не совпадает с ними, он должен содержаться во внутреннем треугольнике (ab, bc, ca).
Есть ли лучший способ сделать это?
РЕДАКТИРОВАТЬ
Вот еще немного информации о предполагаемом применении алгоритма:
Я использую это как маску подразделения для генерациипрекрасная сетка, по которой я намерен интерполировать.Каждый из треугольников будет разделен аналогично до указанной глубины.Я хочу определить треугольник (на максимальной глубине), в котором лежит точка p.При этом я могу оценить функцию в точке р, используя интерполяцию по треугольнику.Существует класс треугольников, которые имеют прямоугольные формы и составляют значительную часть, но с ними гораздо проще работать, и этот алгоритм для них не предназначен.