![]() If you are expecting a lot of shortest path queries it may be worth it to use an algorithm that calculates all shortest paths and calculate the shortest paths between all pairs of nodes in the visibility graph in advance. Dijkstra's Algorithm will do the job just fine. Then you can use a single source weighted shortest path algorithm. You have to add your start and end point to the visibility graph. If the line does not intersect one of the polygons it is an edge in the visibility graph. The you draw a line between all pairs of vertices an see if that line intersects the interior of a polygon. Vertices on the convex hull are the nodes of the visibility graph. Vertices not on the convex hull do not need to be part of the visibility graph. First you calculate the convex hull of your polygons. The brute force way to build that is quite simple. The graph you need for routing in a plane with polygons as obstacles is the visibility graph. is probably better suited for the problem described here and should be easier to implement. If not go to step 1 and remember the length between the start point an the vertex that is now the new start point.Īpproach 2. If you intersect with another polygon go to step 2 with that polygon. Iterate through the vertices of the polygon to the left and to the right side until a line between the vertex and the endpoint does not intersect with the interior of the polygon or until the direct line between the vertex intersects with another polygon.If it does intersect take the intersecting segment of polygon which is closest to the start point.If it does not intersect this is your shortest path. See if it intersects the interior of at least one polygon.Draw a line between the start point and the endpoint.If you have to calculate a lot of shortest paths and the polygons stay the same approach 2. is better if you can not keep internal state between the times your algorithm is used. You can build a graph over all your polygons and then find the shortest path within that graph.Īpproach 1. You can either find the shortest path using just the polygons that are relevant using a spatial index like an R-Tree for your polygons to speed things up. There are two approaches you can take to solve the problem: While not often discussed in a GIS context, visibility problems are very popular and well documented in computational geometry. What helped me most was realizing that shortest path problems in a plane avoiding obstacles can be thought of as visibility problems. I once implemented an algorithm that calculates a polygon that includes the area of a plane (with polygonal obstacles) that can be reached in a certain distance.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |