# 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. – whuber Feb 21 '11 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).

-
– julien Feb 19 '11 at 17:28
Thanks, I'll look into putting those two together. – jjrdk Feb 19 '11 at 18:40

At first I thought Dan's suggestion for k-means made sense, but after looking at mouse data set results on the wikipedia page for k-means, it looks like Expectation-Maximization clustering is closer to what you want.

-
Thanks for your answer, I've actually gone ahead and made a modified version of the k-means algorithm which clusters by max distance. I blogged about it here - reimers.dk/blogs/jacob_reimers_weblog/archive/2011/03/08/… – jjrdk Mar 25 '11 at 8:26
Looks great. I think EM sure would be harder to implement. It would be interesting to see if your code would work in silverlight, maybe using this TPL. – Kirk Kuykendall Mar 25 '11 at 13:35

Where pntGeometryList is your list of points, outAppendFeatureClass the featureclass the aggregation will create and buffer_radius which will determine the links between each 'externally facing' point.

-
Apologies, just got the rest of your question, which I didn't read. – Hairy Mar 24 '11 at 15:27
How do you collate your points? – Hairy Mar 24 '11 at 15:27

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. – jjrdk Feb 20 '11 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?.. – Nicklas Avén Feb 20 '11 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. – jjrdk Feb 20 '11 at 22:41