ポイントが多面体の内側にあるかどうかを判断します

Question

特定のポイントが多面体の中にあるかどうかを判断しようとしています。私の現在の実装では、私が取り組んでいる方法は、多面体の顔の配列（この場合は三角形ですが、他のポリゴンが後である可能性があります）を探しています。私はここにある情報から仕事をしようとしてきました： http://softsurfer.com/archive/algorithm_0111/algorithm_0111.htm

以下に、私の「内部」の方法が表示されます。 NRML/通常のものはちょっと奇妙であることを知っています。それは古いコードの結果です。私がこれを実行していたとき、それは私がそれにどんな入力を与えても、常に真実を返しているように見えました。 （これは解決されます、以下の私の答えを参照してください - このコードは現在機能しています）。

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 ++にありますが、コメントで述べたように、本当に言語不可知論者です。

Answer 1

問題は、上記のリンクで参照されているアルゴリズムの読み物であることがわかりました。読んでいた：

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

なので

N = - dot product of S and ni;

これを変更したため、上記のコードは正しく機能しているようです。 （正しい解決策を反映するために、質問のコードを更新しています）。

Answer 2

あなたの質問のリンクは有効になり、私はあなたのコードからのアルゴリズムを理解できませんでした。あなたが持っていると仮定します 凸 Polyhedron with 反時計回り 方向のある顔（外から見る）、あなたのポイントがすべての顔の背後にあることを確認するだけで十分でなければなりません。そのためには、ベクトルをポイントから各顔に持ち込み、スカラー製品の標識を顔の正常で確認できます。それが正である場合、ポイントは顔の後ろにあります。ゼロの場合、ポイントは顔にあります。負の場合、ポイントは顔の前にあります。

以下は、3ポイントの顔またはプレーンポイント面で動作する完全なC ++ 11コードを示します（最初の3ポイントのみが考慮されます）。簡単に変更できます bound 境界を除外します。

#include <vector>
#include <cassert>
#include <iostream>
#include <cmath>

struct Vector {
  double x, y, z;

  Vector operator-(Vector p) const {
    return Vector{x - p.x, y - p.y, z - p.z};
  }

  Vector cross(Vector p) const {
    return Vector{
      y * p.z - p.y * z,
      z * p.x - p.z * x,
      x * p.y - p.x * y
    };
  }

  double dot(Vector p) const {
    return x * p.x + y * p.y + z * p.z;
  }

  double norm() const {
    return std::sqrt(x*x + y*y + z*z);
  }
};

using Point = Vector;

struct Face {
  std::vector<Point> v;

  Vector normal() const {
    assert(v.size() > 2);
    Vector dir1 = v[1] - v[0];
    Vector dir2 = v[2] - v[0];
    Vector n  = dir1.cross(dir2);
    double d = n.norm();
    return Vector{n.x / d, n.y / d, n.z / d};
  }
};

bool isInConvexPoly(Point const& p, std::vector<Face> const& fs) {
  for (Face const& f : fs) {
    Vector p2f = f.v[0] - p;         // f.v[0] is an arbitrary point on f
    double d = p2f.dot(f.normal());
    d /= p2f.norm();                 // for numeric stability

    constexpr double bound = -1e-15; // use 1e15 to exclude boundaries
    if (d < bound)
      return false;
  }

  return true;
}

int main(int argc, char* argv[]) {
  assert(argc == 3+1);
  char* end;
  Point p;
  p.x = std::strtod(argv[1], &end);
  p.y = std::strtod(argv[2], &end);
  p.z = std::strtod(argv[3], &end);

  std::vector<Face> cube{ // faces with 4 points, last point is ignored
    Face{{Point{0,0,0}, Point{1,0,0}, Point{1,0,1}, Point{0,0,1}}}, // front
    Face{{Point{0,1,0}, Point{0,1,1}, Point{1,1,1}, Point{1,1,0}}}, // back
    Face{{Point{0,0,0}, Point{0,0,1}, Point{0,1,1}, Point{0,1,0}}}, // left
    Face{{Point{1,0,0}, Point{1,1,0}, Point{1,1,1}, Point{1,0,1}}}, // right
    Face{{Point{0,0,1}, Point{1,0,1}, Point{1,1,1}, Point{0,1,1}}}, // top
    Face{{Point{0,0,0}, Point{0,1,0}, Point{1,1,0}, Point{1,0,0}}}, // bottom
  };

  std::cout << (isInConvexPoly(p, cube) ? "inside" : "outside") << std::endl;

  return 0;
}

お気に入りのコンパイラでコンパイルします

clang++ -Wall -std=c++11 code.cpp -o inpoly

そして、それをテストします

$ ./inpoly 0.5 0.5 0.5
inside
$ ./inpoly 1 1 1
inside
$ ./inpoly 2 2 2
outside