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

Question

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

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

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

Прямо сейчас я делаю это с линейным программированием, например, как в /questions/17705482/najti-nahoditsya-li-tochka-vnutri-vyipukloj-obolochki-dlya-nabora-tochek-ne-vyichislyaya-samu-obolochku/17705495#17705495

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

Я делаю это сейчас, сначала посмотрев на ограничивающую рамку моего pointcloud, а во-вторых, подход в /questions/17705482/najti-nahoditsya-li-tochka-vnutri-vyipukloj-obolochki-dlya-nabora-tochek-ne-vyichislyaya-samu-obolochku/17705493#17705493 - комментарий от yombo. Но оба метода могут только определить, находится ли точка за пределами (и оба метода довольно грубые).

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

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

Answer 1

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

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

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