convex hull algorithm

[underline]

I need a working approximate 2D convex hull algorithm. Anyone have one?

success

 

[Greenberet]

http://en.wikipedia.org/wiki/Convex_hull_algorithms ?

 

[underline]

http://en.wikipedia.org/wiki/Convex_hull_algorithms ?

i wanna test another ones instead of the 'google' ones
its for a 2d game.. need to be fast tought.

 

[harSens]

http://www.cgal.org/

 

[Raven]

I would probably try an approach with the Graham-Scan Algorithm:

Step 1: From your point quantity, you take the point P1 with minimal y-Coord ( if there are many, choose the one with the minimal x-coord )

Step2: Calculate the Angle from all edges that include P1 to the x-Axis and sort all points by the just calculated angles in a list let's call it L. So you've got a List L = { P1, P2, ..., Pn }

Step3: Pseudocode From i = 3 till n do { if( Pi from P(i-1) is reachable with an inner Angle >= 180° delete P(i-1) from L. Also delete all P(i-k) if Pi is reachable with an inner angle >= 180° }


That should work for your 2D stuff..

*edit yea I should probably mention that the result is the Convex Hull in L and btw. if there are a couple of points that have the same angle, they'll also be sorted descending by their Distance to P1.
About the performance: The point P1 is found within O(n) Sorting the Angles takes O( n*logn) and each Point is added exactly one time in L and possible deleted one time => O(n) Therefore you have a Runtime of O(n*logn) which is pretty good considering other Algorithms that take O(n^2)

 

[underline]

I would probably try an approach with the Graham-Scan Algorithm:

Step 1: From your point quantity, you take the point P1 with minimal y-Coord ( if there are many, choose the one with the minimal x-coord )

Step2: Calculate the Angle from all edges that include P1 to the x-Axis and sort all points by the just calculated angles in a list let's call it L. So you've got a List L = { P1, P2, ..., Pn }

Step3: Pseudocode From i = 3 till n do { if( Pi from P(i-1) is reachable with an inner Angle >= 180° delete P(i-1) from L. Also delete all P(i-k) if Pi is reachable with an inner angle >= 180° }


That should work for your 2D stuff..

*edit yea I should probably mention that the result is the Convex Hull in L and btw. if there are a couple of points that have the same angle, they'll also be sorted descending by their Distance to P1.
About the performance: The point P1 is found within O(n) Sorting the Angles takes O( n*logn) and each Point is added exactly one time in L and possible deleted one time => O(n) Therefore you have a Runtime of O(n*logn) which is pretty good considering other Algorithms that take O(n^2)

Cool! a new algorith!,
i will try and see what i get!

thanx for the reply!

succes

 

[Prozac]

I clicked on the this topic, thinking it was some sort of star trek thread..

Now I feel stupid, thanks.

 

[underline]

I clicked on the this topic, thinking it was some sort of star trek thread..

Now I feel stupid, thanks.

You are welcome!
LOL