0
366
VisualizaçõesConnect nodes to neighbours via line of sight (straightline)
So I have a structure that is similar to a maze, but with much more open space. And for each node in the structure, I would like to find all it's 'neighbours' (nodes are neighbours if they are in line of sight, i.e no walls blocking the straight line between them).
Here is a little image to help explain what I mean.
- Black lines are walls.
- Red dots are nodes.
- Blue lines are lines to join neighbours (note no blue line crosses a black line).
I am currently implimenting a very naive and extremely costly brute force approch. In which I check every combination of nodes for an intersect with any of the maze walls (walls stored in 'edges').
for n1 in nodes:
for n2 in nodes:
if not intersect(n1, n2, edges):
n1.neighbours.append(n2)
n2.neighbours.append(n1)
This works fine for small structures like the pexample above. But I would love for this to be scalable to much larger structures.
So my question is if there is any way to find all the neighbours of each node much faster/ more efficiently.
Cheers :)
1 Respostas
Responde à pergunta0
You might want to read Monge's book on projective geometry :)
Let's use an occlusive screen around each node, a square is computationally easy, a circle needs more math. The screen is a collection of edges that hide space from the node. The screen.occlude() method takes one of your walls as input an calculates the projection on the screen, and then extends the occlusion by adding an edge or extending one.
The result is that there are (much?) less occlusion edges then walls. Then we invert the loops over occlusion edges and nodes to gain time. Note that the method .remove_occluded_by() only loops over remaining candidate neighbours, which is a shrinking collection. I guess the gain is from O(n^2) to O(n*log(n))
You can also have on each side of the square 2 points that are the extremes of the occlusion in that direction, possibly the corners of the virtual square. Every node outside the 4 occlusion cones is visible. Not sure this will gain time.
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 )