How to make Polyshape from Data points

My goal is to extract polygons from a set of data Points. The points have the following characteristics:

• They are two-dimensional
• They are not stored in order

The following pictures show two examples, the points are very dense so it looks almost like they are shapes already. However, they are not.

The first polyshape should contain two regions of similiar size. Boundary() connects the two shapes, which it should not do:

Several point sets are added in the attachment. The second polyshape from the attachment should contain one or two regions. Boundary works well there.

I aim to convert all of them them to their corresponding polygons. I have tried out several ways to do so, but none of them satisfies me:

• Creating an alpha-shape requires to know how many regions there are in advance
• Using the boundary function does not separate multiple regions (see above)
• Delaunay-Triangulation can not handle concave regions or multiple regions
• The function points2contour (angular based closest-neighbor, downloadable) has its problems with lines within the shape, as seen in the second figure in the attachment
• Using the imcontour function after converting into an image seems like its not the best way. Also, the points would need to be interpolated very often and the re-conversion to polyshape seems hard.
• The auto-simplifiction of polyshape() is obviously not made for such big shapes, it creates chaotic results.

The easy way of putting a boundary over all points was my preferred option from the start, however I cant think of a robust way of cutting all the "inter-shape connectors".

Does anyone know a robust way of doing this, or maybe have hints on what to research further?

Thank you very much

[Greg Dionne]

Have you tried clustering algorithms (e.g. DBSCAN)?

Perhaps line/arc detection algorithms (Hough transform) might help here too.

[maho]

Thank you Greg, dbscan is just what I need. What a great function.

However, im still not entirely satisfied with the results of the boundary function. The higher the boundary factor (which should be more precise), the more likely it is that it creates wrong connections between points.

Do you have another hint for a better function to use? I try to avoid conversion to images.

[Greg Dionne]

There are a few out there. But much I think depends on your particular geometry. The ones you posted looked like something DBSCAN could handle. You probably have a few others which might confuse DBSCAN. Good line fitting algorithms exist (RANSAC). You probably could take a similar approach with arcs and circles that can work without images (e.g. for circular arcs, take triplets of points, finding those that share the same center). If your shapes are very densely sampled, you probably could exploit locality to help you know which points go with which shapes.

Hope this helps,

-Greg

[maho]

Thank you, but I am doing fine with dbscan.

My problem is only the boundary function, which discards many concavity features. RANSAC seems to be great for fitting polynomials, however generating polyshapes from it seems like a big effort.

For now i am sticking with dbscan for clustering, a selfmade code to remove outliers and antennas, and points2contour for the closest neighbor connections.