swaggs21

I know some of you are much better at math than I am, so I need some help.

I have the need for a concave hull algorithm for work, but I am struggling with some of the math for it. I am able to get a convex hull to work, but the concave still alludes me.

Can anyone help with this or am I out of luck? Everything I have found on the internets is based on Convex Hulls, which are fairly simple.

Thanks!!

swaggs21

Here is the pdf I am going off of, and I know these guys have successfully created an algorithm, but they have used it for profit.

http://www.iis.sinica.edu.tw/page/ji...100295-ANC.pdf

HappySnatch

What are you trying to achieve with the algorithm? Might be easier to figure something out with some requirements...

swaggs21

I want the exact outer shape of a polygon generated from a list of points (both interior and exterior points). A convex hull will give a rubber band effect type polygon, not generating the exact shape, but a concave hull will.

HappySnatch

I'm not an expert of any sort but I wanted to give this a shot.

From a logic standpoint, I think it would be best to have
each consecutive point to connecting to the previous. I'm assuming
you'd have the user plot some points on a plane that takes
2 parameters, an X and Y value.


Prompt the user to enter number of points in the polygon.

Store this value as "i". For example, 5.

Prompt user to enter the 2 values for the first point.

prompt user to enter to enter second point.

Have the program draw a line from the first point to the second.

Do this until the iteration equals the value, "i"

while(i < number of points)
{

// code to connect a straight line from the 2 points
i++;
}

then write code to connect the last point to the first.

Maybe you'd use a for loop instead of a while, not sure.

I have no idea on how to code connecting the 2 lines but I'm assuming
there would be some sort of getter method used.

swaggs21

Thanks for the reply, I guess I was a little vague with what I need.

I have a subset of 300 points, there are 26 subsets altogether (so about 7,000 points altogether). These points make up block formations inside a city, but I don't need to go down to the detail of a block, I just need the outside shape of the whole subset.

So first I need to get a convex hull, which give me a rubberbanding effect type polygon, which is a great place to start.

Once I have the convex hull, I will take the first point in the hull and then find the closest point to it in the original list of points.

If that point is not the next point or previous point and is not further away on the edge than the next point or previous point and is not on the edges to the current point in the list, then we would add it to the tail of the list in the concave hull, and then order the list of points after it goes through the previous logic for all of the points that came out of the convex hull algorithm.

I have it all in my head I think, just implementing it has been much more of a bear than one would expect.

swaggs21

I figured it out!!

I am trying to convince the president of our company to let me open source the solution, but I don't know if he is going to or not.

I would like to have other people use this if they want.