如何快速检查点（3D）是否在由点集合给出的凸包内部 [英] How to fastest check if point (3D) is inside convex hull given by set of point

问题描述

我已经设置了P点（3D），它们是凸包的顶点（每个）。我正在寻找检查给定点p0是否不在此凸包之外的方法。

我需要重复检查几次（对于不同的p0）。所以如果有可能重用部分计算，这将是很好的。

在stackoverflow页面上我发现这个：
查找点是否在凸面内在没有计算船体本身的情况下为一组点计算一组点
有两个aproche：
首先基于凸包属性 - 一组线性方程组。
根据观察得出的结论：当其他点的凸包外部的点位于当且仅当从它到其他点的所有矢量的方向小于圆/球/半球的一半时，超过它。

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

解决方案

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>多面体; 
 typedef CGAL :: AABB_face_graph_triangle_primitive< Polyhedron>原始; 
 typedef CGAL :: AABB_traits< K，原始>性状; 
 typedef CGAL :: AABB_tree< Traits>树; 
 typedef CGAL :: Side_of_triangle_mesh< Polyhedron，K> Point_inside; 
 
 bool pointInside（Polyhedron& polyhedron，Point& query）{
 //构造具有KdTree 
的AABB树树树（faces（polyhedron）.first，faces（多面体）。第二，多面体）; 
 tree.accelerate_distance_queries（）; 
 //初始化多面体中的点测试器
 Point_inside inside_tester（tree）; 
 
 //确定边，如果在里面，则返回true！ 
 return inside_tester（query）== CGAL :: ON_BOUNDED_SIDE; 
} 
  

I have set P of point (3D) which are vertices of convex hull (every one). I looking for method for checking if given point p0 is NOT outside of this convex hull.

I'll have to repeat the checking it several times (for different p0). So if is possible to reuse part of computation it would be great.

On stackoverflow pages i found this: Find if a point is inside a convex hull for a set of points without computing the hull itself There are 2 aproche: First based on convex hull property - set of linear equations. Secound based on observation: "The point lies outside of the convex hull of the other points if and only if the direction of all the vectors from it to those other points are on less than one half of a circle/sphere/hypersphere around it."

Unfortunately I don't know how exactly can do it. First give me insoluble system of equations - 3 equation with n unknown (n>3). How can I sovle it? Did I do some mistake? In second approach I don't know how check this assumption.

解决方案

CGAL can easily do this test. Not only you could build the convex hull with CGAL, but you can quickly and easily determine whether a specific point is inside, on the surface or outside of the polyhedron.

A code snippet is shown below:

#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;
}

这篇关于如何快速检查点（3D）是否在由点集合给出的凸包内部的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！