Create an accurate boundary around 2D point cloud horizontal plane
30 views (last 30 days)
Show older comments
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 Comments
John D'Errico
on 26 Mar 2019
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.
Answers (4)
Bruno Luong
on 23 Mar 2019
You might take a look at traveling saleman problem, there are several efficient implementation in File Exchange
1 Comment
Bruno Luong
on 27 Mar 2019
Edited: Bruno Luong
on 27 Mar 2019
I played with the data you provides (horizontal.txt) and TSP have the hard time to get the correct boundary for many reasons:
- There are a too large number of points (> 29000)
- Points seem to be inconsistent (double wall) and density varies greatly
- 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.
Matt J
on 22 Mar 2019
You can use alphaShape.
9 Comments
John D'Errico
on 24 Mar 2019
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
on 24 Mar 2019
Maybe you can examine each pair of points. If L > some length then create a triangle and see if there are points inside it
John D'Errico
on 23 Mar 2019
Edited: John D'Errico
on 23 Mar 2019
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 Comments
Image Analyst
on 23 Mar 2019
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
- skeletonize the image with binaryImage = bwmorph(binaryImage, 'skel', inf)
- find endpoints with binaryImage = bwmorph(binaryImage, 'endPoints')
- label the blobs with labeledImage = bwlabel(binaryImage).
- use a for loop to find the closest endpoints that are not on the same labeled blob
- 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 Comments
Image Analyst
on 25 Mar 2019
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.
See Also
Categories
Find more on Point Cloud Processing in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!