ポリラインやポリゴンをチェーンコードに変換するには？

Question

私は、2D点の集合から成る開いたまたは閉じたポリライン（ポリゴン）を持っています。

ポリラインをチェーンコードとして表現する必要があります。私が正しく理解すれば、私はBresenhamのアルゴリズムを使ってポリラインセグメントをラスタライズし、そのラスタのチェーンコード形式を構築する必要があります。しかし、より良いアルゴリズムはありますか？

ポリライン（ポリゴン）をチェーンコードに変換する最適なアルゴリズムは何ですか？

Answer 1

はい、ポイントを直接フーリエ変換に直接描画する方がはるかに高速です。あなたがKuhl-Giardiana 1982アルゴリズムの使用であると仮定したポリラインの方向に正確にポイントを必要とした後、ラスタをスキップしてチェーンコードを作成します。すべてのピクセルを正しい順序で表示したい場合は、何かをラスタライズするのではなく、ピクセルをアルゴリズム自体に描画して直接取得することができます。実際、これは基本的にチェーンコードとラスタをスキップします。

---

すべての行が式：y = mx + bと、これを行うための最速の方法は、ブレゼンハムのことを行っているのであることを行っています。ただし、最終的な使用に応じて、Wuのアルゴリズムを選択して、アンチエイリアスを確実に含めることができます。アンチエイリアスは、線をシャープに見せる傾向があります（アルファを保存する必要があります）。チェーンコードを特定のものにする必要があると仮定すると、そのラインが生成する実際のピクセルが必要です。これは、ライン描画アルゴリズムを使用することを意味します。

あなたの描画アプリのほとんどは、チェーンコードではなくラスタライズされたイメージを提供します。ポリラインを適切なサイズの白い画像に黒で描画し、画像全体を通り、すべての黒いピクセルをリストするオプションがあります。遅くて不必要な、そしてミッションクリティカルな操作では、初心者ではないにしても、コード化は簡単です。

コードは非常に簡単になるでしょう。ちょうどbresenhamをしてから、チェーンコードにポイントを追加するポイントを投げてください。

public void plotLines(int[] twodshape, Chaincode chain) { 
    for (int i = 0, s = twodshape.length-4; i < s; i+=2) { 
     plotLine(twodshape[i],twodshape[i+1],twodshape[i+2],twodshape[i+3],chain); 
    } 
} 
public void plotLine(int x0, int y0, int x1, int y1, Chaincode chain) { 

    int dy = y1 - y0; //BRESENHAM LINE DRAW ALGORITHM 
    int dx = x1 - x0; 

    int stepx, stepy; 

    if (dy < 0) { 
     dy = -dy; 
     stepy = -1; 
    } else { 
     stepy = 1; 
    } 

    if (dx < 0) { 
     dx = -dx; 
     stepx = -1; 
    } else { 
     stepx = 1; 
    } 
    if (dx > dy) { 
     dy <<= 1;             // dy is now 2*dy 
     dx <<= 1; 
     int fraction = dy - (dx >> 1);       // same as 2*dy - dx 
     chain.add(x0,y0); 

     while (x0 != x1) { 
      if (fraction >= 0) { 
       y0 += stepy; 
       fraction -= dx;        // same as fraction -= 2*dx 
      } 
      x0 += stepx; 
      fraction += dy;         // same as fraction += 2*dy 
      chain.add(x0,y0); 
     } 
     chain.add(x0,y0); 
    } else { 
     dy <<= 1;             // dy is now 2*dy 
     dx <<= 1;             // dx is now 2*dx 
     int fraction = dx - (dy >> 1); 
     chain.add(x0,y0); 
     while (y0 != y1) { 
      if (fraction >= 0) { 
       x0 += stepx; 
       fraction -= dy; 
      } 
      y0 += stepy; 
      fraction += dx; 
      chain.add(x0,y0); 
     } 
     chain.add(x0,y0); 
    } 
} 

更新： 私は私が点Aから点Bまで引き出される線を有する特定の問題が原因の丸めにAにBから同じであることが保証されていないことが必要で、再帰的なビットを除去斜面。たとえば、1ピクセル上に移動する場合、右に移動する場合5.これには2つの同様に有効な方法があり、それは私に一貫した答えを与えていませんでした。

---

あなたが深くchaincodeでそれを必要とする場合は、次の

public int convertToChaincode(int cx, int cy) { 
    if ((cx == 1) && (cy == 0)) return 0; 
    if ((cx == 1) && (cy == 1)) return 1; 
    if ((cx == 0) && (cy == 1)) return 2; 
    if ((cx == -1) && (cy == 1)) return 3; 
    if ((cx == -1) && (cy == 0)) return 4; 
    if ((cx == -1) && (cy == -1)) return 5; 
    if ((cx == 0) && (cy == -1)) return 6; 
    if ((cx == 1) && (cy == -1)) return 7; 
    return -1; //error. 
} 

public void plotLine(int x0, int y0, int x1, int y1, ChainCode chain) { 

    int dy = y1 - y0; //BRESENHAM LINE DRAW ALGORITHM 
    int dx = x1 - x0; 

    int stepx, stepy; 
    int cx = 0; 
    int cy = 0; 

    if (dy < 0) { 
     dy = -dy; 
     stepy = -1; 
    } else { 
     stepy = 1; 
    } 

    if (dx < 0) { 
     dx = -dx; 
     stepx = -1; 
    } else { 
     stepx = 1; 
    } 
    if (dx > dy) { 
     dy <<= 1;             // dy is now 2*dy 
     dx <<= 1; 
     int fraction = dy - (dx >> 1);       // same as 2*dy - dx 
     //typically set start point. 

     while (x0 != x1) { 
      if (fraction >= 0) { 
       y0 += stepy; 
       cy = stepy; 
       fraction -= dx;        // same as fraction -= 2*dx 
      } 
      x0 += stepx; 
      cx = stepx; 
      fraction += dy;         // same as fraction += 2*dy 
      chain.add(convertToChaincode(cx,cy)); 
     } 
    } else { 
     dy <<= 1;             // dy is now 2*dy 
     dx <<= 1;             // dx is now 2*dx 
     int fraction = dx - (dy >> 1); 
     //typically set start point 
     while (y0 != y1) { 
      if (fraction >= 0) { 
       x0 += stepx; 
       cx = stepx; 
       fraction -= dy; 
      } 
      y0 += stepy; 
      cy = stepy; 
      fraction += dx; 
      chain.add(convertToChaincode(cx,cy)); 
     } 
    } 
}