如何快速检查给定一组点所构成的凸包内是否包含一个三维点

Question

我设置了一组点 P（3D），它们是凸包的每个顶点。我正在寻找检查给定点 p0 是否不在该凸包之外的方法。我将不得不多次进行检查（对于不同的 p0）。因此，如果可能重用部分计算，那将是很好的。

在stackoverflow页面上，我发现了这个问题： Find if a point is inside a convex hull for a set of points without computing the hull itself 有两种方法：第一种基于凸包属性 - 一组线性方程。第二种基于观察：“当且仅当来自其他点到它的所有向量的方向位于围绕它的半圆形/球体/超球体的一半以下时，该点位于其他点的凸包之外。”

不幸的是我不知道如何做到这一点。首先给我一个不可解的方程系统-3个方程和 n 个未知数（n > 3）。我该怎么解决它？我犯了一些错误吗？在第二种方法中，我不知道如何检查这个假设。

- Marcel Słabosz

---

我不确定这是否会引导你朝着正确的方向，但还是想提一下：如果你把这个问题转化为如何计算点p0的重心权重/坐标，会怎样呢？如果我没记错的话，在凸包内部的点的重心权重将在[0,1]之间... - André

我认为我的查找点是否在多边形内部的答案可以解决你的问题，代码是用C#编写的。实际上，将其转换为3D并不难，并且非常快速。 - Saeed Amiri

@Andre。这正是我在问题中提到的第一种方法。如果我知道如何计算权重向量，那么我可以简单地检查是否所有条件都满足在[0,1]区间内。但是如果我有一个包含多个元素的集合P，并且只有一个点具有3个维度，该怎么办？ - Marcel Słabosz

@Saeed Amiri。谢谢。对我来说，这看起来像是Graham算法在2D中的一步，但我无法想象如何将其移动到3D。如果您能给我一些线索就好了。PS. 如果我犯了语言错误，请原谅，因为英语不是我的母语。因此，请以可能最简单的方式回答。 :) - Marcel Słabosz

Answer 1

CGAL可以轻松完成这个测试。不仅可以使用CGAL构建凸包，还可以快速轻松地确定特定点是在多面体的内部、表面上还是外部。下面展示了代码片段：

#include <CGAL/Simple_cartesian.h>
#include <CGAL/AABB_tree.h>
#include <CGAL/AABB_traits.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/boost/graph/graph_traits_Polyhedron_3.h>
#include <CGAL/AABB_face_graph_triangle_primitive.h>
#include <CGAL/algorithm.h>
#include <CGAL/Side_of_triangle_mesh.h>

typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_3 Point;
typedef CGAL::Polyhedron_3<K> Polyhedron;
typedef CGAL::AABB_face_graph_triangle_primitive<Polyhedron> Primitive;
typedef CGAL::AABB_traits<K, Primitive> Traits;
typedef CGAL::AABB_tree<Traits> Tree;
typedef CGAL::Side_of_triangle_mesh<Polyhedron, K> Point_inside;

bool pointInside(Polyhedron &polyhedron, Point &query) {
    // Construct AABB tree with a KdTree
    Tree tree(faces(polyhedron).first, faces(polyhedron).second, polyhedron);
    tree.accelerate_distance_queries();
    // Initialize the point-in-polyhedron tester
    Point_inside inside_tester(tree);

    // Determine the side and return true if inside!
    return inside_tester(query) == CGAL::ON_BOUNDED_SIDE;
}

- Maghoumi

Answer 2

假设P很大且有许多p0，您应该计算一个三维三角测量来进行点定位。这是一个CGAL演示。

- Per

---

你建议计算凸包三角剖分，然后尝试定位点p0在哪个三角形（simplex）中。但如果凸包三角剖分的simplex只是平面三角形（不是四面体）呢？（我不确定。）这样有体积而不仅仅是表面吗？没有办法不计算凸包吗？谢谢回答。 - Marcel Słabosz

@MarcelSłabosz 您需要将其分成3D单纯形。 - Per

我被GCAL打败了。我无法安装这个库。首先，我下载了GCAL zip文件并解压缩它。但是这样还不足以运行。接下来，我下载并解压缩boost，安装Cmake并尝试使用，但是出现了一些额外的错误。 Cmake给了我以下错误信息： CMake Error: Unable to find the executable at any of: E:/Library/CGAL-3.9/CMakeFiles/CMakeTmp/cmTryCompileExec.exe E:/Library/CGAL-3.9/CMakeFiles/CMakeTmp/Debug/cmTryCompileExec.exe E:/Library/CGAL-3.9/CMakeFiles/CMakeTmp/Development/cmTryCompileExec.exe此外，我还遇到了一些查找boost_thread的问题。 - Marcel Słabosz

Answer 3

你可以将凸壳中的点作为矩阵中的列写下来，然后有一个向量告诉你要取哪些点的组合：

(X1 X2)  (a)      (X1a + X2b)
(Y1 Y2)  (b)   =  (Y1a + Y2b)
(Z1 Z2)           (Z1a + Z2b)

为了生成您的目标点，您需要找到一个向量来解决这个问题，同时满足向量元素在0和1之间，并且向量元素相加等于1的约束条件。如果有解决方案，您可以通过线性规划来解决这种问题，可能涉及使用http://en.wikipedia.org/wiki/Simplex_algorithm。

有各种技巧可以将其转换为严格形式。向矩阵添加另一行将允许您说a + b = 1。为了强制b <= 1，您可以有b + q = 1和q >= 0，尽管如下面的Ted Hopp所指出的那样，在这种情况下，b <= 1因为a + b = 1，而且a和b都是>= 0。

- mcdowella

---

约束条件“介于0和1之间”可以放宽为“非负”。它们总和为1的附加约束使上限变得多余。 - Ted Hopp