nav[aria-label="Primary Navigation"] { padding: 0; & ul { list-style: none; width: 100%; display: flex; flex-direction: row; justify-content: start; align-items: start; gap: 30px; padding: 0; & li { margin: 0; } & ul li { list-style: none; } } }

Points to Polygon &quot;Footprint&quot;

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!

Vind meer berichten getagd met

Accepted answers

All comments

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.

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

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.

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.

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

bharold

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

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-1365253A756A

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

bharold

All

Please also see:

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

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

JustinPreikschas

It's probably too late for you now, but this method works for me:
http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#/Data_area_delineation_from_lidar_points/00q80000006w000000/

JoeWheaton

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

if the points are sequential, then look at ET Geowizards for tools to convert points to poly* features, if the features are not sequential and you want some of the concavity to be maintained then you are looking for a concave hull for which there is no existing tools within the Arc environment. if the pattern is something else, perhaps a illustrative picture might generate some ideas

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

JaneHogben

I have had similar problems in attempting to get the boundary of an irregular point shapefile. The following works for me:

1. Attribute points with a constant
2. Point to Raster with a small grid size
3. Raster to Polygon in Conversion/From Raster toolbox

This even captures islands or holes inside the point data. If you have problems attributing the points with a constant you could use TextPad or something that can cope with large amounts of data. Also making the raster constant may not even be necessary but I have always done it that way.

Unfortunately for me I do not have 3D or spatial analyst. I use ET Surface to create the constant raster, and Global Mapper to create the DEM which I then clip using my polygon extent (also with ET). If you having spatial or 3D you could also use the raster calculator to merge/union or add the two rasters which limits the boundary to the smallest input.

Now the biggest issue is xyz/asc to shapefile...also do this in Global Mapper!

Cheers
Jane

Z__NahideAydin

Hi!

I also tried this with the methods in ArcGIS and ArcObjects but I never got results satisfying me.

Perhaps it's too late but I found a way and I'm doing following to create a boundary polygon:

1) You have an input point cloud (for better performance --> MULTIPOINT)
2) Create a TIN --> 3D Analyst
3) Modify the TIN with your point cloud data --> 3D Analyst
4) Delineate TIN data area with a max_edge_length as parameter (this depends on the distance between your input points, e.g. I'm using 5m) and parameter "PERIMETER_ONLY" --> 3D Analyst
5) Use TIN Polygon Tag --> 3D Analyst
6) Now you should have a nice and very detailed boundary polygon around your point cloud!!!

If you have any questions please let me know!

Best regards

Thomas

I've just tried your method with the lidar data we had and it worked after couple of tries (for the maximum length part). Thank you very much you've saved me a lot of headache.

Nahide Aydin
Statistical Research Inc.

ChrisMathers

LiDAR of a tooth. Awesome. Ive always wanted to do this for my hand and make a topo of it. Talk about a neat poster for the UC this summer.

More to the point, since you can view the X and Y of each point, sort by the X field in your table and grab the first and last records. Those are the far left and far right points. Do the same on the Y field to get the top and bottom most points. Im not sure about dropping Zs below that poly because I dont do much with DEMs but that will at least give you your bounding points. I would think once you have those Zs (and averaged them?) you can just do a select by attributes to get all "Z" < AveragedMinZ. You can extrapolate a pig surface using the slope of the poly made by those 4 points using some 3D analyst tools I think. And from there, there may be a way to grab everything higher than the surface with 3D analyst or ArcScene. I havnt used 3D Analyst in 3 years so Im not sure but that sounds like something you could do. Try posting in the ArcGIS - Extentions board as well.

AndrewBar

A really appreciate everyone taking time to offer their suggestions. However, so far I haven't gotten a working solution to my problem. My problem is more complex than I thought. I will describe my problem in detail with the hopes of a creative solution from the community.

I have an unordered point feature class which derives from a 3D laser scan of a tooth (see attached pdf "tooth3d" for an arcscene view of the points). I am trying to create a DEM of the tooth surface to do topographic analysis on the shape of the tooth surface which contacts the food. My biggest huge problem is that a DEM needs 1 Z value per raster cell, so I cannot have any undercuts, or the DEM produces meaningless gibberish.

The tooth was oriented precisely at scan time such that the relevant surface is visible when viewed from the top. Thus, when this point cloud is viewed directly from above, down the Z axis (as in ArcMap, see attached jpeg "points_topdown") the boundary points of this cloud can be thought of as the vertices of a polyline Z feature class. The points which are above this polyline need to be in my DEM, the points below this polyline need to be discarded. I also need a polygon "footprint" this boundary to use as an analysis mask when I analyze the DEM.

I need help (1) efficiently identifying these boundary points and (2) subsequently eliminating points which fall below this polyline (NOTE: boundary points will not have constant Z value, so this is not trivial) and (3) constructing a concave footprint polygon to use as an analysis mask.

I realize this is a lot to ask....I can only hope someone's interest is piqued by a full description of the problem.

Thanks again for your help!

tooth3d.pdf

points_topdown.jpg

ChrisMathers

How exact does it need to fit? If you can get by with a rectangle around all of it just do a feature to envelope.

DanPatterson_Retired

similar approaches have been proposed before
http://forums.esri.com/Thread.asp?c=93&f=982&t=191468&mc=11#569228
however, they require extra cost extensions (ie 3D analyst etc)

DarshaHardy

Just been experimenting

Create a 'background' shape, say a big rectangle bigger than the extent of you points
Create a tin
Use the tin to cut a hole in the background shape to create an 'outside' polyon
Start editing the tin
Select by location, select features in the tin layer that share an edge with the 'outside' polygon
Delete those features
Save and stop editing
Should be left with a concave outlined shape
Dissolve the individual triangular polygons to be left with a single polygon

DanPatterson_Retired

if the points are sequential, then look at ET Geowizards for tools to convert points to poly* features, if the features are not sequential and you want some of the concavity to be maintained then you are looking for a concave hull for which there is no existing tools within the Arc environment. if the pattern is something else, perhaps a illustrative picture might generate some ideas

DarshaHardy

Try the Convex Hull function in ET Geowizards

It's a great piece of software that includes functionality sadly lacking in ArcView 😄

ah, oops those post above weren't there when I started writing this post

Have a look at the ET Create Tin function - you could assign all points the same height, then do a dissolve. You'll end up with a 3D shapefile but you can copy the resultant feature in a new 2D file.

Edit: just realised that's still not going to work! You would though, end up with polygons that if deleted, would give you the outline you need. Just need to identify those polygons that have no neighbours on one side - some kind of topology check?

AndrewBar

Sorry to be a nuisance.

Thanks Dan for that link. But is turns out that I misunderstood the definition of Convex Hulls....this is not exactly what I need.

Convex hulls produces the minimum convex polygon containing all the points, but if the border of the point cloud has any concavities, the convex hull will actually include areas not within the point cloud "footprint". I need a polygon that is EXACTLY the same geometry as the xy footprint of the points.

Any further suggestions will be appreciated, and thanks!

DanPatterson_Retired

http://arcscripts.esri.com/details.asp?dbid=14535
has a variety of containers including convex hull

AndrewBar

Thanks to all for the responses

clm42 - multiring buffer seems to choke on the massive number of points in my feature class. I waited for over half an hour and it wasn't even close to being finished.

jbaarda - your suggestion would work if I knew which points in the feature class represented the boundary points already....but I don't know this.

jrflannery - looks like convex hulls are exactly what I need, but as clm42 points out, I don't have access to the Minimum Bounding Geometry tool in 9.3. Anyone know how to implement this in 9.3?

Thanks again

ChrisMathers

I dont see that tool in my toolbox jrflannery. I think its new in 10.

JoeFlannery

Does this help solve your problem?

http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#//00170000003q000000.htm

JonathanBaarda

If the suggestion above doesn't work for you, you might want to take a look at this help page from esri: http://webhelp.esri.com/arcgisdesktop/9.3/index.cfm?TopicName=Writing_geometries

It is fairly straightforwards using the script examples to write the X and Y coords of the points into a polygon.

ChrisMathers

Have you tried to do a multi ring buffer on the whole thing? The rings taht overlap would merge into one poly. Do a tiny buffer so that the footprint isnt much larger than the point cloud. This will really only work if its a dense point cloud like LiDAR data. Just make the buffer = spatial resolution e.g. 1'. You may have to look at the polygons properties and delete and little holes in it.

Doe mee aan het gesprek

Aangemelde leden kunnen berichten plaatsen, updates volgen en meer. Nieuw hier? Registreer een gratis account.

Snelle Links

Community Help
Find useful guides, FAQs, and documents to help you navigate and make the most of Esri Community.