Как быстро проверить, находится ли точка (3D) внутри выпуклой оболочки, заданной набором точек

Question

Я установил P точки (3D), которые являются вершинами выпуклой оболочки (каждая). Я ищу метод проверки, если заданная точка p0 НЕ находится вне этой выпуклой оболочки.

Мне придется повторить проверку несколько раз (для разных p0). Так что, если есть возможность повторно использовать часть вычислений, это было бы здорово.

На страницах stackoverflow я нашел это: Найти, если точка находится внутри выпуклой оболочки для набора точек без вычисления самой оболочки Есть 2 апроша: Сначала на основе свойства выпуклой оболочки - системы линейных уравнений. Побег, основанный на наблюдении: «Точка лежит вне выпуклой оболочки других точек тогда и только тогда, когда направление всех векторов от нее к этим другим точкам находится на менее чем половине окружности / сферы / гиперсферы вокруг нее. «

К сожалению, я не знаю, как именно это можно сделать. Сначала дайте мне неразрешимую систему уравнений - 3 уравнения с n неизвестным (n> 3). Как я могу соврать это? Я сделал какую-то ошибку? При втором подходе я не знаю, как проверить это предположение.

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

Answer 2

Вы можете записать точки в корпусе в виде столбцов в матрице, а затем иметь вектор, который говорит вам, какую комбинацию точек взять:

(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, хотя, как указал Тед Хопп ниже, в этом случае b<= 1, потому что a + b = 1, а a и b равны> = 0.

Answer 3

Предполагая, что P велико и есть много p0, вы должны вычислить трехмерную триангуляцию, в которой нужно определить местоположение точки. Это демо CGAL .