0
357
ViewsConecte los nodos a los vecinos a través de la línea de visión (línea recta)
Entonces tengo una estructura que es similar a un laberinto, pero con mucho más espacio abierto. Y para cada nodo en la estructura, me gustaría encontrar todos sus 'vecinos' (los nodos son vecinos si están en la línea de visión, es decir, no hay paredes que bloqueen la línea recta entre ellos).
Aquí hay una pequeña imagen para ayudar a explicar lo que quiero decir.
- Las líneas negras son paredes.
- Los puntos rojos son nodos.
- Las líneas azules son líneas para unir vecinos (tenga en cuenta que ninguna línea azul cruza una línea negra).
Actualmente estoy implementando un enfoque de fuerza bruta muy ingenuo y extremadamente costoso. En el que reviso cada combinación de nodos para una intersección con cualquiera de las paredes del laberinto (paredes almacenadas en 'bordes').
for n1 in nodes: for n2 in nodes: if not intersect(n1, n2, edges): n1.neighbours.append(n2) n2.neighbours.append(n1)Esto funciona bien para estructuras pequeñas como el ejemplo anterior. Pero me encantaría que esto sea escalable a estructuras mucho más grandes.
Entonces, mi pregunta es si hay alguna forma de encontrar todos los vecinos de cada nodo mucho más rápido/más eficientemente.
Salud :)
1 answers
Answer question0
Es posible que desee leer el libro de Monge sobre geometría proyectiva :)
Usemos una pantalla oclusiva alrededor de cada nodo, un cuadrado es computacionalmente fácil, un círculo necesita más matemática. La pantalla es una colección de bordes que ocultan el espacio del nodo. El método screen.occlude() toma una de sus paredes como entrada y calcula la proyección en la pantalla, y luego extiende la oclusión agregando un borde o extendiendo uno.
El resultado es que hay (¿mucho?) menos bordes de oclusión que paredes. Luego invertimos los bucles sobre los bordes y nodos de oclusión para ganar tiempo. Tenga en cuenta que el método .remove_occluded_by() solo recorre los vecinos candidatos restantes, que es una colección cada vez más pequeña. Supongo que la ganancia es de O(n^2) a O(n*log(n))
También puedes tener a cada lado del cuadrado 2 puntos que sean los extremos de la oclusión en esa dirección, posiblemente las esquinas del cuadrado virtual. Cada nodo fuera de los 4 conos de oclusión es visible. No estoy seguro de que esto gane tiempo.
for n1 in nodes: n1.occlusion = a_1_by_1_square_occlusion( centre = n1 ) for e in edges: n1.occlusion.occlude( e ) n1.neighbours = nodes - n1 # your choice n1.neigbours.remove_connected_walls( n1 ) # your choice for o in n1.occlusion.edges: n1.neighbours.remove_occluded_by( o )