Блог пользователя MMM24

Geometry problem
Автор MMM24, история, 9 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить