Sorting a 2d matrix according to the distance between each successive point.

I have a 2d matrix of points that represents a 2d slice of a 3d model. Ultimately I would like to calculate the distance of perimeter of the 2d shape.

In order to do this, I think I need to order the matrix, starting with one point and then find the closest point to that first point and then the closest point to the next point. Once the matrix is sorted, I will be able to calculate the distance between each successive points in the sorted matrix and this should give me the distance of the perimeter.

I have tried using a convex hull approach but the 2d matrix is not always convex and I would loose important data points.

Thanks in advance for any guidance.

Eoin

[Andrew Newell]

Could you please clarify what you mean by distance to the perimeter? In particular - distance of what to the perimeter? Is the location of the perimeter known in advance?

[Eoin]

Hi Andrew.

Thank you for your response and sorry about the delay in replying. I would like to calculate the distance OF the perimeter, ie the circumference. The 2D matrix represents the perimeter of a 2D shape. This 2D shape was obtained when a 3D shape was sliced through its cross section. The 3D shape was represented by a series of connected triangles and when cut, the points in the 2D matrix represent the points of intersection of the cutting plane and the 3D shape. For example, this is the 2D matrix I got when slicing a cube (100x100x100) across the z-axis at z=25. I used a slicing function called "slice_iso_data" to slice the 3D shape. The answer for the perimeter should be 400. This is a simple case but I would like to apply it to more complex 3D shapes.

0 100

0 75

0 75

0 0

100 100

100 25

100 25

100 0

100 100

75 100

75 100

0 100

100 0

25 0

25 0

0 0

Thanks again for any assistance.

Eoin

Answer 1

[Jan]

There is no simple, general and unique solution: If the points are distributed on an 8 shape, the behaviour in the center is not well defined.

[Eoin]

Thanks for your reply Jan.

When I plot the x values with respect to the y values of the 2D matrix (ie plot(x,y,'b+')), I get 8 points representing the perimeter of a square. It is only when I introduce a solid line between the points (ie plot(matx,maty,'b+-')) that the "8 shape" becomes apparent. I'm not sure why the centre lines that make the "8 shape" appear. Would you have any suggestions on how to better define the 2D shape.

Thanks again,

Eoin

Answer 2

[Brett Shoelson]

Do you have the Image Processing Toolbox? Consider using REGIONPROPS, and requesting the PERIMETER of the region.

Cheers, Brett

[Eoin]

Thanks for the advice Brett.

I do have the image processing toolbox. I'm not sure if I am calling the function correctly though. Say my 2D matrix is called "cut_surface", I am calling the REGIONPROPS function by writing:

cut_surface = REGIONPROPS(1, 'perimeter')

This returns:

cut_surface =

Perimeter: 0

Am I doing something wrong...?

Thanks,

Eoin

Answer 3

[Brett Shoelson]

Yes!

Try this instead:

stats = regionprops(cut_surface,'perimeter');
perims  = [stats.Perimeter];

That will give you (in "perims") the primeter of each ROI in your segmented (binary) image. If you have more than one ROI in your image, you'll need to make sure that you're selecting the correct element of perims--the one corresponding the shape you want to measure.

Cheers, Brett

[Eoin]

Ha ha, silly me! Sorry, I'm fairly new to the world of matlab as you've probably already guessed!

I have implemented that in matlab. For my "cut_surface" 2D matrix, "perims" turns out to be a 1x100 array with only 3 non zero values (2, 2, 19.0711). How do these values relate to the length of the perimeter in question? Also, I'm not sure if I have a binary image or not...

Thanks again,

Eoin

Answer 4

[Brett Shoelson]

Eoin, I'm not sure what those three non-zero values refer to, since I can't see your code. But if the object you are interested in has a perimeter of 400 (as you pointed out in your email to me), then it's clear that you did something wrong. Perhaps this will help:

% TRY THIS: Find the object with the largest perimeter in the % image "pillsetc.png" (ships with the IPT)

%Get/display image
img = rgb2gray(imread('pillsetc.png'));
imshow(img)
% Is it binary?
islogical(img) % (no)

% Convert to binary
% (i.e., create a segmentation mask of the objects in the
% image)
img = im2bw(img,graythresh(img));
islogical(img) % Now it's binary!
imshow(img)

% Now get perimeters
stats = regionprops(img,'Perimeter','Centroid');
perims = [stats.Perimeter]
% And, for illustrative purposes:
centroids = [stats.Centroid];
centroids = reshape(centroids,2,[])';
fprintf('You calculated the perimeters of %d objects.\n',numel(perims));

% Note that every white region is a "blob", or ROI. Some are real objects,
% others are specs. We could have cleaned them up (BWAREAOPEN, for
% instance), but that's not necessary. The values in perims correspond the
% those 22 objects. Their positions are determined by the order in which
% the first white pixel in the region is found, going down the columns,
% from left to right.

% Mark the location of the object having the largest perimeter
idx = find(perims == max(perims));
hold on
text(centroids(idx,1),centroids(idx,2),sprintf('* P = %0.2f',perims(idx)),'color','r')

Cheers, Brett