Si "más rápido" incluye la cantidad de su tiempo invertido, la solución dependerá del software con el que se sienta cómodo y que pueda usar de manera expedita. En consecuencia, los siguientes comentarios se centran en ideas para lograr los tiempos más rápidos posibles de computación .
Si usa un programa enlatado, casi con seguridad lo mejor que puede hacer es preprocesar los polígonos para configurar una estructura de datos de punto en polígono, como un árbol KD o quadtree, cuyo rendimiento será típicamente O ( log (V) * (N + V)) donde V es el número total de vértices en los polígonos y N es el número de puntos, porque la estructura de datos tomará al menos O (log (V) * V) esfuerzo para crear y luego tendrá que sondearse para cada punto a un costo por punto O (log (V)).
Puede hacerlo mucho mejor si primero coloca los polígonos en cuadrícula, aprovechando la suposición de que no hay superposiciones. Cada celda de la cuadrícula se encuentra completamente en el interior de un polígono (incluido el interior del "polígono universal"), en cuyo caso se etiqueta la celda con la identificación del polígono, o bien contiene uno o más bordes de polígono. El costo de esta rasterización, igual al número de celdas de la cuadrícula referenciadas al rasterizar todos los bordes, es O (V / c) donde c es el tamaño de una celda, pero la constante implícita en la notación big-O es pequeña. / p>
(Una belleza de este enfoque es que puede explotar rutinas gráficas estándar. Por ejemplo, si tiene un sistema que (a) dibujará los polígonos en una pantalla virtual usando (b) un color distinto para cada polígono y ( c) te permite leer el color de cualquier píxel al que te interese dirigirse, lo has hecho.)
Con esta cuadrícula en su lugar, haga una evaluación previa de los puntos calculando la celda que contiene cada punto (una operación O (1) que requiere solo unos pocos relojes). A menos que los puntos se agrupen alrededor de los límites del polígono, esto normalmente dejará solo unos puntos O (c) con resultados ambiguos. El costo total de construir la cuadrícula y la preselección es, por lo tanto, O (V / c + 1 / c ^ 2) + O (N). Debe utilizar algún otro método (como cualquiera de los recomendados hasta ahora) para procesar los puntos restantes (es decir, aquellos que están cerca de los límites de polígonos), a un costo de O (log (V) * N * c) .
A medida que c se hace más pequeño, cada vez menos puntos estarán en la misma celda de la cuadrícula con un borde y, por lo tanto, cada vez serán menos los que requerirán el procesamiento posterior de O (log (V)). Actuando contra esto es la necesidad de almacenar las celdas de la cuadrícula O (1 / c ^ 2) y de pasar O (V / c + 1 / c ^ 2) rasterizando los polígonos. Por lo tanto, habrá un tamaño de cuadrícula óptimo c. Usándolo, el costo computacional total es O (log (V) * N) pero la constante implícita es típicamente manera más pequeña que usar los procedimientos enlatados, debido a la velocidad O (N) de la pre- proyección.
Hace 20 años probé este enfoque (utilizando puntos uniformemente espaciados en Inglaterra y en alta mar y explotando una red relativamente cruda de alrededor de 400K celdas ofrecidas por los buffers de video de la época) y obtuve dos órdenes de magnitud de aceleración en comparación con los mejores publicados Algoritmo que pude encontrar. Incluso cuando los polígonos son pequeños y simples (como los triángulos), está virtualmente asegurado de un orden de magnitud de aceleración.
En mi experiencia, el cálculo fue tan rápido que toda la operación estuvo limitada por las velocidades de E / S de datos, no por la CPU. Anticipando que la E / S podría ser el cuello de botella, lograría los resultados más rápidos al almacenar los puntos en un formato lo más comprimido posible para minimizar los tiempos de lectura de datos. También piense cómo deberían almacenarse los resultados, para poder limitar las escrituras en el disco.