I need a working approximate 2D convex hull algorithm. Anyone have one?
Written by MM. Posted at 7:01 pm on June 2nd, 2009
23 comments.
Post a comment.
Status Updates
- Hey, we searched all over the database, but we couldn't find any status updates. Have you posted any yet?
Believe it or not, I was actually looking into this once long ago. My method was a simple sweep. No algorithm unfortunately, but I wanted a method that would eliminate the need for scanning of all the points. It was almost like blind wrapping. Inside a circle, your angle along the edge will always be less than 180. The more points you have within a circle, the more you multiply n-angle if you have a perfectly symmetrical shape. That was what my first test was going to be. First to find a square, then a pentagon and up and up. Anyway, the next test was with asymmetrical. Even if the angles are not equal to eachother within a circle, their sum is still the same. Basically in the end, if a wrong line was drawn between and edge point and an inner point, a simple check of the sum and/or angle would determine if it was correct. This is still tricky. A computer program designed to do this could also perhaps draw a spiral – trying to correct the path and end in error.
Wish you would have asked this years ago lol. I’ve forgotten so much. I may still be able to offer something hopefully, I just have to find my stuff.
Now, that I think of it, if you ask your program to look for the highest degree per point in relation to the path of the last 2, and also the highest number of points you can find (with the highest degree in relation to the last paths)… That should solve the quick and dirty. The hardest part will be to set the start point and assigning the direction. When you get back to the start point, a check of sums will help determine correctness.
Wow… Now I remember why im going into networking and not programming
Hurrr durrr wats a convex hull?
>Hurrr durrr wats a convex hull?
That
http://en.wikipedia.org/wiki/Convex_hull_algorithms#Jarvis_march
Snow: What shapes does that solve? Only squares, pentagons etc. ? I need different kind of shapes.
check out the Cormen book http://books.google.com/books?id=NLngYyWFl_YC&printsec=frontcover&dq=cormen Chapter 33 or Sedgewick book ,they both have convex hull algorithm in both pseudo-code and C code.
do you think approximate would be faster , that’s why you’re asking for approximate?
Check out http://citeseer.ist.psu.edu/cs?cs=1&q=convex+hull+algorithm
You should find articles describing what you need
Good luck and let us know what algorithm you’ve chosen and more importantly why
I need an approximate algorithm were you can define the level of approximation.
I’m using this one currently: http://softsurfer.com/Archive/algorithm_0110/algorithm_0110.htm
But it gives me weird results. That’s why I’m asking if anyone has a WORKING one.
Mine would be able to solve any kind of polygon. However, I have to find my stuff in order to show it and be able to help with producing an algorithm. The squares, pentagons, etc would be to test the algorithm. I’m not a mathematician however, and most likely the current existing algorithms out there are more efficient. Also, what I was talking about with sum of angles – all you have to remember is this simple bit – 180(n-2). n = number of vertices. If your shape is a “C” or a star for instance, the sum will still be the same as any other polygon with the same number of angles/vertices. You can also pull tricks, where it’s like inverse calculation. Rather than counting reflex angles, you count only acute/obtuse. So a star for instance would have half the sum of a polygon with 10 points (rather than 1440, the sum is 720). This helps tremendously. This is as much help as I can give atm, I know you need something that’s working.
If I have some time later today, I may try my hand at this for you. Don’t really want to waste your time becoming annoyed at reading my explanations lol.
Eh dude, I was always keeping that stuff in my cupboard, but I can’t find it right now. ;/
tring to find something for u!
Originally Posted by Raven View Post
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)
obs: you can find this guy in esforces.com
success
Michal , define a metric called “error” , you need to know what error your approximation stays in. Any rigorously written algorithm has this metric , if it’s an approximation.
Make test-cases , write code to visualize the true solution , your solution and print out the error metric.
Also , if necessary , here’s someone who’s pretty well-known to work on these kind of problems , if you’re really stuck on this talk to him http://www.ics.uci.edu/~eppstein/
Good luck Michal , I wanna play the game , do your best !
But Michal , usually you go for an approximation algorithm if there are constraints , but here there are no constraints … there are fast algorithms for solving THE PROBLEM , not giving an approximation.
Why do you need an approximation ?
I looked on google and found this, but u have too probably.
http://www.pms.ifi.lmu.de/lehre/compgeometry/Gosper/convex_hull/convex_hull.html
Why do you need an approximation ?
Cause I need to limit the amount of points in the final polygon. Max 5.
then do this:
calculate the exact convex hull with a classical algorithm
now you need to select 5 points of the exact convex hull.
we already know 4 of them , one is the upper point , one is the leftmost one , one is the lowest one and one is the rightmost one,
now we have to choose just one more point !
let that be an arbitrary one of the convex hull already calculated that is not one of the 4 ones mentioned above.
I’m sure you can find variations on this which will be faster.
maybe calculating the convex hull isn’t even needed.
Hey Michal,
Sorry for promising to help and then not be able to… much. I’m so swamped at work, I’m putting in long weeks and barely even have enough time to check my work email.
What may be the best attempt at this, is to use the gift-wrapping algorithm. There are plenty of examples in C++ and C. Then to solve for 5 points (Dark Avenger is in the right direction.. sort of :P):
Supposing, you use an algorithm in which you can store all the found angles and total sum of angles in an array, find the 5 angles that are the least obtuse to more acute. In all cases, 3 will be desirable points. The exception is 2 or more points found with the exact same angle that satisfy the search. We’ll get to fixing that.
Store these points.
Two things can now be done. Using a simpler form of gift-wrapping, you could create a new convex hull based on the 5 points and omit and destroy all the extra points left over. Otherwise, it may be possible to blindly plot a line to the next neighbor that satisfies the search and plot a line, within the existing hull, then destroy the old lines and points.
In such a case that 2 or more satisfying points have the same angle, store all of the equal points along with the rest. Let’s say we have 6 points for simple sake. Create a new hull, based on the 6 lines. The best way to get rid of the 6th point would probably be distance to the neighbors on either sides. Measure the distance of both identical points to their neighbor points on either side. Destroy the identical point that has the shorter distance to its neighbor. Plot a new line, from the left over point to that neighbor.
If I should be able to scrape some more time together this week, I may finally be able to put up some code, pseudo-code or pseudo-pseudo code.
Basically what I have in mind is being able to find and plot the first line, then starting with that line, using a short block that loops with a single equation or short algorithm where n=angle of the 3rd point to the last line. Based on the angle of the last line compared, the program starts sweeping from 180 degrees and inward. So every time, the equation or code runs, it will plot a new line, solve for the next point and check for next greatest angle. A second function within that loop will run and calling on the array that holds the points and angles, checks the total sum of angles/number of points based on 180(n-2).
It’s still a blind way of finding all the points, but should run very quickly. The difficulty in the logic is that, if a new point is to be discovered by sweeping inward 180 and down, scanning parallel to the last line may still yield many points. Obviously the furthest point with the most obtuse angle toward the line is the desired point, however, it must still be possible to omit some points and areas within the equation without having to waste time finding them and ruling them out. This is where the logic is tricky, in order to do it in the shortest amount of time.
Anyway, bedtime. As always good luck and keep up the good work. Things are looking good.
hello
Solved the problem. On my own. Every algorithm on the net did not satisfy me.
My algoruthm is called quick quick hull and it has max 8 vertices.
The thing you do is check for the right-most points, from that select the highest and lowest. Then check for bottom-most points, from that select the left-most and right most and so on. If they do not duplicate you’ll end up with max 8 points with a near perfect approximation for my needs.
Interesting way to do it. I figured you would solve it on your own. Congrats. Too bad I couldn’t help, but, my method is still slower anyway (and I still have a lot of learning programming to do and I didn’t really post up any code or anything also).
Most likely the reason that all the algorithms out there did not satisfy your need, was simply because they are all probably designed to solve for all outer most points in infinite space and not finite space.
Anyway good job.
And still others will point to all the diet and exercise programs that work temporarily for most people, long term for some people and not at all for others. You have to follow the suggested dose provided into the insert of the product.