algorithm - 凸包の誤解？

Question

グラハムのスキャン凸包アルゴリズムの実装を作成し、テストデータにポイントを使用しました

[(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 の両方が間違っていますか?

Answer 1

コマンドを使用wolframalpha Polygon{}すると、ソリューションと実際のソリューションの違いを確認でき
ます。

本物：

したがって、多角形はどちらconvexでもありません。凸多角形の定義により、多角形内のすべての点のペアは、その多角形からの点のみを含む線分を形成する必要があるためです。そして、例えば、からの線分は多角形の外にある線分を形成します{4,4}。{4,2}第二に、あなたのポリゴンはどちらでもありませんconvex hull。なぜなら、ラバーはポリゴンの内部に曲がってポイントすることができないからです{3., 2.5}。だからあなたはあなたのアルゴを修正する必要があります。

Answer 2

ポイントが 1 つ多すぎることを除いて、あなたの直感的なソリューションは正しいです: (1, 4). 凸包は通常、最小の凸集合として定義されます。を含めて集合は凸ですが、 は集合内の他の 2 つの点との間の線上にある(1, 4)ため、最小ではありません。を外しても仮想輪ゴムの形は変わりません。(1, 4)(0,4)(4,4)(1, 4)

プログラムにバグがあるようです。