How to quickly check if a point (3D) is inside a convex hull defined by many points

Question

I set P points (3D), which are the vertices of the convex hull (each). I am looking for a verification method if the given point p0 is NOT outside this convex hull.

I will need to repeat the check several times (for different p0). Therefore, if you can reuse part of the calculations, it would be great.

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

Unfortunately, I do not know how exactly this can be done. First, give me an unsolvable system of equations - 3 equation with n unknowns (n> 3). How can I process it? Did I make any mistake? In the second approach, I do not know how to verify this assumption.

Answer 1

Assuming P is large and there is a lot of p0, you must calculate a three-dimensional triangulation in which you need to make a point location. This is a CGAL demo .

Answer 2

You can write the points in the case as columns in the matrix, and then specify a vector that tells you which combination of points to take:

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

To generate a target point, you want to find a vector that solves this, taking into account the limitations that the elements of the vector are between 0 and 1, and that the elements of the vector are up to 1. You can solve this problem by looking at the problem - if there is a solution - through linear programming Which may include the use of http://en.wikipedia.org/wiki/Simplex_algorithm .

There are many tricks to get this in strict form. Adding another row to the matrix allows you to say a + b = 1. To force b <= 1, you could have b + q = 1 and q> = 0, although, as Ted Hopp points out below, in this case b <= 1, because a + b = 1, and both a and b → 0.

Answer 3

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

The following is a snippet of code:

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