Алгоритм Point in Polygon 3d (та же плоскость)

Question

У меня есть точка и многоугольник в той же плоскости в трехмерном пространстве, и теперь я хочу проверить, находится ли точка в многоугольнике или нет. Есть ли простой способ изменить алгоритм из этого потока Point in Polygon Algorithm , чтобы он работал для трехмерного пространства? Или есть другие алгоритмы, которые могут легко решить эту проблему?

Если нет, будет ли работать следующая идея: проверьте, является ли плоскость плоскостью XZ или плоскостью YZ, если да, игнорируйте другой оси (т.е. для плоскости XZ игнорировать значения y) и использовать алгоритм pip из ранее упомянутого потока. А если нет, просто игнорируйте значения z точки и многоугольника и используйте алгоритм точки.

Answer 1

есть 2 "основных c" способа проверки плоского вогнутого многоугольника:

1. преобразовать в набор выпуклых и проверить направление перекрестного произведения между точкой и всем Faces

   преобразование в выпуклый многоугольник не так просто, но его можно выполнить либо триангуляцией, либо обрезанием уха, либо каким-либо другим методом ... После этого просто проверьте перекрестные произведения ... так что если ваш выпуклый многоугольник имеет вершины p0,p1,p2,...,p(n-1) и точку тестирования p, затем

   d0 = cross( p-p0 , p0-p(n-1) );
   for (i=1;i<n;i++)
       {
       di = cross( p-p(i), p(i)-p(i-1) );
       if ( dot ( d0 , di ) <=0.0 ) return false;
       }
   return true;
   

   , поэтому просто проверьте все многоугольники и верните ИЛИ подрезультатов

2. используйте хит test

   Вы направляете луч из своей точки в любом направлении, параллельном вашей плоскости, и подсчитываете количество попаданий, нанесенных лучом по краям многоугольника. Если его четная точка находится снаружи, если его нечетная точка находится внутри. Ссылка в вашем вопросе использует этот al go. Однако в 3D вам нужно изменить направление, чтобы оно оставалось внутри плоскости ... например, используя один край многоугольника dir=p1-p0 в качестве направления. Вы также должны закодировать некоторые правила для случаев, когда ваш луч напрямую попадает в вершину, чтобы он учитывался только один раз, а не несколько раз. Также попадание должно быть вычислено в 3D, поэтому вам нужно пересечение оси / линии. Его можно найти здесь:

   • Столкновение конуса с прямоугольником

   просто найдите функцию line closest(axis a0,line l1). Он возвращает линию, которая является ближайшим соединением между линией и осью. Затем просто проверьте, совпадают ли две точки или нет (длина линии равна нулю).

Теперь, чтобы упростить это, вы можете перенести свои 3D-данные в 2D

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

Вы делаете это, просто игнорируя одну координату. Это просто, но это может вызвать некоторые проблемы с округлением, а также результат имеет другую форму (масштабируется по-разному на каждой оси), поэтому показатели больше не те, что может вызвать другие проблемы, если это используется для других целей или какой-либо вид порогового значения б / у.

Есть способ получше. Нам нужны любые 2 базовых вектора u,v, которые перпендикулярны каждому и находятся внутри вашей плоскости, и одна точка o внутри плоскости. Это просто:

o = p0;    // any point from the polygon
u = p1-p0; // any edge of polygon
u /= |u|;  // normalize
v = p2-p1; // any other edge of polygon
v /= |v|;  // normalize
for (;fabs(dot(u,v)>0.75;) // if too parallel
    {
    v=(p(1+rand(n-1))-p0); // chose random "edge"
    v /= |v|;  // normalize
    }
v=cross(u,v); // make u,v perpendicular
v=cross(v,u); // and inside the plane
v /= |v|;     // normalize just in case because of rounding the size might not be unit anymore

Теперь, чтобы преобразовать точку p(x,y,z) из 3D в 2D (x,y) просто выполните:

x = dot(p-o,u);
y = dot(p-o,v);

, чтобы преобразовать обратно в 3D:

p = o + x*u + y*v;

При таком способе преобразования метрики такие же, поэтому длина ребер многоугольника и размер многоугольника не изменятся ...