Problem with creating a polygon based on points using Convex Hull

Question

I've successfully created polygons from points using the ConvexHull function in SQL Server 2008.  But I'd like to have a 'better' shaped polygon created.  For instance, I have points that are distributed in such a way that if you manually drew a line around them, it would form a "L" ( a fat "L" actually).  

But the convex hull function produces a polygon the resembles a triangle.  That is, it's connecting the points from the top of the "L" to the points at the lower right of the "L".

Is there a solution to have the function "hug" the points more closely?

My purpose in this is that I have another set of points that are in the area between the top of the "L" and lower right of the "L" and when these points are 'connected', I get the two shapes overlapping. I'd like to avoid that overlapping.

Thanks for any help on this.

Jay

 

Answer 1

Hi Jay,

The subject of creating "concave" hulls around a set of points has been discussed a couple of times in this forum. You might want to check out:

http://social.msdn.microsoft.com/Forums/en-US/sqlspatial/thread/43e2f7da-3614-4887-80a5-52e7e337943f

http://social.msdn.microsoft.com/Forums/en-US/sqlspatial/thread/7b7898ea-7a5c-42fe-a787-a1042708e266

 

The short answer is that there is no easy way to define a concave hull, for the simple reason that many such shapes exist... (see my reply in the second thread above for a graphic example).

It's certainly possible to write your own method using the SqlServer.Types.dll functions - perhaps join each point to the two next closest points as calculated by STDistance(), or use Richard's suggestion in the post above to buffer each point until they just touch, and then reduce them again. However, there's quite a lot of trial and error" involved in both these approaches.

Do you want to create a generic re-usable function for creating concave hulls, or do you simply want to create a one-off polygon from this particular set of L-shaped points?

---

Beginning Spatial with SQL Server http://www.apress.com/book/view/1430218290

Answer 2

Yes, I need to create a re-usable function. 

The L-shaped example was just one of the many shapes that may exist.  Others could be a "U" shaped polygon, etc.

I'll look into the concave discussions too.

Thanks for the input.