Zone of Fixed Distance Around Grid

[battler.]

Hi all,

I have an arbitrary Grid of segments as shown in the image (grid shown in Black lines).  The Grid can form an enclosed polygon but may have tails (as shown).

I want to form a perimeter (shown in the blue lines) around the Grid which is a fixed distance from the outside of the Grid.

Does anyone have any ideas on how to do this?  Are there any LV tools (perhaps MathScript?) which can help?

Thanks,

Battler.

[charris]

Hello battler.!

How is the grid represented/stored in the software? Is it a series of points in an array, or is stored by some other method?

Thanks!

[Darin.K]

What you are looking for is the Concave Hull of the set of points with some buffer.  The Convex Hull is easier to find/implement and is unique.  The Concave Hull is far more difficult, and not always unique.

I'd try searching for Concave Hull and see if somebody has published an efficient algorithm, or even an inefficient one.

[battler.]

Darin,

After doing some research you're spot on.

I found some convex hull code and have started implementing it.  I haven't seen any mention of a concave hull.  I can't picture the difference in behaviour.. maybe you could explain?

I found an efficient algorithm which unfortunately relies upon the use of the QSORT function for the Point comparisons.  I'll have to modify it to calculate the angles and lengths directly.. which I'm sure will make it inefficient..

Thanks for your response.

Battler.

[Darin.K]

You will notice that the two sides of the blue region in your illustration have concave regions (ie. they curve inwards).  In the convex hull, they will be straight sections.  Imagine you are stretching a rubber band around the points, that is the convex hull.  The region you illustrate is the concave hull since the sides are "pushed in".

[battler.]

Thanks Darin.

I see what you mean.  From what I understand about implementing the convex hull, implementing the concave hull would be (as you mentioned) a lot more difficult.