ポリゴンが点集合を囲んでいる

私は点の集合S（2D：xとyによって定義されています）を持っていて、すべての点を包囲する最小の（意味が最も小さい）ポリゴンを見つけたいと思います。セットはPの順序付きサブセットです。ポリゴンが点集合を囲んでいる

これを計算するアルゴリズムはありますか？（このドメイン内の文化の私の欠如は驚くべきことである...）あなたの助けを

おかげ

2009-05-06 Laurent K

こんにちは、私は自分のアプリケーションで同じ機能を実装する必要があります。あなたは私とアルゴリズムを共有してくださいか？ –

私はQuickHullを使用しました。参考：https://en.wikipedia.org/wiki/Quickhull –

この問題には多くのアルゴリズムがあります。それは "minimum bounding box"と呼ばれます。「convex hull」、特にhereを検索するソリューションもあります。

左端の点を見つけて、他のすべての点が線p（n-1）p（n）の右側にある点を検索することです。

2009-05-06 10:07:34

ありがとう、これは私が探していたものです。 Googleで「jarvis march java」または「quick hull java」と入力すると、Javaのインプラントが見つかりました。 –

「最小境界ボックス」は...ボックスです。一般的なポリゴンではありません。他のリンクは良いかもしれません。 –

PがSのサブセットである必要があることを考慮して、「最小境界ボックス」とは何が関係しているのかわかりません。 – AnT

おそらく、最小の領域、つまり凸包です。

点を本当にしたいのであれば、あなたのすべての点が囲まれるように超大頂点位置を持つ三角形を作ることができます。ここで

2009-05-06 10:12:53 SPWorley

巨大な三角形の点PはSのサブセットではありません。 –

@DanielDaranasこの超大な三角形の頂点はどのようにして得られますか？ – Dinesh

は

が三角形を形成するために、任意の三点...で始まるシンプルなソリューションです。

エッジを2つの連続するパスに分割します.1つのパスでは、各エッジのラインが、追加するポイントをポリゴンの残りの部分から分離します（これを"分離経路"）、他方の経路では、各辺の線はポリゴンと同じ側にある点を有する。

（注：限り、あなたの形状が凸状のままとして、それは、これら2つのパスが連続的で、全体の形状を形成する必要がある）

分離経路は全く縁がない場合、ポイントが多角形内にあると無視する必要があります。そうでない場合は、ポリゴンから分離パスを削除します。これを2つのセグメントに置き換え、分離パスの各端点を新しい点に接続します。

Ta-da！ :)ここで

2009-05-06 10:27:52

2009-05-07 05:24:40

答えて