Calcular el conjunto discreto de puntos B que están en el casco convexo del conjunto de puntos A

Question

La mejor manera de describir este problema es con la siguiente imagen:

Dado el conjunto discreto de puntos $A$ (mostrado en azul), deseo calcular el conjunto discreto de puntos que están contenidos dentro del casco convexo del conjunto $A$ , produciendo el conjunto $B$ (en rojo). Obsérvese que no es necesario calcular el casco convexo en sí, aunque puede ser ventajoso hacerlo.

Lo he conseguido probando si cada punto dentro del cuadro delimitador (mostrado en negro) es linealmente separable de todo el conjunto $A$ (mediante programación lineal). Sin embargo, esto es muy lento cuando el conjunto A es grande y en dimensiones más altas y siento que probar cada punto no es necesario.

Preferiblemente me gustaría que me aconsejaran sobre dónde mirar para optimizar mi búsqueda de puntos. ¿Quizás encajar un rectángulo dentro para evitar probar todos los puntos? Sólo estoy buscando ideas u otros métodos resueltos.

Para mi aplicación necesito extender esto a 3D, pero me resulta mucho más fácil resolver estos problemas en 2D y generalizar.

Answer 1

Dejemos que $n$ sea el número de puntos azules $A$ . Se puede calcular el casco convexo de $A$ en $O(n \log n)$ tiempo tanto en 2D como en 3D. El código para lograr esa complejidad de tiempo en 3D es bastante difícil, por lo que normalmente el código mucho más simple $O(n^2)$ se utilizan algoritmos en 3D. El código está disponible en varias fuentes, entre ellas mi propia .

Existen varias estrategias para evitar la enumeración de cada punto rojo $B$ (lo cual requiere un tiempo proporcional a $|B|$ ). Lo más sencillo es registrar la celda inicial y final en cada $x$ -eje-paralelo segmento de celosía dentro del casco, lo que podría lograrse intersectando el casco con cada $x$ -lattice-line.

También podrías encontrar el mayor rectángulo paralelo al eje encerrado en el casco y registrar ese subconjunto de $B$ a granel. Pero entonces tendrías que complementar este rectángulo con lo que está fuera de él pero todavía en el casco, lo que puede reducirse al enfoque de segmentos de celosía anterior.