Points to Polygon "Footprint"

[AndrewBar]

I have a large point feature class.  I need to produce a polygon that is identical to the x-y "footprint" of the points.  I could manually find the boundary points and digitizing these as the polygon vertices...but I have 10s of thousands of points so this is impractical.  Any ideas?  Using ArcMap 9.3 with all available extensions.  Thanks!

[JoeWheaton]

Your Concave Hull Estimator works great.... we almost broke down and coded this up ourselves. Glad to make good use of your helpful tool instead!:D

All

Please also see:

http://resources.arcgis.com/gallery/file/geoprocessing/details?entryID=AA23C5C6-1422-2418-8811-13652...

There is a model variable (not exposed as a parameter) that will let you play with the number of nearest neighbours for the hull boundary, controlling smoothness.

Regards

[BruceHarold]

ConCAVE hull Joe!  🙂

At some point we should make a system tool for this, the dental LIDAR community will be ecstatic (all one of them).

Cheers

[JoeWheaton]

Whoops.... yes of course conCAVE.

ConCAVE hull Joe!  🙂

At some point we should make a system tool for this, the dental LIDAR community will be ecstatic (all one of them).

Cheers

Actually, there are ton of folks who do topographic surveying who will really appreciate this tool (e.g. GCMRC & ISEMP). My students will also appreciate this.... I concur, its should definitely minimally be a system tool as part of the Minimum Bounding Geometry tool, if not its own stand-alone. It could also be usefully integrated as an option in TIN construction and/or Terrain construction (i.e. where you make it an option to automatically derive a hard clip polygon using your Concave Hull based on the input data for masspoints).

[DanLee]

Hi all,

The concept you are discussing is aggregation of individual features (points, lines, polygons) into polygons - part of generalization. The geoprocessing tool, Aggregate Polygons, was added in ArcGIS 9.2 (Data Management - Generalization); and the geoprocessing tool, Aggreagte Points, was added in ArcGIS 10. Both tools are now in Cartography - Generalization toolbox/toolset; and they require ArcInfo license. You can set the aggregation distance to control the output distance - a very large value would result in a convex shape; reducing the value would make the shape concave.

If you don't have ArcGIS 10, but you have 9.2 or 9.3 with an ArcInfo licensing, what Thomas described is a pretty good workaround (with 3D Analyst). You can also try these steps to get a close result:

- Run Buffer on the point features with a small buffer distance to create polygons from points. You can see this as if you have make your points "grown" in size.
- Run Simplify Polygon on the buffer polygons with simplification distance = 1/3 of the buffer distance to reduce the number of vertices for better performance in the next step.
- Run Aggregate Polygons with a desired distance to combine the polygons. The distance should be the value that you need to aggregate points minus 2 x buffer distance.
- Run Buffer on the aggregated polygons with a negative value of the buffer distance you used. This is to "shrink" the shape back to be tight to the input points.

Hope this helps.

Regards.

[douglaspatton]

Dan nailed the problem, what you really want is a CONCAVE HULL not a CONVEX HULL. 


As Dan suggested, a picture here would help. This is stolen from: http://ubicomp.algoritmi.uminho.pt/local/concavehull.html.
This is what a convex hull would do to a typical XYZ point cloud:

Whereas this is what you really want (a concave hull):

I don't know of any solution with ArcGIS to do this. However, the same guys who made the figures above have made a web application that does this called Concave Hull Online. Unfortunately, the application requires that your input file is just a list of x,y points (doesn't take shape files or geodatabases), and then the output is just an ordered list. However, it does create a proper concave hull. Seems like a good think to suggest to ESRI for future releases or for one of us to actually write a script for...

As whuber said (I think, though I don't understand entirely how he/she explained it), the idea described by the original poster is not well defined. The "concave hull" depicted in your second graph is one of many possibilities. There must also be a tolerance for how smooth or concave the shape should be or something describing how far apart points should be. The second "footprint" picture could also be zigzagged and still  meet the requirements described in the original post.

I had a similar problem with too many little nearby polygons that i need to buffer but the buffer goes super slow (an entire weekend in background processing on a 3ghz xeon wasn't enough...). The suggestion to use the aggregate polygon tool was perfect for me.

[JosselineLou]

It might be late for an answer but it could help so I'm sharing my thoughts.
There is a alternate way to create a polygon following the concave shape of a cloud point.

First, I used the Point to Raster tool using those parameters :
VALUE FIELD : whatever
CELL ASSIGNMENT TYPE : COUNT
PRIORITY FIELD : NONE
It will create a raster following the shape of the point cloud,

Then use the Raster to Polygon tool with the newly created raster input. (use value as field), it will create a polygon following the shape of your point cloud.

Hope this works for you,
Joss

[JosephArmbruster]

If you can write code, give this a shot:

- start with one point, P0
- obtain the next available point that is closest to P0, call it P1
- obtain the next available point that is closest to the line segment P0-P1
- now you have a triangle <P0,P1,P2>, aka polygon (you can construct a polygon from it...), call it PG
- for all remaining points:
     find the next point that is closest to your polygon PG
       cut the point into the polygon using the verts of the closest segment

Disregarding performance and degenerate cases, I think you will find this approach to be very straight-forward.