3

青で表示されている次のポリゴンを分解して、凹面の原因となるすべてのポイントをポリゴンから削除します。

代替テキスト

現在、私がやろうとしていることは次のとおりです。

  • ポリゴンから各ポイントを取り出します
  • ポイントをテストして、セットの残りの部分によって作成されたポリゴン内にあるかどうかを確認します
  • trueの場合、ポイントを削除します
  • falseの場合、要点を維持します

これはほとんどの場合に機能しますが、前のケースでは、（2,3）と（2,4）の両方のポイントが削除されることはありません。どちらの場合も、どちらかのポイントが削除されますが、もう一方は配列が渡される順序に依存しません。

私が疑問に思っているのはこれです：

  1. 私が扱っているポリゴンにこれらのケースのいずれかが発生するかどうかをテストする方法はありますか（つまり、3つの連続した障害点がありますか？）
    または
  2. 凸多角形を作成するより効果的な方法はありますか？

ありがとうございました。

4

4 に答える 4

6

凸包をお探しですか？

頭に浮かぶ最初のアルゴリズムはQuickHullです。最初に、左端と右端の点lとrを取ります。彼らは船体にいるに違いありません。

1つはlからr、もう1つはrからlの2つの外面である船体の最初の推測を作成します。つまり、ボリュームがゼロのポリゴンがあります。

残りのすべてのポイントをlrの前のポイントとrlの前のポイントに分割します。

それ以降、どの顔にもその前にポイントがあります。

  • 顔から最も遠い点を見つける
  • このエッジを削除し、2つのエッジに置き換えます。1つは元の始点から最も遠い点まで、もう1つは最も遠い点から元の終点までです。
  • 古い顔の前にあったすべてのポイントのうち、前のセットに追加した最初の新しい顔の前にそれらを置き、2番目の前のポイントを前のセットに入れます。現在内部にあるものへの参照を保持します

最後に、凸包ができます。

于 2010-11-13T19:18:56.013 に答える
1

ポイントの凸包を単純に計算してみませんか？

これは、本やオンラインの多くのアルゴリズムでよく研究されている問題です。「スイープ角度」の方法は特に一般的です。

http://courses.csail.mit.edu/6.854/06/scribe/s25-rasmu-sweepline.pdf

于 2010-11-13T19:16:28.780 に答える
0

あなたが探しているものは「凸包」発見として知られています。この問題のアルゴリズムについては、ウィキペディアをご覧ください。「ギフトラッピング」アルゴリズムは簡単に実装できます。船体を見つけたら、船体の一部ではないすべてのポイントを削除します。

于 2010-11-13T19:22:10.273 に答える
0

凸包は、一部の言語/環境で既に実装されていることに注意してください。

Mathematica での例:

<< ComputationalGeometry`; 
   data2D = {{4.4, 14}, {6.7, 15.25}, {6.9,12.8}, {2.1, 11.1}, {9.5, 14.9}, 
             {13.2, 11.9}, {10.3, 12.3}, {6.8, 9.5}, {3.3, 7.7}, {0.6, 5.1}, 
             {5.3, 2.4}, {8.45, 4.7}, {11.5,9.6}, {13.8, 7.3}, {12.9, 3.1}, 
             {11, 1.1}};

PlanarGraphPlot[data2D, ConvexHull[data2D]]

出力：

代替テキスト

于 2010-11-13T22:11:10.007 に答える