# Algorithm to find polygons enclosing points

I'm trying to find an algorithm that can determine the smallest possible polygons to cover a number of points.

I know how to get the convex hull around all the points, but say that the points are located on different islands, is it possible to determine that there is a gap between different groups and get separate polygons for each group?

• The answer is that only one polygon is needed; its area can be arbitrarily close to zero; and it is never unique. (One way to find a solution: there exist points on the plane from which every point in the original set is visible. Trace a non-self-intersecting route from this point out to each of the given points in turn, forming a star with extremely narrow rays.) This shows that the problem is incompletely stated: it needs a clearer, more thorough statement of the analytical objective. Feb 21, 2011 at 14:05

It sounds like you need a clustering algorithm (eg. K-means clustering) first, followed by a hull (convex hull, but a concave hull may have a smaller area but more difficult to implement).

• Feb 19, 2011 at 17:28

The "Clustr" tool that we use(d) at Flickr to generate the shapefiles derived from geotagged photos might be of use:

https://github.com/straup/Clustr

(Stackexchange is preventing me from adding more than 2 links in this post. If you search for "the shape of alpha" you can find the code.flickr blog post we did when we announced the shapefiles.)

It was designed to try and generate the contour from a constantly changing bag of points (aka photos). The actual math-y bits are here:

http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html

Clustr has some known-known bugs but mostly works, most of the time...

from a database perspective it sounds like you want to group the points on the ilands and make a convexhull on each group.

in postgis it would look something like:

``````SELECT ST_Convexhull(ST_Collect(p.the_geom))
FROM pointtable p INNER JOIN islands i ON ST_Intersects(p.the_geom,i.the_geom)
GROUP BY i.id;
``````

/Nicklas

• I don't think I was clear in my initial question. The point was that I don't know where the points are, but the will be in different distinct location, so I needed an algorithm to dynamically create clusters where the points are, not move them to defined areas. I modified the k-means clustering algorithm to search the data set for cluster centroids and then cluster. Feb 20, 2011 at 18:42
• You mean you don't know where the Islands are?. You don't have a vector representation of the islands, ok. But what do you mean by "not move them". I didn't suggest moving anything?.. Feb 20, 2011 at 19:33
• I don't know where the groups (islands) will be located, it will depend on the location of the points. So I am trying to find the smallest polygon that encloses the point locations. By move, I meant clustering points in a defined count of clusters as in the k-means clustering. Feb 20, 2011 at 22:41 