convex hull algorithm

New Member
Joined
Apr 3, 2007
Messages
294
Best answers
0
I need a working approximate 2D convex hull algorithm. Anyone have one?

success
 
Project Manager
🌠 Staff
✔️ HL Verified
💻 Oldtimer
Joined
Nov 25, 2001
Messages
1,729
Best answers
0
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 :p 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:
New Member
Joined
Apr 3, 2007
Messages
294
Best answers
0
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 :p 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! :D

succes
 
Active Member
✔️ HL Verified
🚂 Steam Linked
💻 Oldtimer
Joined
Sep 23, 2002
Messages
1,876
Best answers
0
I clicked on the this topic, thinking it was some sort of star trek thread..

Now I feel stupid, thanks.
 

Users who are viewing this thread

Top