title: Finding edge from 2d points Python
body: <p>I have several 2d sets of scattered data that I would like to find the edges of. Some edges may be open lines, others may be polygons.</p>
  
  <p>For example, here is one plot that has an open edge that I would like to be able to keep. I would actually like to create a polygon from the open edges so I can use <code>point_in_poly</code> to check if another point lies inside. The points that would close the polygon are the boundaries of my plot area, btw.
  <a href="https://i.stack.imgur.com/AtedE.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/AtedE.png" alt="enter image description here"></a></p>
  
  <p><a href="https://i.stack.imgur.com/leHVX.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/leHVX.png" alt="enter image description here"></a></p>
  
  <p>Any ideas on where to get started?</p>
  
  <p><strong>EDIT:</strong></p>
  
  <p>Here is what I have already tried:</p>
  
  <ol>
  <li><p>KernelDensity from sklearn. The edges point density varies significantly enough to not be entirely distinguishable from the bulk of the points.</p>
  
  <pre><code>kde = KernelDensity()  
  kde.fit(my_data)  
  dens = np.exp(kde.score_samples(ds))  
  dmax = dens.max()  
  dens_mask = (0.4 * dmax &lt; dens) &amp; (dens &lt; 0.8 * dmax)  
  ax.scatter(ds[dens_mask, 0], ds[dens_mask, 1], ds[dens_mask, 2],  
  c=dens[dens_mask], depthshade=False, marker='o', edgecolors='none')  
  </code></pre></li>
  </ol>
  
  <p><a href="https://i.stack.imgur.com/SXZf7.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/SXZf7.png" alt="enter image description here"></a></p>
  
  <p>Incidentally, the 'gap' in the left side of the color plot is the same one that is in the black and white plot above. I also am pretty sure that I could be using KDE better. For example, I would like to get the density for a much smaller volume, more like using radius_neighbors from sklearn's <code>NearestNeighbors()</code></p>
  
  <ol start="2">
  <li><p>ConvexHull from scipy. I tried removing points from semi-random data (for practice) while still keeping a point of interest (here, 0,0) inside the convex set. This wasn't terribly effective. I had no sophisticated way of exlcuding points from an iteration and only removed the ones that were used in the last convex hull. This code and accompanying image shows the first and last hull made while keeping the point of interest in the set.</p>
  
  <pre><code>hull = ConvexHull(pts)
  contains = True
  while contains:
  
      temp_pts = np.delete(pts, hull.vertices, 0)
      temp_hull = ConvexHull(temp_pts)
      tp = path.Path(np.hstack((temp_pts[temp_hull.vertices, 0][np.newaxis].T,
      temp_pts[temp_hull.vertices, 1][np.newaxis].T)))
  if not tp.contains_point([0, 0]):
      contains = False
      hull = ConvexHull(pts)
      plt.plot(pts[hull.vertices, 0], pts[hull.vertices, 1])
  else:
      pts = temp_pts
  
  plt.plot(pts[hull.vertices, 0], pts[hull.vertices, 1], 'r-')
  plt.show()
  </code></pre></li>
  </ol>
  
  <p><a href="https://i.stack.imgur.com/Tqb4Q.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Tqb4Q.png" alt="enter image description here"></a></p>
  
  <p>Ideally the goal for convex hull would be to maximize the area inside the hull while keeping <strong>only</strong> the point of interest inside the set but I haven't been able to code this.</p>
  
  <ol start="3">
  <li>KMeans() from sklearn.cluster. Using n=3 clusters I tried just run the class with default settings and got three horizontal groups of points. I haven't learned how to train the data to recognize points that form edges.</li>
  </ol>
  
  <p>Here is a piece of the model where the data points are coming from. The solid areas contain points while the voids do not.</p>
  
  <p><a href="https://i.stack.imgur.com/jfOOc.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/jfOOc.png" alt="enter image description here"></a></p>
  
  <p><a href="https://stackoverflow.com/questions/32511114/strategy-for-isolating-3d-data-points">Here</a>, and <a href="https://stackoverflow.com/questions/32357699/interpolating-scattered-data-from-a-volume-that-has-empty-space">here</a> are some other questions I have asked that show some more of what I have been looking at.</p>