You could use BreadthFirstSearch and explore the graph through this with a bounding box as limit. Use the LocationIndex to get a first entry node. Then you can mark all the nodes or edges.
Another approach would be on runtime: use a custom Weighting class to modify the edge weights and check if the edges are in some of your hazard regions. Here it is important to make the bounding box check very efficient, see into this discussion for some hints and links.