Answers.Body: <p>The usual way to solve this kind of problem is to construct a <em>configuration space</em>: extruding all the polygonal obstacles by sliding the polygon corresponding to the robot around them (<a href="https://www.cs.cmu.edu/~motionplanning/lecture/Chap3-Config-Space_howie.pdf" rel="nofollow noreferrer">some slides</a>).</p>
  
  <p>The exterior vertices of the configuration space can then be used as input to a path-planning algorithm, such as A*.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-21T17:37:10.530Z
Answers.LastActivityDate: 2019-03-21T17:37:10.530Z
Answers.UserDisplayName: NietzscheanAI
Body: <p>I have a 2D plane, with a fixed height and width of 10M. The plane has an agent (or robot) in the point <span class="math-container">$(1, 2.2)$</span>, and an <em>electric outlet</em> in the point <span class="math-container">$(8.2, 9.1)$</span>. The plane has a series of obstacles.</p>
  <p><a href="https://i.sstatic.net/ucSQA.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ucSQA.png" alt="enter image description here" /></a></p>
  <p>Is there an algorithm to find the shortest path between the agent and the goal?</p>
  <p>And if the point has a fixed wingspan? For example, that the space between <strong>O</strong> and <strong>N</strong> is smaller than the agent, and then the agent cannot cross?</p>
  
Tags: <search><robotics><a-star><shortest-path-problem><path-finding>
Title: How can I calculate the shortest path between two 2d vector points in an environment with obstacles?
UserDisplayName: Tlaloc-ES
ThreadText: # How can I calculate the shortest path between two 2d vector points in an environment with obstacles?
  
  (Asked by: username_0 on 2019-03-19)
  
  I have a 2D plane, with a fixed height and width of 10M. The plane has an agent (or robot) in the point $(1, 2.2)$, and an *electric outlet* in the point $(8.2, 9.1)$. The plane has a series of obstacles.
  
  [![enter image description here](https://i.sstatic.net/ucSQA.png)](https://i.sstatic.net/ucSQA.png)
  
  Is there an algorithm to find the shortest path between the agent and the goal?
  
  And if the point has a fixed wingspan? For example, that the space between **O** and **N** is smaller than the agent, and then the agent cannot cross?
  
  **Tags:** search, robotics, a-star, shortest-path-problem, path-finding
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-03-21. Score: 2 | Accepted answer
  
  The usual way to solve this kind of problem is to construct a *configuration space*: extruding all the polygonal obstacles by sliding the polygon corresponding to the robot around them ([some slides](https://www.cs.cmu.edu/~motionplanning/lecture/Chap3-Config-Space_howie.pdf)).
  
  The exterior vertices of the configuration space can then be used as input to a path-planning algorithm, such as A\*.
  
  
  ---
  
  