algorithm - jarvis - Encuentre si un punto está dentro de un casco convexo para un conjunto de puntos sin calcular el casco mismo

envolvente convexa

Question

¿Cuál es la forma más simple de probar si un punto P está dentro de un casco convexo formado por un conjunto de puntos X?

Me gustaría un algoritmo que funcione en un espacio de alta dimensión (por ejemplo, hasta 40 dimensiones) que no calcule explícitamente el casco convexo. ¿Algunas ideas?

Answer 1

¿Estás dispuesto a aceptar una respuesta heurística que normalmente debería funcionar pero que no está garantizada? Si eres así, podrías probar esta idea aleatoria.

Sea f (x) el cubo de la distancia a P multiplicado por el número de cosas en X, menos la suma de los cubos de la distancia a todos los puntos en X. Comience en algún lugar al azar y use un algoritmo de escalada para maximizar f (x) para x en una esfera que está muy lejos de P. Excepto casos degenerados, si P no está en el casco convexo, esto debería tener una muy buena probabilidad de encontrar la normal a un hiperplano, que P está a un lado de , y todo en X está del otro lado.

Answer 2

Aunque la publicación original fue hace tres años, tal vez esta respuesta aún sea útil. El algoritmo de Gilbert-Johnson-Keerthi (GJK) encuentra la distancia más corta entre dos politopes convexos, cada uno de los cuales se define como el casco convexo de un conjunto de generadores --- notablemente, el casco convexo en sí mismo no tiene que ser calculado. En un caso especial, que es el caso sobre el que se pregunta, uno de los politopos es solo un punto. ¿Por qué no intentar usar el algoritmo GJK para calcular la distancia entre P y el casco convexo de los puntos X? Si esa distancia es 0, entonces P está dentro de X (o al menos en su límite). Una implementación de GJK en Octave / Matlab, llamada ClosestPointInConvexPolytopeGJK.m, junto con el código de soporte, está disponible en http://www.99main.com/~centore/MunsellAndKubelkaMunkToolbox/MunsellAndKubelkaMunkToolbox.html . Una simple descripción del algoritmo GJK está disponible en la Sección. 2 de un artículo, en http://www.99main.com/~centore/ColourSciencePapers/GJKinConstrainedLeastSquares.pdf . Utilicé el algoritmo GJK para algunos conjuntos muy pequeños X en el espacio de 31 dimensiones y obtuve buenos resultados. La forma en que el rendimiento de GJK se compara con los métodos de programación lineal que otros recomiendan es incierta (aunque cualquier comparación sería interesante). El método GJK evita el cálculo del casco convexo o la expresión del casco en términos de desigualdades lineales, lo que puede llevar mucho tiempo. Espero que esta respuesta ayude.

Answer 3

El problema se puede resolver encontrando un punto factible de un Programa Lineal. Si le interesan los detalles completos, en lugar de simplemente conectar un LP a un solucionador existente, le recomendaría leer el Capítulo 11.4 en el excelente libro de Boyd y Vandenberghe sobre optimización convexa .

Establezca A = (X[1] X[2] ... X[n]) , es decir, la primera columna es v1 , la segunda v2 , etc.

Resuelve el siguiente problema de LP,

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

dónde

1. x^T es la transposición de x
2. [1] es el vector todo-1.

El problema tiene una solución si el punto está en el casco convexo.

Answer 4

El punto se encuentra fuera del casco convexo de los otros puntos si y solo si la dirección de todos los vectores desde él a esos otros puntos está en menos de la mitad de un círculo / esfera / hiperesfera a su alrededor.

Answer 5

No tiene que calcular el casco convexo en sí, ya que parece bastante problemático en espacios multidimensionales. Hay una propiedad bien conocida de cascos convexos :

Cualquier vector (punto) v dentro del casco convexo de los puntos [v1, v2, .., vn] se puede presentar como sum(ki*vi) , donde 0 <= ki <= 1 y sum(ki) = 1 . En consecuencia, ningún punto fuera del casco convexo tendrá dicha representación.

En el espacio m-dimensional, esto nos dará el conjunto de m ecuaciones lineales con n incógnitas.

editar
No estoy seguro acerca de la complejidad de este nuevo problema en el caso general, pero para m = 2 parece lineal. Tal vez, alguien con más experiencia en esta área me corrija.

Answer 6

Tuve el mismo problema con 16 dimensiones. Como incluso qhull no funcionaba correctamente porque se tenían que generar demasiadas caras, desarrollé mi propio enfoque probando si se puede encontrar un hiperplano de separación entre el nuevo punto y los datos de referencia (lo llamo "HyperHull";)) .

El problema de encontrar un hiperplano de separación se puede transformar en un problema de programación cuadrático convexo (ver: SVM ). Hice esto en python usando cvxopt con menos de 170 líneas de código (incluida E / S). El algoritmo funciona sin modificación en cualquier dimensión, incluso si existe el problema, que cuanto mayor sea la dimensión, mayor será el número de puntos en el casco (ver: En el casco convexo de puntos aleatorios en un politopo ). Como el casco no se construye explícitamente, solo se controla, si un punto está dentro o no, el algoritmo tiene ventajas muy grandes en dimensiones más altas en comparación con, por ejemplo, el casco rápido.

Este algoritmo puede ''paralelizarse'' naturalmente y la aceleración debe ser igual al número de procesadores.