Two-Dimensional Concave Hull?

[genemroz]

I have seen Rick Wicklin's blog entry on creating two-dimensional convex hulls.  Is there a way within SAS to create two-dimensional concave hulls?

Thanks in advance for any guidance you can provide, 

Gene

[Rick_SAS]

There is no built-in method for creating a concave hull.  You would have to program it yourself.

See GitHub - Liagson/ConcaveHullGenerator: Concave hull for C# (Comes with a Unity demo)

which is based on this paper: http://www.it.uu.se/edu/course/homepage/projektTDB/ht13/project10/Project-10-report.pdf 

Are you proficient in SAS/IML programming? If so, I can move this thread to the SAS/IML Community. Otherwise, I will leave your question here. Personally, I suspect an IML implementation is the best way to solve this problem.

[genemroz]

Thanks, Rick, for your response and for the links.  They are helpful.

Unfortunately, I am not proficient with SAS/IML Programming.  But this would be a great topic for a future Do Loop post.  I hope you will consider it.

Thanks again,

Gene

[Rick_SAS]

Can you say something about your use case? What are you trying to accomplish? What is the scientific question that you are trying to answer? Since a concave hull is not unique, what criteria do you intend to use to determine which concave hull is appropriate for your data?

[genemroz]

Thank you for your response.

My particular use case would fall in the category of data visualization.

I am using Proc Optmodel to optimize the pointing of multiple cameras so as to optimize sky coverage for the detection of meteors.

I wish to visualize the field of view of the individual cameras at selected altitude levels. The shape of the FoV at any given altitude is a complex shape affected by lens distortion, atmospheric extinction and the presence of local obstructions (trees, buildings etc.)

Proc Optmodel operates on a dataset that holds a 3d matrix of x,y,z cartesian coordinates of the interior of each possible field of view of each camera. It finds the optimal orientation of the cameras that covers the maximum volume of sky with at least 3-camera coverage.

I was hoping to find the polygon described by the concave hull of the interior x,y coordinates of the optimal orientations at a selected z. Then I could use Gproject to transform the polygon from x,y and fixed z to Lat/Long and use Gmap in conjunction the SAS Annotate Facility to visualize the outline of the polygon of the optimal orientations over a map of the coverage region.

I understand that concave hulls are not unique but I don't think that's very critical in this application as the shape of the perimeter is not terribly convoluted but is smoothly concave in some regions. I hope that's somewhat clear.

Writing this response has sparked an idea in me to plot the interior points that I already have instead of trying to find the concave hull. I'll try this.

Thanks for your interest,

Gene

[Rick_SAS]

> Writing this response has sparked an idea in me to plot the interior points that I already have instead of trying to find the concave hull. I'll try this.

Exactly. It seems like you could generate a dense grid of points and, for each point, mark it as to whether it is in the field of view for some camera.