22
$\begingroup$

I have an accumulation of points representing a body as you can see in the image below. From this data I want to generate a list of points or a curve, which is the envelope.

ListPlot of the data

The first idea was a convex hull, but the shape of the body is not convex.

ConvexHull of the datapoints

Is there a way to extract the points at the border?

click here for the data

$\endgroup$
2
  • 3
    $\begingroup$ Related: mathematica.stackexchange.com/q/4624/862 $\endgroup$ Commented Mar 25, 2014 at 12:11
  • 1
    $\begingroup$ it may be useful to add that once you get your points on that integer lattice, you can use Picks to calculate the area of your funkalicious blob. $\endgroup$
    – PlaysDice
    Commented Mar 25, 2014 at 14:29

3 Answers 3

20
$\begingroup$

One very simple basic approach is the following (I assume you already loaded the variable spiel)

With[{m = Normal@SparseArray[spiel -> 1]}, 
 boundary = Position[m - Erosion[m, 1, Padding -> 0], 1];
 ListPlot[{Position[m, 1], boundary}, PlotStyle -> {Gray, Red}]]

Mathematica graphics

$\endgroup$
5
  • $\begingroup$ Hi halirutan. What exactly does the variable spiel store? Also, is there a way to: 1) generalise your method if the the list is real valued and 2) if the list is 3D and real valued? $\endgroup$ Commented Aug 10, 2016 at 7:39
  • $\begingroup$ 1) Extending it to real values would not work in all circumstances because at some point you need to sample the positions onto a fixed grid for the method I showed. With some adaption this might still work, but I would need to see the data give a better answer. 2) In 3D the approach is completely the same as Erosion doesn't care wether it's two- or three-dimensional. $\endgroup$
    – halirutan
    Commented Aug 10, 2016 at 12:53
  • $\begingroup$ @DanieleBinosi The variable spiel was holding the original list of points. It was provided by the original poster of the question and could be found in the Dropbox link that unfortunately doesn't work anymore. $\endgroup$
    – halirutan
    Commented Aug 10, 2016 at 12:54
  • $\begingroup$ Considering that spiel is no longer available, how I can apply this on my list of points? $\endgroup$ Commented Jun 29, 2020 at 2:42
  • $\begingroup$ @MehdiEbadi m in my code is just a binary matrix that has 1 for "inside the region" and 0 for "outside the region". Try my example with, e.g. m = Table[If[i^2 + j^2 < 1000, 1, 0], {j, -100, 100}, {i, -100, 100}] and than adapt your code accordingly. $\endgroup$
    – halirutan
    Commented Jun 29, 2020 at 8:19
28
$\begingroup$

Given that your data is on an integer grid, it may be sufficient to define a boundary point as one which does not have 4 neighbours (up, down, left, right)

boundary = Complement[spiel, Intersection @@
    Outer[Plus, {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}, spiel, 1]];

ListPlot[boundary]

enter image description here

$\endgroup$
5
  • $\begingroup$ A +1 from me because opposed to my solution, your approach doesn't destroy the index information. It seems that Erosion doesn't work with SparseArray and the moment you call Normal, you destroy the information that y runs from -100 to -33.. $\endgroup$
    – halirutan
    Commented Mar 25, 2014 at 13:40
  • $\begingroup$ +1. Can one extend this to a 3D situation? $\endgroup$
    – RunnyKine
    Commented Mar 25, 2014 at 14:58
  • 1
    $\begingroup$ @RunnyKine, sure, just put an appropriate list of neighbour coordinates into Outer. $\endgroup$ Commented Mar 25, 2014 at 17:01
  • $\begingroup$ Thanks, I did just that after looking at your code. Works fine. $\endgroup$
    – RunnyKine
    Commented Mar 25, 2014 at 17:20
  • $\begingroup$ If there were "holes" in the original list of points, this would also detect the edges of the holes. Any idea how to get rid of them, i.e. only keep the outermost edge? $\endgroup$
    – chris97ong
    Commented Dec 8, 2019 at 9:07
8
$\begingroup$

This is not really direct answer to the question because the data points are given. But, I think, still it's fun to share image processing alternative solution.

img = Import@"https://i.sstatic.net/h2Ewf.png";
ii = CommonestFilter[img, 3]

enter image description here

iii = DeleteSmallComponents@ Closing[ColorNegate@ii, 6] // ImageAdjust
iiii = Thinning@EdgeDetect[ContourDetect[iii]]

enter image description here

corners = ImageCorners[iiii, MaxFeatures -> 1000];
HighlightImage[img, corners]

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.