Is there an effective algorithm for creating a two-dimensional concave body?

Question

Having a set of (2D) points from a GIS file (city map), I need to generate a polygon that defines the "outline" for this display (its borders). Its input parameters would be set points and "maximum edge length". Then it will output the corresponding (probably non-convex) polygon.

The best solution I've found so far was to create Delaunay triangles and then remove the outer edges that are longer than the maximum length. After all the outer edges are shorter than this, I just delete the inner edges and get the desired polygon. The problem is that it is very time consuming and I wonder if there is a better way.

Answer 1

This paper discusses the efficient generation of simple polygons to characterize the shape of many points on a plane and provides an algorithm. There's also a Java applet using the same algorithm here .

Answer 2

One of the former students of our laboratory used some applicable methods for his doctoral dissertation. I believe one of them is called "alpha forms" and is mentioned in the following article:

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

This article provides some additional links that you can follow.

Answer 3

The guys here claim to have developed an ak nearest neighbors approach to define a concave casing of a set of dots that behaves almost linearly by the number of dots. "Unfortunately, their paper seems to be very well guarded, and you will need to ask for her.

Here's a good set of links that includes the foregoing and may lead to you finding a better approach.

Answer 4

The answer may be interesting for someone else: you can apply a variation of the marching square algorithm used (1) inside the concave body, and (2) then include (for example, 3) different scales , which depend on the average density of points. The scales must be multiples of each other, so you create a grid that you can use for efficient sampling. This allows you to quickly find empty samples = squares, samples that are completely in the "cluster / cloud" of points, and those that are between them. The latter category can then be used to easily identify a polyline representing part of a concave body.

Everything is linear in this approach, no triangulation is required, it does not use alpha forms and differs from the commercial / patented proposal, as described here ( http://www.concavehull.com/ )

Answer 5

Good question! I have not tried this at all, but this iterative method would be my first shot:

• Create a set N ("not containing") and add all the points in your set to N.
• Select 3 points from N in random order to form the original polygon P. Remove them from N.
• Use some algorithm from a point in the polygon and look at the points in N. For each point in N, if it is now in P, remove it from N. Once you find a point in N that is still not in P, go to step 4. If N becomes empty, everything is ready.
• Call the point you found A. Find the line in P closest to A and add A to the middle.
• Go back to step 3.

I think it will work as long as it works well enough - a good heuristic for your initial 3 points can help.

Good luck

Answer 6

A simple solution is to walk along the edge of the polygon. Given the current edge of the bounded connecting points P0 and P1, the next point on the boundary of P2 will be the point with the smallest possible A, where

H01 = bearing from P0 to P1 H12 = bearing from P1 to P2 A = fmod( H12-H01+360, 360 ) |P2-P1| <= MaxEdgeLength 

Then you install

 P0 <- P1 P1 <- P2 

and repeat until you return to where you started.

This is still O (N ^ 2), so you want to sort your list a bit. You can limit the set of points that must be taken into account at each iteration if you sort the points, say, their supports from the city center.

Answer 7

You can do this in QGIS with this connection; https://github.com/detlevn/QGIS-ConcaveHull-Plugin

Depending on how you need to interact with your data, it might be worth checking how it was done here.

Answer 8

As a wildly accepted link, PostGIS begins with a convex hull, and then cave it, you can see it here.

https://github.com/postgis/postgis/blob/380583da73227ca1a52da0e0b3413b92ae69af9d/postgis/postgis.sql.in#L5819

Answer 9

The Bing Maps V8 interactive SDK has a concave casing in advanced form operations.

https://www.bing.com/mapspreview/sdkrelease/mapcontrol/isdk/advancedshapeoperations?toWww=1&redig=D53FACBB1A00423195C53D841EA0D14E#JS

In ArcGIS 10.5.1, the 3D Analyst extension has a Minimum Bounding Volume tool with the geometric types of a concave body, sphere, shell, or convex body. It can be used at any license level.

There is a concave case algorithm here: https://github.com/mapbox/concaveman

Answer 10

A quick approximate solution (also useful for convex hulls) is to find the borders of north and south for each small element from east to west.

Depending on how much detail you want, create an array of a fixed size upper / lower bounds. For each point, calculate which EW column it is in, and then update the upper / lower bounds for that column. After processing all the points, you can interpolate the top / bottom points for the missing columns.

It is also worth doing a quick check in advance for very long thin figures and deciding whether to load NS NS or Ew.