Hay un costo de ruta de solución, pero usted tendrá que código usted mismo. Aquí es lo que puede parecer cuando se aplica a cada punto de la imagen en la pregunta (un poco tosco para acelerar los cálculos):
![Figure 0]()
El negro células son las partes de los alrededores de los polígonos. Los colores, que van desde la luz naranja (corto) a través de azul (de largo), muestran la distancia máxima (a un máximo de 50 células) que se puede llegar por la línea-de-vista transversal sin interceptar el polígono de las células. (Cualquier celda fuera del alcance de esta imagen es tratada como parte de los polígonos.)
Vamos a hablar de una manera eficiente para hacer que el uso de un mapa de bits de la representación de los datos. En esta representación de todos los "alrededores" de las células poligonales se tiene, por ejemplo, valores distintos de cero y cualquier célula que puede ser "visto a través de la" tendrá un valor de cero.
Paso 1: Precomputing un barrio de estructura de datos
Primero tienes que decidir qué es lo que significa para un celular a otro bloque. Uno de los más justa de las reglas que encuentro es esta: el uso integral de las coordenadas de filas y columnas (y suponiendo que la plaza de las células), tengamos en cuenta que las células podrían bloquear la celda (i,j) desde el punto de vista en el origen (0,0). Yo nomino a la celda (i',j'), que es la más cercana al segmento de línea que une (i,j) a (0,0) entre todas las células cuyas coordenadas se diferencian de i y j en 1. Debido a que este no siempre permite dar una solución única (por ejemplo, con (i,j) = (1,2) tanto en (0,1) y (1,1) funcionará igual de bien), algunos medios para resolver los lazos que se necesita. Sería bueno para esta resolución de lazos con respecto a las simetrías de la circular barrios en las rejillas: de la negación de cualquiera de las coordenadas o de cambio de las coordenadas conserva estos barrios. Por lo tanto, podemos decidir que las células de bloque (i,j) para i >=0, j>=0, y i >= j y el uso de estas simetrías para determinar el resto de bloqueo de relaciones.
Ilustrando esta regla es el siguiente prototipo de código escrito en R. Este código devuelve una estructura de datos que será conveniente para la determinación de la "surroundedness" arbitraria de las células en una cuadrícula.
screen <- function(k=1) {
#
# Returns a data structure:
# $offset is an array of offsets
# $screened is a parallel array of screened offset indexes.
# $distance is a parallel array of distances.
# The first index always corresponds to (0,0).
#
screened.by <- function(xy) {
uv <- abs(xy)
if (reversed <- uv[2] > uv[1]) {
uv <- rev(uv)
}
i <- which.min(c(uv[1], abs(uv[1]-uv[2]), uv[2]))
ij <- uv + c(floor((1-i)/3), floor(i/3)-1)
if (reversed) ij <- rev(ij)
return(ij * sign(xy))
}
#
# For each lattice point within the circular neighborhood,
# find the unique lattice point that screens it from the origin.
#
xy <- subset(expand.grid(x=(-k:k), y=(-k:k)),
subset=(x^2+y^2 <= k^2) & (x != 0 | y != 0))
g <- t(apply(xy, 1, function(z) c(screened.by(z), z)))
#
# Sort by distance from the origin.
#
colnames(g) <- c("x", "y", "x.to", "y.to")
ij <- unique(rbind(g[, 1:2], g[, 3:4]))
i <- order(abs(ij[,1]), abs(ij[,2])); ij <- ij[i, , drop=FALSE]
rownames(ij) <- 1:length(i)
#
# Invert the "screened by" relation to produce the "screened" relation.
#
# (Row, column) offsets.
ij.df <- data.frame(ij, i=1:length(i))
#
# Distances from the origin (in cells).
distance <- apply(ij, 1, function(u) sqrt(sum(u*u)))
#
# "Screens" relation (represented by indexes into ij).
g <- merge(merge(g, ij.df), ij.df,
by.x=c("x.to", "y.to"), by.y=c("x","y"))
g <- subset(g, select=c(i.x, i.y))
h <- by(g$i.y, g$i.x, identity)
return( list(offset=ij, screened=h, distance=distance) )
}
El valor de screen(12) se utiliza para producir esta representación de este análisis de la relación: flechas punto de las células a las que inmediatamente pantalla. Los tonos son proporcionadas por la distancia al origen, que se encuentra en el centro de este barrio:
![Figure 1]()
Este cálculo es rápido y necesita ser hecho solamente una vez para un determinado barrio. Por ejemplo, al mirar a 200 m sobre una rejilla con 5 m de las células, el barrio tamaño será 200/5 = 40 unidades.
Paso 2: Aplicación de la computación a los puntos seleccionados
El resto es sencillo: para determinar si una célula se encuentra en (x,y) (en la fila y columna de las coordenadas) es "rodeado" con respecto a este barrio de la estructura de datos, realizar la prueba de forma recursiva comienzo con un desplazamiento de (i,j) = (0,0) (el barrio de origen). Si el valor en el polígono de la cuadrícula en (x,y) + (i,j) es distinto de cero, entonces la visibilidad es bloqueados allí. De lo contrario, tendremos que considerar todos los desplazamientos que podría haber sido bloqueado en el desplazamiento (i,j) (que se encuentran en O(1) tiempo de uso de la estructura de datos devuelto por screen). Si no hay ninguno que están bloqueados, hemos alcanzado el perímetro y a la conclusión de que (x,y) no es rodeado, así que deje el cálculo (y no molestar a inspeccionar los puntos restantes en el barrio).
Se puede obtener aún más información útil manteniendo el más alejado de la línea de visión distancia alcanzada durante el algoritmo. Si este es menor que el radio deseado, la célula está rodeada; de lo contrario no lo es.
Aquí está una R prototipo de este algoritmo. Es más largo de lo que parece, porque R no soporta de forma nativa la (simple) de la pila de la estructura necesaria para aplicar la recursividad, por lo que una pila para codificados, también. El real algoritmo comienza alrededor de dos tercios del camino a través y sólo necesita de una docena de líneas o así. (Y la mitad de aquellos que simplemente manejar la situación alrededor del borde de la cuadrícula, la comprobación de la hacia fuera-de-rango de índices dentro del barrio. Esto podría ser más eficaz, simplemente mediante la ampliación del polígono cuadrícula k filas y columnas en todo su perímetro, eliminando cualquier necesidad de índice de comprobación de rango en el costo de un poco más de memoria RAM para contener el polígono de la cuadrícula.)
#
# Test a grid point `ij` for a line-of-sight connection to the perimeter
# of a circular neighborhood.
# `xy` is the grid.
# `counting` determines whether to return max distance or count of stack ops.
# `perimeter` is the assumed values beyond the extent of `xy`.
#
# Grid values of zero admit light; all others block visibility
# Returns maximum line-of-sight distance found within `nbr`.
#
panvisibility <- function(ij, xy, nbr=screen(), counting=FALSE, perimeter=1) {
#
# Implement a stack for the algorithm.
#
count <- 0 # Stack count
stack <- list(ptr=0, s=rep(NA, dim(nbr$offset)[1]))
push <- function(x) {
n <- length(x)
count <<- count+n # For timing
stack$s[1:n + stack$ptr] <<- x
stack$ptr <<- stack$ptr+n
}
pop <- function() {
count <<- count+1 # For timing
if (stack$ptr <= 0) return(NULL)
y <- stack$s[stack$ptr]
#stack$s[stack$ptr] <<- NA # For debugging
stack$ptr <<- stack$ptr - 1
return(y)
}
#
# Initialization.
#
m <- dim(xy)[1]; n <- dim(xy)[2]
push(1) # Stack the *indexes* of nbr$offset and nbr$screened.
dist.max <- -1
#
# The algorithm.
#
while (!is.null(i <- pop())) {
cell <- nbr$offset[i, ] + ij
if (cell[1] <= 0 || cell[1] > m || cell[2] <= 0 || cell[2] > n) {
value <- perimeter
} else {
value <- xy[cell[1], cell[2]]
}
if (value==0) {
if (nbr$distance[i] > dist.max) dist.max <- nbr$distance[i]
s <- nbr$screened[[paste(i)]]
if (is.null(s)) {
#exited = TRUE
break
}
push(s)
}
}
if (counting) return ( count )
return(dist.max)
}
![Figure 2: Example]()
En este ejemplo, las células poligonales son de color negro. Los colores dan el máximo de la línea de visión a distancia (a 50 células) para que no las células poligonales, que van desde la luz naranja para las distancias cortas de color azul oscuro para las distancias más largas. (Las células son una unidad de ancho y de alto.) Visiblemente evidente vetas son creados por el pequeño polígono "islas" en medio del "río": cada uno de los bloques de una larga línea de otras células.
Análisis del algoritmo de
La pila de la estructura implementa una búsqueda en profundidad de el barrio de la visibilidad de la gráfica para pruebas de que una célula es no rodeado. Donde las células están muy lejos de cualquier polígono, en esta búsqueda se requerirá la inspección de sólo S(k) de las células de un radio-k circular barrio. El peor de los casos ocurren cuando hay un pequeño número de dispersos polígono de las células dentro del barrio, pero aún así el límite del barrio no se puede alcanzar: estos requieren la inspección de casi todas las células en cada barrio, que es un O(k^2) de la operación.
El siguiente comportamiento es típico de lo que va a ser encontrado. Para valores pequeños de k, a menos que los polígonos de relleno de la mayoría de la cuadrícula, la mayoría de las células poligonales será obviamente unsurrounded y el algoritmo de escalas como la de O(k). Para valores intermedios, la escala empieza a mirar como O(k^2). Como k se pone muy grandes, la mayoría de las células de ser rodeado y que el hecho de que puede ser resuelto antes de que todo el barrio es inspeccionado: el algoritmo de esfuerzo computacional con lo que alcanza un límite práctico. Este límite se alcanza cuando el barrio de radio se aproxima al diámetro de la más grande conectado no poligonal regiones en la red.
Como un ejemplo, yo uso el counting opción codificado en el prototipo de screen a devolver el número de la pila de operaciones utilizadas en cada llamada. Este mide el esfuerzo computacional. En el siguiente gráfico se traza el número promedio de pila ops como una función de vecindad de radio. Exhibe el comportamiento previsto.
![Figure 3]()
Podemos utilizar esto para calcular el cómputo necesarios para evaluar los 13 millones de puntos en una cuadrícula. Supongamos que un barrio de k = 200/5 = 40 se utiliza. Luego de unos pocos cientos de pila de operaciones será necesaria en promedio (dependiendo de la complejidad del polígono de la cuadrícula y donde los 13 millones de puntos en relación a los polígonos), lo que implica que en un eficaz lenguaje compilado, en la mayoría de unos pocos miles de simples operaciones numéricas (sumar, multiplicar, leer, escribir, offset, etc.). La mayoría de los Ordenadores serán capaces de evaluar la surroundedness de alrededor de un millón de puntos en la tasa. ( R De ejecución es mucho, mucho más lento que eso, porque es pobre en este tipo de algoritmo, que es la razón por la que sólo puede ser considerado como un prototipo.) En consecuencia, podemos esperar que una implementación eficiente de una manera razonablemente eficiente y adecuada el lenguaje C++ y Python vienen a la mente, podría completar la evaluación de 13 millones de puntos en un minuto o menos, suponiendo que la totalidad del polígono de la cuadrícula reside en la RAM.
Cuando una red es demasiado grande para caber en la memoria RAM, este procedimiento puede ser aplicado al suelo de baldosa partes de la red. Sólo tienen que superponerse k filas y columnas; tomar la maxima en el se superpone al mosaico de los resultados.
Otras aplicaciones
La "búsqueda" de un cuerpo de agua está estrechamente relacionado con el "surroundedness" de sus puntos. De hecho, si utilizamos un barrio de radio igual o mayor que la masa de agua del diámetro, vamos a crear una red de (no direccional) de captura en cada punto de la masa de agua. Mediante el uso de un pequeño barrio de radio podamos, al menos, obtener un límite inferior para la recuperación en todos los de más alta-recuperar los puntos, que en algunas aplicaciones puede ser lo suficientemente bueno (y puede reducir sustancialmente el esfuerzo computacional). Una variante de este algoritmo, que los límites de la "filtrada por" relación a direcciones específicas sería una manera de calcular recuperar de manera eficiente en esas direcciones. Tenga en cuenta que tales variantes se requiere la modificación del código de screen; el código de panvisibility no cambia en absoluto.
