Ask A Cartographer

Concave Hull

November 24 2010 | 5 comments
Categories: Map Data

I have a point dataset with about 17,000 points. I'm looking to create a footprint of the outer most points. I see one can create a convex hull, but my points form an irregular shape and the convex hull doesn't follow the path of the outer most points. Is there a way to do this?

I've attached a jpg that shows the result of a convex hull.

Thanks for your help.

Mapping Center Answer:

I presume you are using the Minimum Bounding Geometry tool in the Features toolset in the Data Management toolbox in ArcToolbox. If you read the online help for this tool, you will see that the hull (polygon defining the extents of the input features) will always be convex, as shown in your example. You do not have the option to create, what you call a concave hull.

Instead try using the Feature Outline Mask tool in the Masking toolset of the Cartography toolbox in ArcToolbox. With this tool, along with BOX and CONVEX_HULL, you can also specify:

EXACT_SIMPLIFIED —A generalized polygon representing the exact shape of the symbolized feature. Polygons created with this method will have a significantly smaller number of vertices compared to polygons created with the EXACT method.

EXACT —A polygon representing the exact shape of the symbolized feature.

This would not work in all cases, but given the nature of your data, I think it will work for you.  This is why -- given the symbology you are using, your data are clustered so close together that the mapped features coalesce into a contiguous area.  It is important to understand that the Feature Outline Masks tools will create a mask polygon around the SYMBOLIZED features, so if you used a smaller point symbol or a larger reference scale (so that you zoomed in on the area) then you would start to see pockets within the polygon.

Once you have used the Feature Outline Masks tool, use the Dissolve tool to create one or a few polygons that represent the extent of the distribution.

Note that this solution, unlike the Minimum Bounding Geometry solution, provides a polygon that extends OUTSIDE the actual extent of your point features and instead represents the extent of the SYMBOLS used to map your point features.

Below is an example using census data for the places in Michigan.

25M Points

The point distribution mapped with a 4 pt symbol at a map scale of 1:25,000,000 (this looks more like the coalescing points in your attachment.)

25M Masks

The output from the Feature Outline Masks tool for the mapped features above.

25M Dissolve

The results after using Dissolve.

5M Points

The point distribution mapped with a 4 pt symbol at a map scale of 1:5,000,000 (notice all the pockets within the mapped distribution.)

25M Masks

The output from the Feature Outline Masks tool for the mapped features above.

5M Dissolve

The results after using Dissolve.

This is the solution that was offered in the comments below by Kyaw Naing Win. This inventive solution uses TINs.

Concave Hull with TINs

Concave Hull posted by Kyaw Naing Win on Dec 2 2010 6:15PM
Your points remind me of topographic surveying using totalstations and thus TIN creation in the survey software. In the survey software there are some control over tin appearance. I can control narrow triangle that usually happen along the edge as in your case. So I try with ArcGIS 3D Analyst. But there is no such control in the creation of TIN. I convert TIN to polygons using command line (TinTriangle input_tin output_shp). Then I deleted narrow triangle manually. Finally I dissolve the polygons into one.
Pls see the attach.
Concave Hull (fail attachment) posted by Kyaw Naing Win on Dec 2 2010 6:44PM
I cannot find any button to attach my result.
No attachments to comments posted by Aileen Buckley on Dec 7 2010 12:56PM
Right now you cannot attach a file to a comment. If you want to send it to us directly, so that we can post it for you, you can either submit a new Ask a Cartographer question and add the attachment there or you can use the Contact Us link at the bottom of any page on Mapping Center and send us the attachment in that email. We look forward to seeing your results!
Graphic is now attached posted by Aileen Buckley on Dec 7 2010 10:31PM
The graphic is now attached showing how Kyaw Naing Win was able to use TINs to find the solution!
Alternative method for concave hull posted by Charlotte Peters on Jan 27 2012 4:01PM
Hi, I discovered an alternative method to generating a concave hull that takes minutes to process. I used spatial analyst for some of my steps, but there may be other tools or extensions that could do the task in place of spatial analyst. This method is not exact, meaning that the polygon hull will not intersect the outermost points, but it may still be suitable for some applications. I will try to get an attachment submitted, but the steps are outlined below:
1. convert points to raster using spatial analyst>>convert>>features to raster (3m cell size worked best for me at creating a continuous surface and following the outline of the outer points)
2. calculate hillshade from raster using spatial analyst>>surface analysis>>hillshade (used 0.5m cell size to try and reduce amount of pixelation along edges)
3. convert the hillshade to a feature polygon using spatial analyst>>convert>>raster to feature (leave generalize lines check)
4. the new polygon file will need to be dissolved but first create a new field in the resulting polygon shapefile
5. enter any value in the new field for all records, it doesn't matter what value you use just make sure the value is the same for all the records
6. dissolve the polygon shapefile based on the new field
7. depending on the cell size used in previous steps, there may be interior doughnuts that need to be deleted manually, you can stop here or continue to get a smoother looking outline
8. smooth the polygon outline using arctoolbox>>generalization>>smooth polygon (PAEK algorithm worked for me, trial and error for the tolerance distance)
Since the intent of this exercise was to just get an outline of the points for visual display, I didn't choose process settings based on their analysis value or standard analysis practices. I chose settings that produced the correct visual output. The entire process took about 10 minutes for a file with over 300,000 points. Using other methods, the process took hours and sometimes crashed.

If you would like to post a comment, please login.

Contact Us | Legal | Privacy |