如何检查一个点是在一个ConvexHull使用CGAL

Question

我使用CGAL库创建了一个带有一些3D点的凸壳。现在我想检查一个点是否在船体内部。但我找不到任何选择。有人能帮忙吗?

我的代码如下。

    #include <CGAL/Simple_cartesian.h>
    #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
    #include <CGAL/point_generators_3.h>
    #include <CGAL/algorithm.h>
    #include <CGAL/Polyhedron_3.h>
    #include <CGAL/convex_hull_3.h>
    #include <vector>
    typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
    typedef CGAL::Polyhedron_3<K> Polyhedron;
    typedef K::Point_3 Point;
    std::vector<Point> hullPoints[16];
    int numPoints[16];
    Polyhedron poly[16];
    //Reading hull points
    for(int i=0;i<a->vertI;i++)
    {
        for(int j=0;j<16;j++)
        {
            if(a->vertices[i][1] <= (a->maxY-(j*(a->maxY-a->minY)/16.0)) && a->vertices[i][1] >= (a->maxY-((j+1)*(a->maxY-a->minY)/16.0)) )
            {
                hullPoints[j].push_back(Point(a->vertices[i][0],a->vertices[i][1],a->vertices[i][2]));
            }

        }

    }
//Create hull
    for(int i=0;i<16;i++)
    {
        CGAL::convex_hull_3(hullPoints[i].begin(), hullPoints[i].end(), poly[i]);
        std::cout << "The convex hull " << i <<" contains " << poly[i].size_of_vertices() << " vertices" << std::endl;
    }

它的工作完美，我可以访问多边形，看到没有顶点存在于它。但是不能查找和检查一个点是否在里面

Answer 1

这是一种2D方法的改编，但它可能是可行的…

你能定义构成凸壳表面的二维平面吗?如果是这样，那么在有问题的点和任何其他足够远的点之间构造一条无限线，以保证在船体外。然后，对于船体表面上的每个平面，确定这条线是否与该平面相交。

编辑。(感谢BrunoLevy的评论)
对于一个一般的任意封闭三维船体，如果它穿过奇数个平面，点在船体内，如果它是偶数，点在船体外。

对你来说就简单多了。对于凸船体，它必须穿过零个、一个或两个这样的平面。