Найдите, находится ли точка внутри выпуклой оболочки для набора точек без вычисления самого корпуса

Ответ 1

Проблема может быть решена путем нахождения допустимой точки линейной программы. Если вас интересует полная информация, а не просто подключить LP к существующему решателю, я бы рекомендовал прочитать главу 11.4 в Boyd and Vandenberghe отличную книгу о выпуклой оптимизации.

Установить A = (X[1] X[2] ... X[n]), то есть первый столбец v1, второй v2 и т.д.

Решите следующую проблему с LP,

minimize (over x): 1
s.t.     Ax = P
         x^T * [1] = 1
         x[i] >= 0  \forall i

где

• x^T - это транспонирование x
• [1] - это вектор all-1.

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

Ответ 2

Точка лежит вне выпуклой оболочки других точек тогда и только тогда, когда направление всех векторов от нее к этим другим точкам меньше половины окружности/сферы/гиперсферы вокруг нее.

Ответ 3

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

Любой вектор (точка) v внутри выпуклой оболочки точек [v1, v2, .., vn] может быть представлен как sum(ki*vi), где 0 <= ki <= 1 и sum(ki) = 1. Соответственно, никакая точка вне выпуклой оболочки не будет иметь такого представления.

В m-мерном пространстве это даст нам набор линейных уравнений m с n неизвестными.

изменить
Я не уверен в сложности этой новой проблемы в общем случае, но для m = 2 она кажется линейной. Возможно, кто-то, у кого больше опыта в этой области, исправит меня.

Ответ 4

У меня была та же проблема с 16 измерениями. Поскольку даже qhull не работал должным образом, так как слишком много лиц должно было быть создано, я разработал свой собственный подход путем тестирования, можно ли найти разделительную гиперплоскость между новой точкой и справочными данными (я называю это "HyperHull";)),

Задача о нахождении разделительной гиперплоскости может быть преобразована в задачу выпуклого квадратичного программирования (см. SVM). Я сделал это на python, используя cvxopt с менее чем 170 строками кода (включая ввод-вывод). Алгоритм работает без изменений в любом измерении, даже если существует проблема: чем выше размерность, тем выше число точек на корпусе (см. На выпуклой корпус случайных точек в многограннике). Поскольку корпус не сконструирован явно, а проверен только, находится ли точка внутри или нет, алгоритм имеет очень большие преимущества в более высоких измерениях по сравнению с, например, быстрый корпус.

Этот алгоритм может "естественно" распараллеливаться, а ускорение должно быть равно числу процессоров.

Ответ 5

Хотя исходный пост был три года назад, возможно, этот ответ по-прежнему будет полезен. Алгоритм Гильберта-Джонсона-Кирти (GJK) находит кратчайшее расстояние между двумя выпуклыми многогранниками, каждое из которых определяется как выпуклая оболочка множества генераторов - в частности, сама вычисленная оболочка не должна вычисляться. В частном случае, о котором идет речь, один из многогранников - это всего лишь точка. Почему бы не попробовать использовать алгоритм GJK для вычисления расстояния между P и выпуклой оболочкой точек X? Если это расстояние равно 0, то P находится внутри X (или, по крайней мере, на его границе). Реализация GJK в Octave/Matlab под названием ClosestPointInConvexPolytopeGJK.m вместе с поддерживающим кодом доступна по адресу http://www.99main.com/~centore/MunsellAndKubelkaMunkToolbox/MunsellAndKubelkaMunkToolbox.html. Простое описание алгоритма GJK доступно в разделе Sect. 2 документа, http://www.99main.com/~centore/ColourSciencePapers/GJKinConstrainedLeastSquares.pdf. Я использовал алгоритм GJK для некоторых очень маленьких множеств X в 31-мерном пространстве и имел хорошие результаты. Как производительность GJK сравнивается с методами линейного программирования, которые другие рекомендуют, является неопределенной (хотя любые сравнения были бы интересными). Метод GJK не позволяет вычислять выпуклую оболочку или выражать оболочку в терминах линейных неравенств, которые могут потребовать много времени. Надеюсь, что этот ответ поможет.

Ответ 6

Готовы ли вы принять эвристический ответ, который обычно должен работать, но не гарантирован? Если вы тогда, вы можете попробовать эту случайную идею.

Пусть f (x) - куб расстояния до P раз число вещей в X, минус сумма кубов расстояния до всех точек в X. Начните где-нибудь случайным и используйте восхождение на холм алгоритм для максимизации f (x) для x в сфере, очень удаленной от P. За исключением вырожденных случаев, если P не находится в выпуклой оболочке, это должно иметь очень хорошую вероятность найти нормаль к гиперплоскости, на которой P находится одна сторона, и все в X находится на другой стороне.