Dada una lista de coordenadas, ¿cuál es la forma más rápida de determinar si un punto reside dentro del grupo conectado?

Answer 1

Supongo que está preguntando acerca de la prueba ‘point-in-convex-poly’, no sobre la construcción del casco convexo.

Supongamos que construiste el casco. Entonces tiene un polígono convexo (el devanado también es fijo, por ejemplo, en sentido antihorario). Debe determinar si el punto arbitrario se encuentra dentro de él.

Versión ingenua para poli convexo: compruebe contra cada borde, como contra la línea. Si todas las líneas le dan el signo ‘izquierda’, entonces su punto se encuentra dentro del polígono convexo. Esto funciona solo para convexos y toma tiempo O (N).

La mejor versión para poli convexo utiliza la búsqueda binaria y se ejecuta en tiempo O (logN).

Otro caso es cuando tiene una solicitud poli y luego muchas solicitudes. De esta manera, puede lograr un tiempo O (1) constante para cada solicitud, realizando un preprocesamiento. Puede construir árboles BSP, árboles kd o cuadrículas de niveles múltiples. En general, cualquier tipo de estructura de datos que lo ayude a localizar rápidamente y dar el resultado lo más rápido posible. Pero ese es otro caso, creo.

Lea aquí para obtener más información: ubicación del punto

Answer 2

No hay ninguna razón para suponer que el polígono es convexo ya que esto no se indicó. Así es como puede hacer la prueba para cualquier polígono simple:

Para el punto de prueba (x0, y0), forme el conjunto de vértices con y

La exactitud del algoritmo se deriva del teorema de la curva de Jordan.

Este algoritmo se ejecuta en tiempo O (n), ya que se puede hacer en un solo bucle sobre los vértices o el recorrido del límite.

Answer 3

Algoritmos de casco convexo