2Dポリゴンをラスタライズ

Question

ポイントのリストとして表される閉じた2Dポリゴンからバイナリビットマップを作成する必要があります。あなたはそれを行うための効率的で十分に単純なアルゴリズム、あるいはC++コードのほうが良いと指摘してください。

ありがとうございます！

PS：プロジェクトに依存関係を追加しないようにしたいと思います。しかし、オープンソースのライブラリをお勧めするなら、私はいつもコードを見ることができるので便利です。

Answer 1

あなたが望む魔法のgoogleのフレーズは、「非ゼロ巻きルール」または「偶数奇数ポリゴンフィル」です。どちらも、ほとんどの目的のために実装するのは非常に簡単で、十分に高速である

• non-zero winding rule
• even odd polygon fill

：

はのためにWikipediaのエントリを参照してください。いくつかの巧みさで、アンチエイリアス化することもできます。

Answer 2

• Triangulate your polygon
• ラスター三角形の各三角形が持っていない場合
  • （あなたはGPUを使用している場合、それはそれはGPUの原始的な操作ですが、代わりにあなたのためにそれを行うことができます） x軸に平行な線分を2つの三角形に分割し、x軸に平行な線を持ち、median-yの点を通ります。
  • 残りのタスクは次のような三角形を描画します。 x軸に平行な線分です。このような三角形は、左辺セグメントと右辺セグメントを有する。
  • 三角形の走査線（min-yからmax-y）を反復する。各yについて、その走査線の左および右のセグメントの点を計算する。これら2つの点（単純なmemset）をスキャンラインセグメントに入れます。

複雑さはO（ピクセル単位エリア）

Answer 3

あなたはpygameのポリゴンの塗りつぶしルーチンをチェックアウトすることができます。 draw_fillpolyの機能を見てください。

アルゴリズムは非常に簡単です。各セグメントがY軸に沿って交差するすべての位置を検出します。これらの交点はソートされ、次に各交点のペアが水平に塗りつぶされます。

これは複雑で交差する図形を処理しますが、明らかに大量のセグメントでこのアルゴリズムを破ることができます。 "even-odd rule"

の堅牢implimentationについては

Answer 4

はDarel Rex Finley's Efficient Polygon Fill、またはそれのBlender's versionを参照してください。

これは、そのような状況を検出するための複雑なコードを必要とせずに、自己交差線をサポートし、巻き線に依存しない（ポリゴンを反転して同じ結果をもたらす）です。

---

更新、Iは各Yピクセルのため上の全ての座標をループ回避Darelレックスの方法の最適化されたバージョンを作りました。

スタンドアローンの実装：

• C99。
• Rust（テストあり）。

高速化の可能性が高い2540x1600地域、YMMV以上の任意の手描き落書きを使用して、その速く7.5倍（11X roundコールを削除）を中心に、簡単なテストからは、指数関数的になりますが。