graphics - 任意のピクセルベースの描画のバウンディングボックスを計算します

Question

任意のピクセルの連続した描画（たとえば、HTML5キャンバス上）を考えると、単にすべてのピクセルを見て最小/最大x / y値を記録するよりも効率的な、軸に沿ったバウンディングボックスを見つけるためのアルゴリズムはありますか？

Answer 1

左上から右へ、そして下へスキャンラインするだけで、yが上になり、残りの方向が異なる同様のアルゴリズムが得られます。

---

Phrogzによる編集：

これが擬似コードの実装です。含まれている最適化により、各スキ​​ャンラインが以前のパスでカバーされたピクセルを認識しないようにします。

function boundingBox()
  w = getWidth()            # Assuming graphics address goes from [0,w)
  h = getHeight()           # Assuming graphics address goes from [0,h)
  for y=h-1 to 0 by -1      # Iterate from last row upwards
    for x=w-1 to 0 by -1    # Iterate across the entire row
      if pxAt(x,y) then
        maxY=y
        break               # Break out of both loops

  if maxY===undefined then  # No pixels, no bounding box
    return               

  for x=w-1 to 0 by -1      # Iterate from last column to first
    for y=0 to maxY         # Iterate down the column, up to maxY
      if pxAt(x,y) then
        maxX=x
        break               # Break out of both loops

  for x=0 to maxX           # Iterate from first column to maxX
    for y=0 to maxY         # Iterate down the column, up to maxY
      if pxAt(x,y) then
        minX=x
        break               # Break out of both loops

  for y=0 to maxY           # Iterate down the rows, up to maxY
    for x=0 to maxX         # Iterate across the row, up to maxX
      if pxAt(x,y) then
        minY=y
        break               # Break out of both loops

  return minX, minY, maxX, maxY

結果（実際には）は、単一ピクセルのブルートフォースアルゴリズムとほぼ同じように実行され、オブジェクトが大きくなるにつれて大幅に向上します。

デモ： http： //phrogz.net/tmp/canvas_bounding_box2.html

楽しみのために、このアルゴリズムがどのように機能するかを視覚的に表現します。

       
       
       
       
       

サイドをどの順序で選択するかは重要ではありません。コーナーをダブルスキャンしないように、前の結果を考慮に入れる必要があります。

Answer 2

ある種の二分探索を使用したり、粗いグリッドでサンプリングしてから、連続して細かいグリッドでサンプリングしたりできる場合があります。この方法の正確さは、図面で「穴」が許可されているかどうかによって異なります。

Answer 3

私は現在の答えが嫌いです。これが私がOPウェブサイトに接続した私のコードです。FirefoxとChromeでははるかに高速です。

アイデアは、X軸のすべてのピクセルをチェックして、Y軸にヒットがあるかどうかを確認することです。その場合は、Yを更新し、Xを増やして、最大Xをスキャンできるようにします。

function contextBoundingBox(ctx,alphaThreshold){
    if (alphaThreshold===undefined) alphaThreshold = 15;
    var w=ctx.canvas.width,h=ctx.canvas.height;
    var data = ctx.getImageData(0,0,w,h).data;

    let minX=w;
    let maxX=0
    let minY=h
    let maxY=0
    for(let y=0; y<h; y++)
    {
        for(let x=0; x<w; x++)
        {
            if (data[y*w*4 + x*4+3])
            {
                minX = Math.min(minX, x);
                maxX = Math.max(maxX, x);
                minY = Math.min(minY, y);
                maxY = y;
                x=maxX
            }
        }
    }

    return {x:minX,y:minY,maxX:maxX,maxY:maxY,w:maxX-minX,h:maxY-minY};
}