Algoritmo para dividir recursivamente un polígono en cuadrantes de entrada/salida: ¿Cómo se llama y dónde está el código?

Question

Tengo muchos puntos (cientos de miles) y quiero verificar cuáles están dentro de un polígono. Para un polígono relativamente pequeño (es decir, es probable que contenga solo decenas o cientos de puntos), solo puedo usar la caja delimitadora del polígono como una verificación inicial, y luego hacer una verificación regular de apuntamiento en busca de esos puntos dentro de la casilla . Pero imagine un gran (es decir, que contenga miles de mis puntos), polígono de forma irregular. Muchos puntos pasarán la verificación de la casilla delimitadora, y además la verificación de puntos en poli será más costoso porque el polígono más grande está compuesto por muchos más puntos. Por lo tanto, me gustaría poder filtrar la mayoría de los puntos dentro o fuera sin tener que hacer la verificación completa de Point-in-Poly.

Entonces, tengo un plan, y principalmente quiero saber si lo que estoy describiendo es un algoritmo bien conocido, y de ser así, cómo se llama y dónde podría encontrar el código existente para ello. No creo que lo que estoy describiendo es un quad-tree o un árbol R, y no sé cómo buscarlo. Lo llamo un "árbol recto" a continuación.

La idea es manejar estos polígonos más grandes:

Haga un preprocesado de "árbol recto", donde la profundidad del árbol RECT varía según el tamaño del polígono (es decir, permita más profundidad para un polígono más grande). El árbol RECT dividiría la caja delimitadora del polígono en cuatro cuartos. Verificaría si cada trimestre está completamente dentro del polígono, completamente fuera del polígono o ninguno. En el caso de ninguno de los dos dividiría recursivamente las subrectas, continuando de esta manera hasta que todos los rectos estuvieran completamente dentro o fuera, o se había alcanzado la profundidad máxima. Entonces, la idea es que (a) el tiempo de preprocesamiento para hacer este árbol, a pesar de que en sí mismo hará varios controles de puntos en Polygon, vale la pena porque ese tiempo está enano por la cantidad de puntos que se verifican, y (b) la gran mayoría de los puntos se pueden tratar utilizando verificaciones simples de la caja delimitadora (generalmente algunas verificaciones de estos a medida que desciende el árbol), y luego un número relativamente pequeño tendría que hacer la verificación completa de Point-in-Polygon ( porque cuando llegas a un nodo de hoja que todavía es "ninguno").

¿Cómo se llama ese algoritmo? ¿Y dónde está el código? De hecho, no parece tan difícil de escribir, pero pensé que preguntaría antes de saltar a la codificación.

Answer 1

De hecho, terminé usando un enfoque relacionado pero diferente. Me di cuenta de que esencialmente esta estructura de árboles que estaba construyendo no era más que el polígono dibujado a baja resolución. Por ejemplo, si mi árbol bajaba a una profundidad de 8, realmente eso fue como dibujar mi polígono en un mapa de bits con la resolución 256x256 y luego hacer pruebas de píxeles contra ese polígono. Así que extendí esa idea y usé una biblioteca de gráficos rápidos (la biblioteca CIMG). Dibujo el polígono en una mapa de bits en blanco y negro de tamaño 4000x4000. Luego simplemente reviso los puntos como píxeles contra ese mapa de bits. La magia es que el dibujo de ese enorme mapa de bits es realmente rápido en comparación con el tiempo que me llevaba a construir el árbol. Así que tengo una resolución mucho más alta de la que podría tener con mi árbol.

Un problema es poder detectar puntos cerca del borde del polígono, que puede incluirse o excluirse incorrectamente debido a problemas de redondeo/resolución, incluso al tamaño de 4000x4000. Si necesita saber con precisión si esos puntos están dentro o fuera, podría dibujar un golpe alrededor del polígono en otro color, y si su prueba de píxel alcanza ese color, haría el punto completo en Poly Check. Para mis propósitos, la resolución 4000x4000 fue lo suficientemente buena (podría tolerar la inclusión/exclusión incorrecta para algunos de mis puntos de borde).

Entonces, el truco fundamental de esta solución es la idea de que los algoritmos de dibujo de polígono son súper rápido en comparación con otras formas en que podría "digitalizar" su polígono.