java - java/android で指定された点を使用して凸包を描画します

Question

いくつかの 2D ポイントが指定されており、それらのポイントを使用してポリゴンを描画したいと考えています。このポリゴンは指定されたすべてのポイントを通過する必要があります。これは、ポリゴンの内側または外側にそのようなポイントがないことを意味します。

例: (0,0)、(1,1)、(-1,-1)、(-1,1)、(1,-1) のような点があり、多角形を描きたい場合それらを使用すると、ポイント配列は次の方法でソートする必要があります。

(1,1) -> (1,-1) -> (-1,-1) -> (-1,1) -> (0,0) -> (1,1) または

(1,1) -> (0,0) -> (-1,1) -> (-1,-1) -> (1,-1) -> (1,1)

しかし、それはできません：

(1,1) -> (0,0) -> (-1,-1) -> (-1,1) -> (-1,1) -> (1,-1) -> (1, 1)

ポリゴンを描画するために、drawLine関数を使用して、あるポイントから別のポイントまで、最後に最後のポイントから最初のポイントまで線を描画しています。

これに利用できるアルゴリズムまたはコードはありますか?

ありがとう！！

Answer 1

グーグルでのクイック検索：凸包アルゴリズム、そしてここにJavaの実装があります。

編集：あなたの質問を読み直して、それがあなたが望んでいたものではないことに気づきました。「凸包」というタイトルは誤解を招く可能性があります...

Answer 2

あなたの問題は思ったほど些細なことではないと思います。私見は、巡回セールスマン問題の特別な形式ですが、交差するパスはありません。