等式 aX + bY <= c で指定される直角三角形の場合、整数について
以前のヒットポイントのリストを保存せずに、疑似ランダムな順序で三角形の各ピクセル(*)を一度だけプロットしたいと考えています。
0とxの間の線分でこれを行う方法を知っています
線に沿ってランダムな点「o」を選び、
x と互いに素な「p」を選びます
x 回まで繰り返します: O next = (O cur + P) MOD x
三角形に対してこれを行うには、次のよう
にします。 1. 三角形 sans リスト内のピクセル数をカウントする必要があります
。 2. 整数 0..points を、三角形内の有効なピクセルである ax、y ペアにマップします。
解決策がピラミッドや高次元の形状に一般化されることを願っています。
(*) 方程式が満たされるように、整数点 X、Y のペアに CG 用語ピクセルを使用します。
各ピクセルに 1 回だけアクセスすることを保証したいので、実際の三角形ではなく、ピクセルの観点から考えた方がよいでしょう。三角形を水平にスライスして、水平走査線の束を得ることができます。走査線を接続すると、「三角形」が長い線に変換されます。ポイント ビジット アルゴリズムをスキャン ラインの長いチェーンに適用します。
ところで、このマッピングは紙の上で行うだけでよく、必要なのは仮想走査線に沿って (t) を指定して (x, y) を返すことができる関数だけです。
編集: 2 つの点を線分に変換するには、Bresenham のスキャン変換を探すことができます。3 つの線分を一連のポイントに変換したら、すべてのポイントをバケットに入れ、すべてのポイントを y でグループ化できます。同じ y 値内で、ポイントを x で並べ替えます。y 値内の最小の x はスキャン ラインの始点であり、y 値内の最大の x はスキャン ラインの終点です。これを「走査変換三角形」と呼びます。Google で検索すると、より多くの情報を見つけることができます。
三角形のポイントピッキングのソリューションは次のとおりです。
あなたがしなければならないのは、三角形の2つのベクトル（辺）を選択し、それぞれに[0,1]の乱数を掛けて、それらを合計することです。これにより、ベクトルによって定義された四辺形に一様分布が提供されます。結果が元の三角形の内側にあるかどうかを確認する必要があります。変換されない場合、または単に破棄して再試行する場合。
これは、CPU時間を浪費する方法ですが、より複雑な方法ほど無駄にはならないでしょう。
三角形に外接する長方形を計算します。その長方形を「線形化」するのは簡単です。各スキャンラインの後に次のラインが続きます。長方形のピクセルをトラバースするには、すでに知っているアルゴリズムを使用します。各ピクセルをヒットしたら、そのピクセルが三角形の中にあるかどうかを確認し、そうでない場合はスキップします。
1 つの方法は、すべてのピクセルを配列に入れてから配列をシャッフルし (これは O(n))、シャッフルされた配列内の順序でピクセルにアクセスすることです。ただし、これにはかなりのメモリが必要になる場合があります。
三角形の線は、セグメントにカットされた単一の線と見なします。セグメントは配列に格納され、そこにはセグメントの長さも格納され、行の全長のオフセットも格納されます。次に、O の値に応じて、この情報に基づいてその時点で描画するピクセルを含む配列要素を選択し、要素の値に基づいてピクセルをペイントできます。