Грубый тест, если точки находятся внутри / снаружи выпуклой оболочки

Question

Я работаю над алгоритмом, в котором я должен проверить, находятся ли точки внутри или снаружи выпуклой оболочки некоторых точек.Проблема в том, что

1. Я должен проверить это для множества точек: ~ 2000,
2. Облако точек, определяющее выпуклую оболочку, имеет около 10000 точек,
3. размеры, в которых я работаю, довольно велики: 10-50.

Единственное, что может быть положительным для моих очков, это то, что для каждой точки x также есть -x,таким образом, точки определяют точечный симметрический многогранник, а выпуклая оболочка не вырождена (имеет непустую внутреннюю часть).

Сейчас я делаю это с помощью линейного программирования, например, как в https://stackoverflow.com/a/11731437/8052809

Чтобы ускорить мою программу, я хочу оценить, точно ли точка находится внутри или снаружи выпуклой оболочки, прежде чем вычислять ее точно.Другими словами, мне нужен некоторый быстрый алгоритм, который может определить для некоторых точек, находятся ли они внутри или нет, соответственно.вне зависимости от того, находятся они снаружи или нет - и в некоторых случаях быстрый алгоритм не может решить это.

Это я делаю сейчас, сначала посмотрев на ограничивающую рамку моего pointcloud, а во-вторых, подход вhttps://stackoverflow.com/a/4903615/8052809 - комментарий от yombo.Но оба метода могут только определить, действительно ли точка находится снаружи (и оба метода довольно грубые).

Поскольку большинство точек, которые я проверяю, находятся внутри, мне в основном нужен тест, который определяет, является ли точка дляконечно внутри.

Короткий вопрос: мне нужен алгоритм, который может очень быстро проверить, находится ли точка внутри / снаружи выпуклой оболочки или нет.Алгоритму разрешено сообщать «внутри», «без понятия» и «снаружи».

Answer 1

Чтобы быстро удалить точки, которые сертифицированы как находящиеся внутри выпуклой оболочки, вы можете повторно использовать точки, которые вы нашли в своих вычислениях ограничивающей рамки.А именно, 2k точек (измерения k), содержащих минимальное и максимальное значение в каждом измерении.

Вы можете построить небольшую (2k ограничение) задачу линейного программирования и удалить любую точку, которая находится внутри выпуклой оболочкиэти 2k точек.

Вы можете сделать это как для точек запроса, так и для исходного облака точек, что оставит вас с меньшей задачей линейного программирования для решения оставшихся точек.