凸包误区？ [英] Convex Hull Misunderstanding?

问题描述

我写了格雷厄姆的扫描凸包算法的实现及测试数据我用了点

<$p$p><$c$c>[(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)]

据我的程序的凸包是

  [（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）]
 

不过，我预计的凸包是

  [（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）]
 

我想我点的集合与 https://github.com/shadwstalkr/GrahamScanDemo/ 以及这给了相同的溶液为好。经过一番抱怨和牢骚我读维基百科说，一个目的是凸的，如果每对中的目标点，在直线段即加入他们的每一点也是对象之内。

在画了我的观点和船体。看来，我的程序产生的定义中的一个对象，但并不意味着这只是单纯的角度分类将给予凸包的意志，而不在船体的任何点？

我不明白什么是凸包居然是和我绑来解决不同的问题，或者是我的两个实施和shadwstalkr不正确？

解决方案

通过使用 WolframAlpha的的 多边形{} 命令，你可以看到你的解决方案和真实之间的区别：
您：

真正的：

所以，你的多边形既不是凸，因为凸聚定义范围内的所有多边形点对必须形成包含点只能从多边形线段。而对于例如专线 {4,4} 到 {4,2} 构成段是出多边形。 二 - 你的多边形既不是凸包，因为橡胶不能弯曲，在成多边形内部指向 。 所以，你需要修复你的算法中。

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?

解决方案

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.

这篇关于凸包误区？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！