ポリゴンを定義する (x,y) 値の配列セットがあります。ポリゴンは、ポイントの位置 * 鉛筆サイズに基づいて描画されます。問題は、内側の頂点を無視して、そのような形状の境界線を描きたいということです。この例を参照してください。BLACK 頂点は私が興味を持っているものです。YELLOW のものを取り除きたいです。
時計回りに並べられた別の配列で X を取得したいと思います。すべてのポイントを評価して、隣人がいるかどうか、どこにあるか (北、南、東、西) を確認することを考えていましたが、すべての頂点をチェックするにはあまりにも多くの処理が必要なようで、別の証明済みのよりエレガントなアルゴリズムに違いないと思います。
ヒントはありますか？
通常、ポリゴンはアウトラインによって定義されます。それはあなたがそこで対処しなければならない不幸なフォーマットです。
それらがそのように配置されている場合 (同じ y 座標の行に)、最初に x で、次に y で配列を並べ替えてから、最初の点、y の変化の周りの 2 つの点、およびアウトラインを形成する最後のポイント。
物事の実際の状態が少し複雑な場合は、「アルファ シェイプ」を調べることをお勧めします。いくつかのリンク: http://biogeometry.duke.edu/software/alphashapes/、http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html
あなたの「ポイント」は小さな四角形であるため、内側のポイント (形状の境界に寄与しないポイント) は、 、 、 、および すべてのポイントであるよう(x-1,y)に(x+1,y)聞こえ(x,y-1)ます(x,y+1)。
すべてのポイントをハッシュテーブル (または他の多くのインデックス構造の 1 つ) に入れることで、そのテストをすばやく行うことができます。
時計回りに注文するには、国境を歩くだけです。穴がある場合は、穴をどうするかを決定する必要があります。