title: Line detection in 2D point cloud
body: <p>I am developing a larger system for navigation and positioning of automated guided vehicles and have stumbled upon a problem. When developing a map, the important part is finding the walls. The navigation is done using a LiDAR unit.</p>
  
  <p>An example "image" of that the sensor sees is as follows:
  <a href="https://i.stack.imgur.com/DqL8l.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/DqL8l.png" alt="enter image description here"></a></p>
  
  <p>And the wanted output is something like this:
  <a href="https://i.stack.imgur.com/ZAgyP.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ZAgyP.png" alt="enter image description here"></a></p>
  
  <p>I have looked alot at the Hough transform and the RANSAC algorithm but the Hough transform as from what I know is used on images which is not optimal for my case and the RANSAC is not great for finding multiple walls in sparse data.</p>
  
  <p>The data that was used in this specific example can be found in this link: <a href="https://drive.google.com/file/d/1EnSOr2FYjIdqG1RdFgTkgsoEhVcG7Tl_/view?usp=sharing" rel="nofollow noreferrer">https://drive.google.com/file/d/1EnSOr2FYjIdqG1RdFgTkgsoEhVcG7Tl_/view?usp=sharing</a>
  Where the two arrays in the file represent x and y coordinates where elemets correspond by index.</p>
  
  <p>Im developing in python but I have no issue to write the algorithm myself if anyone knows a suitable one that is not available in a package or so.</p>
  
  <p>Thanks in advance, Jakob</p>