title: How do you implement a program to find the shortest path in a 2d plane?
body: <p>If on a 2d plane there are a no. of obstacles of all possible 2d shapes(circles, quadrilaterals, triangles, irregular shapes...) then how do you implement a mechanism to find the shortest path around the obstacles? I'm considering visual c++, as it provides many graphical classes to draw such figures.</p>
  
  <p>I have come quite far</p>
  
  <p>1) Firstly i'll be using A* search(A-star) to find the path with least cost</p>
  
  <p>2) The path with the least displacement from the straight path will be considered for best path. (not really sure though)</p>
  
  <p>3) The shortest path to get around a figure, for eg from the start, is a line from that point to :</p>
  
  <pre><code>a) the farthest vertex in case of a polygon/quadrilateral
  b) a point on the circumference such that the line drawn would be tangential to the circle, in case of a circle or arc
  c) (not sure about irregular figures)
  </code></pre>
  
  <p><img src="https://i.stack.imgur.com/O7M8u.png" alt="enter image description here"></p>
  
  <hr>
  
  <p>Now coming back to the 2) point- least displacement between 2 or more paths can be determined by comparing perpendiculars from those lines to the farthest points of an object on their respective sides. (hope i've made myself understood) . </p>
  
  <p>So then- how do we draw perpendiculars to the straight path?  <img src="https://i.stack.imgur.com/8sNp7.png" alt="enter image description here"></p>
  
  <p><em>x1,x2,y1,y2,k and l</em> are known. We just have to find <em>a,b</em>.</p>
  
  <p>Slope of the straight path * slope of it's perpendicular = -1</p>
  
  <pre><code>=&gt; (y2-y1)/(x2-x1) * (b-l)/(1-k) = -1
  hence, b = [(x1-x2)/(y2-y1) * (a-k)] + l
  </code></pre>
  
  <p>I've imagined that by using pythagoras theorem we can find the other equation in terms of the co-ordinates. The lengths of each line can be found by this way: 
      dx = x1-x2
      dy = y1-y2
      dist = sqrt(dx<em>dx + dy</em>dy) </p>
  
  <p>And then by solving these 2 eqns we can find the correct values of <em>a,b</em>.</p>
  
  <hr>
  
  <p>I can't think of anything further- any ideas or suggestions? </p>