Finding A connecting region between two unconnected hulls

Hi, I have many convex hulls in 2D that represent different shapes. The hulls are not connected or overlapping, but some sides of them are very close to other hulls. I want to write something that can determine whether a part of the hull is close enough to another hull, and merge the two parts of that polygon so they're connecting, but maintain two separate polygons. Attached is an image of an example where there are two hulls next to each other. The goal would be that the place where they're very close I could have them share points in that area between them.

The hulls also can be somewhat odd-shaped, and the area where they're close may have several points in one hull, and not many in the other, so essentially you'd have many lines from one polygon and just one from the other, but the goal would still be to share that area. Thanks!

[Anuruddha Jayasuriya]

Hi Cole Smith,

Are those hulls in 2D generated randomly? Or otherwise, how did you make sure that the hulls (many of them) didn't overlap with each other?

Thank you.

Answer 1

[Image Analyst]

What do you have? Images or just coordinates? If you have coordinates, use poly2mask() to turn them into an image. Then, once you have an image, use imclose() to do a mrophological closing operation to join the two regions. The use bwboundaries() to get the outlines. If you want only the convex hull coordinates, then pass the results of bwboundaries() into convhull(). imclose might change the shape of non-smooth parts of the boundary slightly but it looks like you shouldn't have anything to worry about with the shapes you gave.

Another option is to use activecontour(). A demo is attached.

[Cole Smith]

Thanks, I'll give that a shot. I only have points, which were the output of convhull().

[Cole Smith]

Just out of curiosity, how will bwboundaries find the line between them? I'm probably not understanding the manual, but it sounds like it just finds the outline after the two ate merged.

At the end I still wanted 2 polygons, but sharing some points.

[Image Analyst]

It won't. The algorithm I gave will "merge the two parts of that polygon so they're connecting" just like you asked for. You will end up with a single, merged region, not two regions that have a narrow pathway between them.

[Cole Smith]

Sorry, I specified what I was trying to do incorrectly. I still am looking for two separate polygons, but sharing a region they're connected in. I'll update the problem description.

[Image Analyst]

Attach a desired output image. For example, when two points on different polygons are within a certain specified distance, do you want to add a point that is the average to both vertex lists? Or do you want to replace that point with one of the vertices, or with the average location of the two vertices? In any event, this is simple to do with a for loop and the Pythagorean theorem.

[Cole Smith]

Yes, exactly. Ideally it would be for that for every point P in polygon A within distance D from polygon B, a new point would be created as point P2 that's the middle point of those two. I could also just use a point from another polygon, but that won't be as accurate since the number of points in the polygon can vary, and there may not be a point in B close to one in A, even though a line from two points in B is right next to A. Either way will work for this. I think I need to find a function that calculates the minimum distance from a point to a polygon, then gives that point on the polygon. I can search fileexchange for something like that, but I wasn't sure if a function already existed. I can draw an image if needed, but I think you nailed exactly what it is I'm trying to accomplish.

[Cole Smith]

Or perhaps on more thought on this...if I find a series of points in polygon A and a series in polygon B that are all within some small distance of the other polygon, I could do a voronoi diagram on just those points and pick out the part of the voronoi that runs through them.

[Image Analyst]

I don't see how voronoi would help since you want to retain most the sides completely unaltered. The algorithm is simple enough, but rare enough that there is no built in function for it. You can easily write your own. Let us know if you can't.