Post Project
Continue with Facebook
Continue with LinkedIn
0 views
0 appreciationsEntry content
Entry content
Entry description
Navigate a ship from point A to point B in the Northern Ocean with icebergs. The path should be as short as possible and not cross any of the icebergs (touching the iceberg is OK).
Assumptions:
All polygons are convex.
The polygons are not overlapping with each other (touching is OK).
Algorithm
Observation: the shortest route must only go through the start and end points and vertices on the various icebergs. If an iceberg is blocking a possible travel between two points, it is always shorter to go around it to its edge rather than further.
Therefore, we first build an undirected graph where each point (start, end and vertices of all the icebergs) is a node. Then, we go through each pair of nodes and figure out if a route between them is possible (not blocked by and iceberg). If the route is clear, we add an edge to the graph between the two nodes and mark its weight as the geometric distance between them.
Finally, we have a graph with all possible routes and their lengths. What is left is to use a shortest route algorithm (such as Dijkstra's algorithm) to calculate the shortest path.
Project page: https://github.com/Kasha/Iceberg-Challenge
Live Demo: http://veeca.me/iceberg/index.html
Clone: https://github.com/Kasha/Iceberg-Challenge.git
https://github.com/Kasha/Iceberg-Challenge/wiki
Assumptions:
All polygons are convex.
The polygons are not overlapping with each other (touching is OK).
Algorithm
Observation: the shortest route must only go through the start and end points and vertices on the various icebergs. If an iceberg is blocking a possible travel between two points, it is always shorter to go around it to its edge rather than further.
Therefore, we first build an undirected graph where each point (start, end and vertices of all the icebergs) is a node. Then, we go through each pair of nodes and figure out if a route between them is possible (not blocked by and iceberg). If the route is clear, we add an edge to the graph between the two nodes and mark its weight as the geometric distance between them.
Finally, we have a graph with all possible routes and their lengths. What is left is to use a shortest route algorithm (such as Dijkstra's algorithm) to calculate the shortest path.
Project page: https://github.com/Kasha/Iceberg-Challenge
Live Demo: http://veeca.me/iceberg/index.html
Clone: https://github.com/Kasha/Iceberg-Challenge.git
https://github.com/Kasha/Iceberg-Challenge/wiki
Add Response
0 Responses
Add Response
0 Responses
Please
sign in
to respond
