确定点是否在多面体内 [英] Determining if a point is inside a polyhedron

问题描述

我试图确定特定点是否位于多面体内。在我目前的实现中，我工作的方法，我们正在寻找的点，我们正在寻找多面体的面（在这种情况下，三角形，但它可以是其他多边形）。我一直在尝试从这里找到的信息： http://softsurfer.com/Archive/ algorithm_0111 / algorithm_0111.htm

I'm attempting to determine if a specific point lies inside a polyhedron. In my current implementation, the method I'm working on take the point we're looking for an array of the faces of the polyhedron (triangles in this case, but it could be other polygons later). I've been trying to work from the info found here: http://softsurfer.com/Archive/algorithm_0111/algorithm_0111.htm

下面，您将看到我的inside方法。我知道nrml /正常的东西是有点怪异的..它是旧代码的结果。当我运行这个似乎总是返回true，无论什么输入，我给它。 （这是解决，请看下面的答案 - 这段代码是现在工作）。

Below, you'll see my "inside" method. I know that the nrml/normal thing is kind of weird .. it's the result of old code. When I was running this it seemed to always return true no matter what input I give it. (This is solved, please see my answer below -- this code is working now).

bool Container::inside(Point* point, float* polyhedron[3], int faces) {
  Vector* dS = Vector::fromPoints(point->X, point->Y, point->Z,
                 100, 100, 100);
  int T_e = 0;
  int T_l = 1;

  for (int i = 0; i < faces; i++) {
    float* polygon = polyhedron[i];

    float* nrml = normal(&polygon[0], &polygon[1], &polygon[2]);
    Vector* normal = new Vector(nrml[0], nrml[1], nrml[2]);
    delete nrml;

    float N = -((point->X-polygon[0][0])*normal->X + 
                (point->Y-polygon[0][1])*normal->Y +
                (point->Z-polygon[0][2])*normal->Z);
    float D = dS->dot(*normal);

    if (D == 0) {
      if (N < 0) {
        return false;
      }

      continue;
    }

    float t = N/D;

    if (D < 0) {
      T_e = (t > T_e) ? t : T_e;
      if (T_e > T_l) {
        return false;
      }
    } else {
      T_l = (t < T_l) ? t : T_l;
      if (T_l < T_e) {
        return false;
      }
    }
  }

  return true;
}

这是在C ++中，但正如评论中提到的，它真的非常语言不可知。

This is in C++ but as mentioned in the comments, it's really very language agnostic.

推荐答案

事实证明，问题是我阅读上面链接中引用的算法。我正在阅读：

It turns out that the problem was my reading of the algorithm referenced in the link above. I was reading:

N = - dot product of (P0-Vi) and ni;

为

N = - dot product of S and ni;

改变了这一点，上面的代码现在似乎工作正常。 （我也更新问题中的代码以反映正确的解决方案）。

Having changed this, the code above now seems to work correctly. (I'm also updating the code in the question to reflect the correct solution).

这篇关于确定点是否在多面体内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！