8

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?

Improve this question
1
  • 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, 2011 at 14:05

5 Answers 5

Reset to default
9

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).

Improve this answer
1
3

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...

Improve this answer
2

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

Improve this answer
3
  • 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, 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?..
    – Nicklas Avén
    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.
    – jjrdk
    Feb 20, 2011 at 22:41
1

arcpy.AggregatePoints_cartography(pntGeometryList, outAppendFeatureClass, buffer_radius)

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.

Improve this answer
2
  • Apologies, just got the rest of your question, which I didn't read.
    – Hairy
    Mar 24, 2011 at 15:27
  • How do you collate your points?
    – Hairy
    Mar 24, 2011 at 15:27
1

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.

enter image description here

Improve this answer
2
  • 1
    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, 2011 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, 2011 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.