MMM24's blog

Geometry problem
By MMM24, history, 10 years ago, In English

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 ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The optimal path will be a concatenation of 3 types of segments:

  1. Common tangents between each pair of circles
  2. Tangents to circles going throgh origin and destination.
  3. Circle arcs.

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.

→ Reply