На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Определить входит ли точка в пирамиду , ну не совсем в пирамиду....
    Есть вершина, есть четыре точки. Не обязательно они расположены правильно, не обязательно расстояние из вершины до каждой точки одинаково. Так вот из вершины через эти четыре точки исходят лучи образуя пирамиду, основание находится где-то в далеке. иначе сказать образуется четырёхгранный угол.
    Вопрос: как определить нахидится ли некая точка (x,y,z) в этой пирамиде (четырёхгранном угле)?
    Сообщение отредактировано: Ahilles -
      Определить, принадлежит ли точка d трехгранному углу (a,b,c) можно примерно так:

      ExpandedWrap disabled
        if(  (det(a,b,d)+det(b,c,d)+det(c,a,d))>det(a,b,c) )
        {
          //не принадлежит
        }
        else
        {
           //принадлежит
        }


      det= определитель, составленный из соответствующих векторов.
      Это в том случае, если вершина пирамиды в начале координат. Иначе- вычитаешь из координат точки координаты вершины.

      С четырехгранным сложнее, придется разбить его на два трегранных и считать по отдельности.
        Цитата OpenGL @
        трехгранному углу (a,b,c)

        трёхгранный угол - это такой угол который составлен из векторов a, b и c ? я правильно понял?
          Цитата
          я правильно понял?


          Да, правильно

          Еще посмотри тут, глава 2, про принадлежность точки многоугольнику- возможно, подойдет подобный алгоритм
          Сообщение отредактировано: OpenGL -
            Цитата OpenGL @
            Определить, принадлежит ли точка d трехгранному углу (a,b,c) можно примерно так:


            Извиняюсь, наврал :whistle:

            det это не определитель, это модуль определителя
              Цитата Ahilles @
              Есть вершина, есть четыре точки. Не обязательно они расположены правильно, не обязательно расстояние из вершины до каждой точки одинаково. Так вот из вершины через эти четыре точки исходят лучи образуя пирамиду, основание находится где-то в далеке. иначе сказать образуется четырёхгранный угол.

              Иначе сказать, выходит ли точка за основание, тебя не интересует. Впрочем, это децл.

              Цитата Ahilles @
              Вопрос: как определить нахидится ли некая точка (x,y,z) в этой пирамиде (четырёхгранном угле)?

              Если нужно проверять на принадлежность много точек, можно зараннее посчитать и запомнить нормали к граням четырехгранного угла, причем лутше направление обхода задать так, чтобы скалярное произведение номали на вектор вершина->тестируемая точка было положительным. Тогда для выпуклого угла надо проверить, что все эти скалярные произведения положительны, или, если направление обхода не подбирать, имеют один знак. Впуклый угол надо разбить на два трехгранных дополнительной гранью от впуклого ребра к противолежащему. Заметим, что положение точки отн. доп. грани надо проверять один раз - сначала проверяем его, а затем, в зависимости от положения отн. доп. грани (знака скалярного произведения) проверяем две из четырех заданных граней. Сложность - три скалярных произведения в трехмерном пространстве, т.е. 9 умножений.
                Следующая функция проверяет, находится ли точка P внутри тетраэдра ABCD. По сути это разложение вектора AP по векторам AB, AC, AD.
                Четырехгранную пирамиду нетрудно разбить на два тетраэдра.
                А для проверки, находится ли точка внутри пространственного угла, нужно убрать ограничение отсечения задней плоскостью - сравнение с Det
                ExpandedWrap disabled
                  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;
                  спасибо конечно.
                  MBo, спасибо, но не то, но похоже я теме неправильное название дал, у меня есть четырёхгранный угол, мне надо определить входит ли точка в него. Мне больше подходит алгоритм, который дал OpenGL.

                  Добавлено
                  Цитата OpenGL @
                  Это в том случае, если вершина пирамиды в начале координат. Иначе- вычитаешь из координат точки координаты вершины.

                  надо вычесть из координаты точки координаты вершины, а так же из координат каждой из четырёх точек. правильно?
                  Сообщение отредактировано: Ahilles -
                    Цитата Ahilles @
                    надо вычесть из координаты точки координаты вершины, а так же из координат каждой из четырёх точек. правильно?

                    :yes:
                      так, алгоритм реализовал.
                      но оказалось что он определяет что точка именно внутри пирамиды, т.е. если точка дальше основания, то не работает.
                        Тогда попробуй так. Составь матрицу 3х3, в которой столбцы будут векторами a,b,c. Найди обратную к ней. Теперь если ты умножишь эту матрицу на вектор d, то, если все компоненты получившегося вектора неотрицательны, то точка лежит внутри угла.

                        ЗЫ обратная матрица будет существовать, если определитель не равен нулю, что в данном случае эквивалентно тому, что вектора не лежат в одной плоскости.
                        Сообщение отредактировано: OpenGL -
                          >у меня есть четырёхгранный угол, мне надо определить входит ли точка в него
                          Я же написал, что нужно изменить
                            спасибо MBo и OpenGL
                            буду думать...
                              Я так понимаю, угол можно рассечь плоскостью и получить четурехугольник. Можно спроецировать точку на эту плоскость и проверить принадлежность проекцию четырехугольнику
                                Цитата amk @
                                Я так понимаю, угол можно рассечь плоскостью и получить четурехугольник. Можно спроецировать точку на эту плоскость и проверить принадлежность проекции четырехугольнику.

                                Кстати, это первое, о чем я подумал. И для балее чем четыргранного угла, скорее всего, именно так и надо делать. :yes:
                                  Цитата MBo @
                                  Следующая функция проверяет, находится ли точка P внутри тетраэдра ABCD. По сути это разложение вектора AP по векторам AB, AC, AD.
                                  Четырехгранную пирамиду нетрудно разбить на два тетраэдра.
                                  А для проверки, находится ли точка внутри пространственного угла, нужно убрать ограничение отсечения задней плоскостью - сравнение с Det
                                  ExpandedWrap disabled
                                    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;

                                  Здравствуйте, спасибо огромное за функцию

                                  Подскажите, пожалуйста, откуда берутся условия (из каких алгебраических предпосылок)
                                  1)(b + c + d <= Det) в первом случае
                                  2)(b + c + d >= Det) во втором случае
                                    На двумерном примере:
                                    Вектор AP есть линейная комбинация векторов AB, AC:

                                    AP = b * AB + c * AC
                                    Для точек внутри треугольника ABC коэффициенты положительны, и их сумма не превышает единицы (единица достигается только на ребрах).

                                    В данном случае коэффициенты не нормированы (делением на Det), и сравнение проводится с величиной Det
                                      Цитата MBo @

                                      Спасибо
                                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                      0 пользователей:


                                      Рейтинг@Mail.ru
                                      [ Script execution time: 0,0508 ]   [ 16 queries used ]   [ Generated: 28.03.24, 16:51 GMT ]