Dado un conjunto de polígonos y una serie de puntos, encuentre los polígonos que son los puntos ubicados

Question

Esta es una pregunta similar a the one here, pero creo que sería útil si puedo reformularla en términos más generales.

Tengo un conjunto de polígonos, estos polígonos se pueden tocar, se superponen y pueden tomar cualquier forma. Mi pregunta es, dada una lista de puntos, ¿cómo idear un algoritmo eficiente que encuentre qué polígonos son los puntos ubicados?

Una de las restricciones interesantes de la ubicación de los puntos es que todos los puntos están ubicados en los bordes de los polígonos, si esto ayuda.

Entiendo que r-trees can help, pero dado que estoy haciendo una serie de puntos, ¿hay un algoritmo más eficiente en lugar de calcular para cada punto uno por uno?

Answer 1

Creo que está chocando con la intuición sobre el problema (que es una percepción casi analógica) frente a un enfoque computacional que es necesariamente O (n).

Dado un plano, un polígono degenerado (una línea) y un conjunto arbitrario de puntos en el plano, ¿los puntos se cruzan con la línea o caen "por encima" o "por debajo"? No puedo pensar en un enfoque que sea más pequeño que O (n) incluso para este caso degenerado.

O bien, cada punto debería verificarse por su relación con la línea, o tendría que dividir los puntos en una estructura parecida a un árbol que requeriría al menos operaciones O (n) pero muy probablemente más.

Si fuera mejor en geometría computacional, podría ser capaz de decir con autoridad que acaba de reformular Klee's measure problem pero tal como está solo tengo que sugerirlo.

Answer 2

Si los puntos solo pueden caer en los bordes, entonces puede encontrar los polígonos en O (n) simplemente examinando los bordes.

Si no fuera así, tendría que triangular los polígonos en O (n log n) para probar los triángulos en O (n).

También podría dividir el espacio por la línea extendida desde cada segmento, observando qué lado está dentro/fuera del polígono correspondiente. Un punto está dentro de un polígono si cae en un borde o si está en la parte interior de cada borde del polígono. Es O (n) en el número de aristas en el peor de los casos, pero tiende a O (m) en el número de polígonos en el caso promedio.

Un R-tree ayudaría en ambos casos, pero solo si tiene varios puntos para probar. De lo contrario, construir el árbol R sería más costoso que buscar en la lista de triángulos.

Answer 3

El término de búsqueda de clave aquí es punto ubicación. Bajo ese nombre, hay muchos algoritmos en la literatura de geometría computacional para varios casos, desde especiales hasta generales. Por ejemplo, this link enumera varios paquetes de software, incluido el mío. (Una lista algo desactualizada ahora.)

Existe una importante compensación entre la velocidad y la complejidad del programa (y, por lo tanto, el esfuerzo de implementación). El método más fácil de programar es verificar cada punto contra cada polígono, utilizando el código estándar de punto en un polígono. Pero esto podría ser lento dependiendo de cuántos polígonos tenga. Más difícil es construir una estructura de datos de ubicación de puntos al recorrer el plano y encontrar todos los puntos de intersección de borde y borde. Consulte el this Wikipedia article para ver algunas de sus opciones.