# convex hull algorithm

#### underline

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

success

🌠 Staff

#### underline

##### New Member
its for a 2d game.. need to be fast tought.

#### Raven

##### Project Manager
🌠 Staff
✔️ HL Verified
💻 Oldtimer
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)

Last edited:

#### underline

##### New Member
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!

succes

#### Prozac

##### Active Member
✔️ HL Verified
💻 Oldtimer
I clicked on the this topic, thinking it was some sort of star trek thread..

Now I feel stupid, thanks.

#### underline

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

Now I feel stupid, thanks.
You are welcome!
LOL