私は、未整理の2D点集合を持っています。この集合の "等高線"（凸包ではありません）を探したいと思います。スピード目標（平均的なコンピュータでは10ms以下）があるため、アルファ形状を使用できません。 私の最初のアプローチは、グリッドを計算し、アウトライン四角（四角形が空の四角形を隣人として持つ）を見つけることでした。だから私は効率的に私のポイント数を（22000から3000に）大まかに縮小したと思う。しかし、私はまだこの新しいセットを改良する必要があります。2D unorganizedポイントクラウドの輪郭を見つけよう
私の質問は：どのように私は本当の私の緑の点の中のポイントを概説見つけるのですか？
リフレクションがいっぱいの週末の後、私は便利な解決策を見つけたかもしれません。
グリッドが必要なので、ポイントを記入する必要がありますが、ここで問題はありません。
「四角形」と見なされる四角形を決定する必要があります。私たちの基準は、少なくとも1つの空のネイバーと少なくとも3つの空でないネイバーです。
接続に関する情報がありません。そこで、私たちは、2つの「輪郭」の隣人またはそれ以下の「輪郭」の四角形を選択します。次に、隣人の1人を選ぶ。それで、私たちは拡大を開始することができます。私たちは、現在の四角形を囲んで、前の「等高線」の四角形を知っている次の「等高線」の四角形を見つけます。私たちの輪郭の基準は私たちが行き詰まるのを防ぐ。
接続された四角形のベクトルがあります。通常、形状に穴がない場合、接続された四角形のベクトルは1つだけです。
ここで、各四角形について、輪郭に最適な点を見つける必要があります。我々は、我々の飛行機の重心から遠いものを選択する。それはほとんどの形状で機能します。もう1つの方法は、選択した四角形の空の近傍の重心を計算し、最も近い点を選択することです。
赤点は緑色一方の輪郭です。使用される技術は、平面の重心である。
28000ポイントのセットでは、このテクニックは8ミリ秒かかります。 CGALのアルファシェイプは28000ポイントで平均125ミリ秒かかるでしょう。
PS：私は英語が私のmothertongueはありませんが、私は自分自身を明らかにした願っています。■
アルファシェイプを使用してください。たぶんアルファアルファアルゴリズムの入力として緑の点だけを使用します。
でも2500ポイントを、CGALのアルファシェイプの計算時間は15msです。緑の点を見つける5msに追加され、20msの計算時間です。私は3ミリ秒かかり、良い出力を持つ解決策を見つけました（私はそれをタイプしています）。 – Cyril
@Xerto：マシンが非常に遅いか、またはCGALアルファシェイプを悪く使用しています。ラップトップでは、大きすぎるアルファ値を指定してすべてのエッジを返さない限り、25000ポイントの実行時間は約5msです（この場合、約20ms、25000ポイント）。 – lrineau
私のprocはCore 2 Duoです。ソフトウェアは無人機向けに設計されているので、低仕様（おそらくAtom）があります。 CGALのAlphashapesでは、私はドキュメントの中の与えられた例を使用します。 – Cyril
てみてください[アルファシェイプ]（http://en.wikipedia.org/wiki/Alpha_shape） – chaohuang