Convex Hull Misunderstanding?

问题:

I wrote an implementation of Graham's Scan convex hull algorithm and for test data I used the points

[(2.0,2.0),(4.0,2.0),(0.5,2.5),(3.0,3.5),(1.0,4.0),(0.0,4.0),(1.0,1.0),(3.0,2.5),(4.0,4.0),(3.5,1.5),(0.5,1.0)]

According to my program the convex hull is

[(0.0,4.0),(1.0,4.0),(4.0,4.0),(3.0,2.5),(4.0,2.0),(3.5,1.5),(1.0,1.0),(0.5,1.0)]

However, I expected the convex hull to be

[(0.0,4.0),(1.0,4.0),(4.0,4.0),(4.0,2.0),(3.5,1.5),(1.0,1.0),(0.5,1.0)]

I tried my set of points with https://github.com/shadwstalkr/GrahamScanDemo/ as well and that gives the same solution as well. After much complaining and grumbling I read on wikipedia that "An object is convex if for every pair of points WITHIN the object, every point on the straight line segment that joins them is also within the object."

After drawing out my points and hull. It appears that my program produced an object within that definition, however wouldn't that mean that just simply sorting by the angle would give a convex hull as will without any points in the hull?

Do I not understand what a convex hull actually is and I am tying to solve a different problem or is both my implementation and shadwstalkr incorrect?

回答1:

By using wolframalpha Polygon{} command you can see the differences between your solution and the real one:
your:

real:

So your polygon is neither convex, because by definition of convex poly ALL pairs of points within polygon must form line segment which contains points ONLY from that polygon. And for example line from {4,4} to {4,2} forms segment which is out of polygon. Second - your polygon is neither convex hull because rubber can't bend-in into polygon interior to point {3., 2.5}. So you need to fix your algo.

回答2:

Your intuitive solution is correct except that it has one point too many: (1, 4). A convex hull is usually defined to be a minimal convex set. Including (1, 4), the set is convex, but it is not minimal because (1, 4) is on the line between two other points in the set: (0,4) and (4,4). If you remove (1, 4), the shape of the imaginary rubber band doesn't change.

It looks like there's a bug in your program.