# Create an accurate boundary around 2D point cloud horizontal plane

57 ビュー (過去 30 日間)
Alexandru Mihai LAPADAT 2019 年 3 月 22 日

Hello everyone,
I am dealing with creating an accurate boundary (concave hull) of a point cloud. I want to create the a polygon around it and compute the center of gravity using centroid function. None of the threshold values (0-1) give me a good result. I add here a resulting boundary colored in blue and the point cloud set colored in red. Is there any better approach using another function rather then boundary+polyshape??

#### 6 件のコメント

Alexandru Mihai LAPADAT 2019 年 3 月 26 日
Here you have the point cloud. I tryed also TSP and did not work. After applying it and plotting the resulting sorted XY coordinates they were not correctly linked with a line.
Matt J 2019 年 3 月 26 日
I tryed also TSP and did not work.
Are you going to show us what you did and what you got?
John D'Errico 2019 年 3 月 26 日
That it did not work just means you did not properly formulate the Traveling Salesman Problem correctly, or solve it correctly, or correctly interpret the results, because it WILL work.
A better more useful way to approach this would have beento provide your data, show what you tried, then state why it is that you think it did not indeed work.

サインイン to comment.

### 回答 (4 件)

Bruno Luong 2019 年 3 月 23 日
You might take a look at traveling saleman problem, there are several efficient implementation in File Exchange

#### 1 件のコメント

Bruno Luong 2019 年 3 月 27 日
I played with the data you provides (horizontal.txt) and TSP have the hard time to get the correct boundary for many reasons:
1. There are a too large number of points (> 29000)
2. Points seem to be inconsistent (double wall) and density varies greatly
3. The data you provide does not match your plot in the question
I think you might need to preprocess the data to facilitate the TSP algorithm.
For the record here is an old post that show TSP can solve such problem with reasonable data

サインイン to comment.

Matt J 2019 年 3 月 22 日
You can use alphaShape.

#### 9 件のコメント

darova 2019 年 3 月 23 日
convhull() ?
John D'Errico 2019 年 3 月 24 日
A convex hull will fail because the domain is not convex, so the area enclosed will be too large. Note that it was already requested to be able to improve this result to be better than a convex hull.
darova 2019 年 3 月 24 日
Maybe you can examine each pair of points. If L > some length then create a triangle and see if there are points inside it

サインイン to comment.

John D'Errico 2019 年 3 月 23 日

As I thought about your problem, there is a simple solution. This is a TSP - a Traveling Salesman Problem. You want a closed solution, so the first and the last points will be the same. What I don't know is if those lines are thinned out. You want single pixels around the perimeter of that boundary, not multi-pixel thick lines. But given that, then just use a TSP solver. There are a few to be found on the File Exchange. Try this one, for example:

#### 0 件のコメント

サインイン to comment.

Image Analyst 2019 年 3 月 23 日
I'm guessing that you generally like the red shape (rather than the black outline shape) but you want the ends of the red pieces to be connected to the closest other piece so that the curve/boundary is closed. So you want "edge linking" (Google it).
One way is to
1. skeletonize the image with binaryImage = bwmorph(binaryImage, 'skel', inf)
2. find endpoints with binaryImage = bwmorph(binaryImage, 'endPoints')
3. label the blobs with labeledImage = bwlabel(binaryImage).
4. use a for loop to find the closest endpoints that are not on the same labeled blob
5. connect these endpoints with imline (attached demos might help)
Now all your end points will have a line connecting them to the nearest other piece. Now you can simply use imfill to make the shape solid, then use bwboundaries to get a list of (x,y) coordinates around the entire shape.
binaryImage = imfill(binaryImage, 'holes');
boundaries = bwboundaries(binaryImage);
The only steps that are slightly more than trivial are steps 4 and 5 but I'm sure you're smart enough to handle it. If not, let me know. Steps 1-3 area all one liners that I've already given you.

#### 7 件のコメント

Alexandru Mihai LAPADAT 2019 年 3 月 24 日
Well I need to sort them in order to throw them in polyshape function. But for this I need to go back to the point-cloud xy system after sorting them as binary points. Do you have any suggestion how to do this? I found some explanation in the following link: https://www.mathworks.com/matlabcentral/answers/50787-convert-an-image-pixel-coordinate-to-physical-coordinate?s_tid=answers_rc1-3_p3_Topic. But it did not work that well for me.
Alexandru Mihai LAPADAT 2019 年 3 月 24 日
Hello Image Anayst
I did not find the solution on my problem with converting back to real point cloud coordinate system. Could you please help me with this. I also tryed to use the point2contour function directly on the x,y point cloud but did not give a great result. I really don't know how to solve it :(
Image Analyst 2019 年 3 月 25 日
I thought you had the image in red. It appears now you just have a collection of point locations, not an image. To do anything with my suggestion, you'd have to create an image.
Again, you might want minimum perimeter polygon - I don't know.

サインイン to comment.

サインイン してこの質問に回答します。

Translated by