1

グリッド環境にあるポリゴンの頂点があると仮定すると、それに含まれる各セル（エッジ上のセルを含む）をどのように反復できますか？

明確にするために、私は次の頂点を持っています（左上がそうであるかのように数えられます(0, 0)）：

//each point is [x, y]
var verts = [
    [1, 1],
    [3, 1],
    [3, 2],
    [4, 2],
    [4, 4],
    [0, 4],
    [0, 3],
    [1, 3]
];

これは、次のようなポリゴンを定義します。

グリッド

上記の頂点に基づいて、各緑色の点が繰り返したい点です。頂点がポリゴンのエッジに沿って歩く方向にパターンはありません。ポリゴンの周りを時計回りまたは反時計回りに移動できます。ただし、それらは順番になります。つまり、ペンを下に置いて、持ち上げずに各頂点に順番に移動すると、ポリゴンの内側を横切ることなく輪郭が描画されます。

ユースケースはimageData、キャンバスAPIを介してロードされたPNGからのものです。このPNGは「ゾーン」に分割されており、現在の「ゾーン」の各ピクセルを繰り返す必要があります。各「ゾーン」は、上記のような頂点配列によって定義されます。

次のようなものを試しました。これにより、配列内の4つの頂点のセットごとに反復する正方形が作成されます。

for(var v = 0, vl = verts.length - 4; v < vl; ++v) {
    //grabbing the minimum X, Y and maximum X, Y to define a square to iterate in
    var minX = Math.min(verts[v][0], verts[v + 1][0], verts[v + 2][0], verts[v + 3][0]),
        minY = Math.min(verts[v][1], verts[v + 1][1], verts[v + 2][1], verts[v + 3][1]),
        maxX = Math.max(verts[v][0], verts[v + 1][0], verts[v + 2][0], verts[v + 3][0]),
        maxY = Math.min(verts[v][1], verts[v + 1][1], verts[v + 2][1], verts[v + 3][1]);

    for(var x = minX; x < maxX; ++x) {
        for(var y = minY; y < maxY; ++y) {
            //do my checks on this pixel located at X, Y in the PNG
        }
    }
}

ただし、これには2つの大きな問題があります。

  1. ポリゴン内のポイントを繰り返すことができ、
  2. ポリゴンの外側のポイントをつかむことができます

チェックするポイントを追跡することで最初の問題を解決できるので、チェックを繰り返さない。2つ目は、各ポイントでチェックを実行することによってのみ解決できますPointInPoly。これにより、このソリューションは私が望むよりもはるかに重くなります。

編集
画像全体の各ピクセルを繰り返し、それぞれにPointInPolyチェックを適用することも受け入れられません。上記のアルゴリズムよりもさらに遅くなります。

4

1 に答える 1

1

ポリゴンが凸面の場合は、次のように実行できます。

  • ポリゴンの各エッジに、一方の側を内側に、もう一方の側を外側に示す線を作成します（これは法線に基づいており、巻き方向に依存する可能性があります）
  • すでに計算したバウンディングボックス内のすべてのピクセルについて、ピクセルが線の内側にあるかどうかを確認します。ピクセルがいずれかの線の外側にある場合、それはポリゴンの外側にあります。それがそれらすべての中にあるなら、それは中にあります。

基本的なアルゴリズムはここからです：https ：//github.com/thegrandpoobah/voronoi/blob/master/stippler/stippler.cpp#L187

ポリゴンが凸状でない場合、私が行うことは、実際にキャンバス上に既知の色でポリゴンを描画してから、反復フラッドフィルアルゴリズムを適用することです。それには、内側にある少なくとも1つのピクセルを知っている必要がありますが、それは高価なテストではありません。ただし、オフスクリーンバッファ（canvasタグに精通していない）で実行できない場合、これはJavaScriptでは適切でない可能性があります。

于 2012-11-15T06:29:31.283 に答える