2本の線で定義された領域内のすべての整数点を取得する効率的な方法が必要です。
まず、2つの点Pt1とPt2で定義される線から始めます。次に、この線を移動して、2つの新しいポイントPt1newとPt2newを取得します。次に、線の移動によって生成された領域にあるすべてのオイラー点を見つける必要があります。
簡単なケースでは、最小のx値とy値と最大のx値とy値の間に長方形の領域を生成するだけなので、問題はありません。次に、オイラーグリッドとの確立された交点が実際に私の点によって生成された領域内にあるかどうかを確認します。（ポイントを時計回りに移動し、ポイントが常に右側にあるかどうかを確認します）
ただし、2番目の問題（画像の下の問題）では、ポイントが実際にエリア内にあるかどうかを簡単に確認できないため、これは機能しないようです。どうすればこれらすべてのポイントをすばやく簡単に見つけることができますか。
グラフィックでは、緑色の点を見つけることに興味があります。これはオイラーグリッド上にあります（たとえば、x座標とy座標は整数値です）。
2本の線Pt1-Pt2とPt1new-Pt2newが点P0で交差する場合、三角形Pt1-Pt1new-P0とPt2-Pt2new-P0のすべてのオイラー点を見つけます。
最も単純なアプローチは、四辺形に使用するものと同じです。バウンディングボックスを計算し、内部のすべてのオイラー点をテストします。これを確認するには、重心座標を使用することをお勧めします。
さらに一般化すると、常に三角形を使用することができます。通常の三角形ではPt1-Pt2-Pt2new + Pt2-Pt2new-Pt1new、縮退した三角形ではPt1-Pt1new-P0+Pt2-Pt2new-P0です。
参照を変更する必要があると思います。
あなたの原点があなたの線に固定されていると想像してください、そしてそれは実際に動いているグリッドです。最初に強調表示されたグリッドポイントが線上に移動したことがはっきりとわかります。2番目の例では、グリッドが回転し、強調表示されたポイントのみが線上を移動しました。
すべてが線形であるため（ここには曲線がありません）、ポイントが変換前のラインの「下」にあり、変換後のラインの下にある場合、ポイントはそれと交差していません。
次に、ポイントが線より下か上かを測定します。移動したラインの最も遠い端が3ユニットだった場合、ラインから最大3ユニット離れたグリッドポイントのみを考慮する必要があります。これらの各ポイントについて、変換の前後で線より下か上かをテストします。ステータスが変更された場合、行はそれを通過しました。そうでない場合は、そうではありませんでした。
それでは、上/下の測定。線はによって定義されます
y = mx+c。
ポイントp（px、py）は、次の場合に線より上にあります。
py> m.py+c。
行列では、最初に線AB（ax、ayからbx、by）と点（px、py）の両方を変換して、Aを原点に配置できます。
Q' = Q + | -ax |
| -ay |
次に、それを回転させて軸を線に合わせます。線とx軸の間の角度はsin（θ）=（dy / d）で与えられるので、cos（θ）=（dx / d）：
d = sqrt((by-ay)^2 + (bx-ax)^2)
s = (by-ay)/d
c = (bx-ax)/d
角度の回転行列はこのウィキペディアのページに記載されており、sとcを使用すると次のようになります。
R = | c s |
| -s c |
平行移動を適用してから線に回転を適用すると、原点からx=dまでのx軸に沿ってライが発生します。その場合、ポイントは正または負のy値を持ちます。したがって、これをポイントpに適用します。
q = R(p+T) = | c s | ( |px| + |-ax|
| -s c | |py| |-ay| )
p'x = px - ax
p'y = py - ay
qx = c * p'x + s * p'y
qy = -s * p'x + c * p'y
これをポイントPで、2つの異なるラインABとCDに対して実行するとします。2つのポイントFとG（前後の変換されたポイント）を取得します。次の場合、ポイントは（いわば）線を越えました。
if( signof(fy) != signof(gy) ) {
// crossed the origin
}
ただし、これはyのみをテストすることに注意してください。線が短すぎて点に到達できない場合は、点が線を通過しただけである可能性があります。したがって、x値も変更されているかどうかをテストします。
if( (fx < 0) && (gx < 0) ||
(fx > d) && (gx > d) ) {
// whooshed past
}
したがって、これらの両方をテストすると、ポイントがラインを越えたかどうかがわかります。
それが明確であることを願っています...