Hi all. i was thinking about this problem : we have a person located at the origin of plane and we are given a point wich is the destination also we are given a number of lake , each lake is defined by a center and a radius . wich is the minimum distance needed to go from the origin to the distination . i managed to solve the points of intersection between the line formed by the 2 points and the circles however i'am asking how can i calculate the distance arround it ?
The optimal path will be a concatenation of 3 types of segments:
You can build the corresponding graph on the tangent points (it will have O(n2) vertices and edges) and find the shortest path in the graph.