How to convert a set of 2D points (multipoint) to a polygon?

I have a set of dense, irregurarly distributed 2D points ("scattered all over the place"). They can be stored in a single MULTIPOINT WKT object including "holes" or - if needed - as delaunay triangles.

How would you convert this into a polygon, i.e. one outer boundary and zero, one or more inner boundaries?

P.S. It's not the largest enclosing polygon I'm looking f开发者_运维技巧or (that would be solved by ConvexHull or ConcaveHull). I'm looking for a true polygon with the same shape as the scattered point set (including inner boundary).

---

Your question reads to me like “find a polygon which has a given set of points as vertices.” Is that interpretation correct?

If so, you can do the following: Create the convex hull of your points. Remove those points from consideration, and take the convex hull of the remaining points. Proceed in this fashion until there are no more remaining points. The intermediate result will be a sequence of convex polygones nested inside one another. You can turn them into a single polygon by connecting each subsequent pair of polygons. You connect two polygons by removing an edge from each, and connecting the resulting endpoints ”the other way round”. Some care has to be taken that these connections don't overlap anything else, but that shouldn't be too hard.

Note that there are many possible results fulfilling the specification as I read it. If you need a specific one, you'll have to give details on the criteria for that choice.

---

Use QHull: http://www.qhull.org/

It is the de facto standard for this sort of thing.