title: R: Find a shape from a point cloud
body: <p>I have a point cloud like such below</p>
  
  <p><a href="https://i.stack.imgur.com/YnAeG.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/YnAeG.jpg" alt="enter image description here"></a></p>
  
  <pre><code>df &lt;- data.frame(x=c(2,3,3,5,6,2,6,7,7,4,3,8,9,10,10,12,11,12,14,15),
                y=c(6,5,4,4,4,4,3,3,2,3,7,3,2,3,4,6,5,5,4,6))
  plot(df,xlab="",ylab="",pch=20)
  </code></pre>
  
  <p>Think of them as gps coordinates of movement by an animal. I would like to find the spatial area covered by the points (animal). The most obvious solution is a convex hull which produces this:</p>
  
  <p><a href="https://i.stack.imgur.com/fABCW.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/fABCW.jpg" alt="enter image description here"></a></p>
  
  <pre><code>df1 &lt;- df[chull(x = df$x,y=df$y),]
  polygon(x = df1$x,df1$y)
  </code></pre>
  
  <p>But this is not the result I am looking for. The movement area is not a closed geometric shape, but rather a boomerang kind of shape. The convex hull covers a lot of area not covered by the animal thereby overestimating the area. I am looking for something like this:</p>
  
  <p><a href="https://i.stack.imgur.com/Nyw8R.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Nyw8R.jpg" alt="enter image description here"></a></p>
  
  <p>Of course, this is a mock dataset to give an idea. The original datasets have lot more points and varying geometries in point cloud. I was thinking along the lines of DBSCAN or minimum spanning networks, but they don't quite work.</p>
  
  <p>I am not sure how to describe this geometrically or mathematically. If anyone has any ideas on how to approach this (even if it's not a full solution), I would very much appreciate that. If anyone has a better title for this question, that would be nice too :-)
  Thanks.</p>
  
  <p>Update ----------------------------------------------------------------</p>
  
  <p>Plot of (minimum spanning tree) MST. I think this might be in the right direction.</p>
  
  <pre><code>library(ape)
  d &lt;- dist(df)
  mstree &lt;-mst(d)
  plot(mstree, x1 = df$x, x2 = df$y)
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/uDCeI.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/uDCeI.jpg" alt="enter image description here"></a></p>