algorithm - perimetro - poligonos regulares
Dado un conjunto de polígonos y una serie de puntos, encuentre los polígonos que son los puntos ubicados (3)
Creo que estás chocando con la intuición sobre el problema (que es una percepción cuasi-analógica) frente a un enfoque computacional que es necesariamente O (n).
Dado un avión, 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 tendría que 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 decir con autoridad que acabas de replantear el problema de medición de Klee, pero tal como está, solo tengo que sugerirlo.
Esta es una pregunta similar a la de aquí , pero creo que sería útil si puedo reformularla en términos más generales.
Tengo un conjunto de polígonos, estos polígonos pueden tocarse, superponerse 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 los árboles-r pueden ayudar , 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?
El término clave de búsqueda aquí es la ubicación del punto . Bajo ese nombre, hay muchos algoritmos en la literatura de geometría computacional para varios casos, desde especiales hasta generales. Por ejemplo, este enlace 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 barriendo el avión y encontrando todos los puntos de intersección de borde y borde. Vea este artículo de Wikipedia para ver algunas de sus opciones.
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ías que triangular los polígonos en O (n log n) para probarlos en O (n).
También podría dividir el espacio por la línea extendida desde cada segmento, y observar 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 tienes varios puntos para probar. De lo contrario, construir el árbol R sería más costoso que buscar en la lista de triángulos.