math - 長方形内の点かどうかを確認します

Question

私は持っている：

1. 軸に沿った四角形R ;
2. 非垂直線A (2 点で指定);
3. 垂直線B (x 座標で指定)。

上記のすべてのオブジェクトは、整数座標によって指定されます。

AとBを交差させた結果がRにあるかどうかを確認する必要があります。しかし、整数座標では表現できない可能性があるため、AとBを交差させた結果を計算することはできません。また、不正確なことなく絶対に正確な結果を得る必要があるため、double に変換することはできません。

では、どうすれば確認できますか？

Answer 1

線が整数座標で指定されている場合、それらの交点は有理座標を持ち、絶対精度で比較できます。

A が点 (ax0, ay0) と (ax1, y1) を通り、B が X0 座標にあるとします。交点の Y 座標は (ay0*(ax1-ax0)+(X0-ax0)*(ay1-ay0))/(ax1-ax0) = p/q で、p と q は整数で、q は正です。 (必要に応じて指名詞を否定します)。

次に、p を R.Top*q および R.Bottom*q と比較できます。

Answer 2

(x0, y0)A 上の 2 点がと(x1, y1)であり、'x0 < x1' であるとしましょう。

長方形は、x 座標xRと y座標によって決定されます。yR

B ラインは x 座標によって決定されます。xB

あなたが探しているポイントは、整数のみを操作することによって(xB, yB)、どこかで決定されることです:yB

ですので、まずは確認が必要です

1. if xB * xR >= 0(x 座標の同じ側)
2. if abs(xB) <= abs(xR)(B 線が長方形を切り取る)

問題がなければ、この整数 ((x1-x0)yB に等しい) を確認する必要があります。

Y = (y1-y0)(xB-x0)+(x1-x0)y0

検証する

1. Y * yR >=0(y 座標の同じ側)
2. abs(Y) <= (x1-x0) * abs(yR)(交点がy座標に関してR領域にあることを意味します)

4つの条件が真の場合にのみ、ポイントはR内にあります。それが役に立てば幸い。

Answer 3

[B が R と交差しない場合の面白くないケースは無視しましょう]

R は B からセグメントを切り取ります。これを S と呼びましょう。A が S を横切る場合に限り、B と A の交点は R の内側にあります。

S の点を見つけることは自明です。

線分が線分と交差しているかどうかを確認するには、S の端が A とは異なる側にあることを確認する必要があります。これは符号付き角度で確認できます。