确定一个点是否在多面体内部 [英] 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

在下面，您将看到我的内部"方法.我知道 nrml/normal 的东西有点奇怪......这是旧代码的结果.当我运行它时，无论我给它什么输入，它似乎总是返回 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屋！