Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.21.103.209] |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Есть вершина, есть четыре точки. Не обязательно они расположены правильно, не обязательно расстояние из вершины до каждой точки одинаково. Так вот из вершины через эти четыре точки исходят лучи образуя пирамиду, основание находится где-то в далеке. иначе сказать образуется четырёхгранный угол.
Вопрос: как определить нахидится ли некая точка (x,y,z) в этой пирамиде (четырёхгранном угле)? |
Сообщ.
#2
,
|
|
|
Определить, принадлежит ли точка d трехгранному углу (a,b,c) можно примерно так:
if( (det(a,b,d)+det(b,c,d)+det(c,a,d))>det(a,b,c) ) { //не принадлежит } else { //принадлежит } det= определитель, составленный из соответствующих векторов. Это в том случае, если вершина пирамиды в начале координат. Иначе- вычитаешь из координат точки координаты вершины. С четырехгранным сложнее, придется разбить его на два трегранных и считать по отдельности. |
Сообщ.
#3
,
|
|
|
Цитата OpenGL @ трехгранному углу (a,b,c) трёхгранный угол - это такой угол который составлен из векторов a, b и c ? я правильно понял? |
Сообщ.
#4
,
|
|
|
Цитата я правильно понял? Да, правильно Еще посмотри тут, глава 2, про принадлежность точки многоугольнику- возможно, подойдет подобный алгоритм |
Сообщ.
#5
,
|
|
|
Цитата OpenGL @ Определить, принадлежит ли точка d трехгранному углу (a,b,c) можно примерно так: Извиняюсь, наврал det это не определитель, это модуль определителя |
Сообщ.
#6
,
|
|
|
Цитата Ahilles @ Есть вершина, есть четыре точки. Не обязательно они расположены правильно, не обязательно расстояние из вершины до каждой точки одинаково. Так вот из вершины через эти четыре точки исходят лучи образуя пирамиду, основание находится где-то в далеке. иначе сказать образуется четырёхгранный угол. Иначе сказать, выходит ли точка за основание, тебя не интересует. Впрочем, это децл. Цитата Ahilles @ Вопрос: как определить нахидится ли некая точка (x,y,z) в этой пирамиде (четырёхгранном угле)? Если нужно проверять на принадлежность много точек, можно зараннее посчитать и запомнить нормали к граням четырехгранного угла, причем лутше направление обхода задать так, чтобы скалярное произведение номали на вектор вершина->тестируемая точка было положительным. Тогда для выпуклого угла надо проверить, что все эти скалярные произведения положительны, или, если направление обхода не подбирать, имеют один знак. Впуклый угол надо разбить на два трехгранных дополнительной гранью от впуклого ребра к противолежащему. Заметим, что положение точки отн. доп. грани надо проверять один раз - сначала проверяем его, а затем, в зависимости от положения отн. доп. грани (знака скалярного произведения) проверяем две из четырех заданных граней. Сложность - три скалярных произведения в трехмерном пространстве, т.е. 9 умножений. |
Сообщ.
#7
,
|
|
|
Следующая функция проверяет, находится ли точка P внутри тетраэдра ABCD. По сути это разложение вектора AP по векторам AB, AC, AD.
Четырехгранную пирамиду нетрудно разбить на два тетраэдра. А для проверки, находится ли точка внутри пространственного угла, нужно убрать ограничение отсечения задней плоскостью - сравнение с Det function PtInTetrahedron(ax, ay, az, bx, by, bz, cx, cy, cz, dx, dy, dz, px, py, pz: Integer): Boolean; var Det, b, c, d: Integer; cdx, cdy, cdz: Integer; begin Result := False; bx := bx - ax; by := by - ay; bz := bz - az; cx := cx - ax; cy := cy - ay; cz := cz - az; dx := dx - ax; dy := dy - ay; dz := dz - az; px := px - ax; py := py - ay; pz := pz - az; cdx := cy * dz - cz * dy; cdy := cz * dx - cx * dz; cdz := cx * dy - cy * dx; Det := bx * cdx + by * cdy + bz * cdz; if Det <> 0 then begin b := px * cdx + py * cdy + pz * cdz; c := px * (dy * bz - dz * by) + py * (dz * bx - dx * bz) + pz * (dx * by - dy * bx); d := px * (by * cz - bz * cy) + py * (bz * cx - bx * cz) + pz * (bx * cy - by * cx); if Det > 0 then Result := (b >= 0) and (c >= 0) and (d >= 0) and (b + c + d <= Det) else Result := (b <= 0) and (c <= 0) and (d <= 0) and (b + c + d >= Det); end; end; |
Сообщ.
#8
,
|
|
|
спасибо конечно.
MBo, спасибо, но не то, но похоже я теме неправильное название дал, у меня есть четырёхгранный угол, мне надо определить входит ли точка в него. Мне больше подходит алгоритм, который дал OpenGL. Добавлено Цитата OpenGL @ Это в том случае, если вершина пирамиды в начале координат. Иначе- вычитаешь из координат точки координаты вершины. надо вычесть из координаты точки координаты вершины, а так же из координат каждой из четырёх точек. правильно? |
Сообщ.
#9
,
|
|
|
Цитата Ahilles @ надо вычесть из координаты точки координаты вершины, а так же из координат каждой из четырёх точек. правильно? |
Сообщ.
#10
,
|
|
|
так, алгоритм реализовал.
но оказалось что он определяет что точка именно внутри пирамиды, т.е. если точка дальше основания, то не работает. |
Сообщ.
#11
,
|
|
|
Тогда попробуй так. Составь матрицу 3х3, в которой столбцы будут векторами a,b,c. Найди обратную к ней. Теперь если ты умножишь эту матрицу на вектор d, то, если все компоненты получившегося вектора неотрицательны, то точка лежит внутри угла.
ЗЫ обратная матрица будет существовать, если определитель не равен нулю, что в данном случае эквивалентно тому, что вектора не лежат в одной плоскости. |
Сообщ.
#12
,
|
|
|
>у меня есть четырёхгранный угол, мне надо определить входит ли точка в него
Я же написал, что нужно изменить |
Сообщ.
#13
,
|
|
|
спасибо MBo и OpenGL
буду думать... |
Сообщ.
#14
,
|
|
|
Я так понимаю, угол можно рассечь плоскостью и получить четурехугольник. Можно спроецировать точку на эту плоскость и проверить принадлежность проекцию четырехугольнику
|
Сообщ.
#15
,
|
|
|
Цитата amk @ Я так понимаю, угол можно рассечь плоскостью и получить четурехугольник. Можно спроецировать точку на эту плоскость и проверить принадлежность проекции четырехугольнику. Кстати, это первое, о чем я подумал. И для балее чем четыргранного угла, скорее всего, именно так и надо делать. |