6

Point1 と Point2 の 2 つの点があるとします。これらのポイントは常に異なる位置にある可能性があり、必ずしも静的であるとは限りません。

Point1 は時間 t のある位置にあり、その位置は時間 t での x 座標と y 座標を与える連続関数 x1(t) と y1(t) によって定義されます。これらの関数は微分可能ではなく、線分から区分的に構築されます。

Point2 は同じで、x2(t) と y2(t) があり、各関数は同じプロパティを持ちます。

可視性を妨げる可能性のある障害物は、単純な (そして動かない) ポリゴンです。

可視性の境界点を見つけるにはどうすればよいですか?

つまり、点が見えるようになる場所と見えなくなる場所の 2 種類の境界があります。

可視化境界 i の場合、いくつかの ϵ>0 が存在し、任意の実数 a, a ∈ (i-ϵ, i) に対して、Point1 と Point2 が表示されません (つまり、接続する線分がいくつかの障害物(x1(a), y1(a))を横切ります) (x2(a), y2(x))）。

b ∈ (i, i+ϵ) の場合、それらは可視です。

そして、見えなくなるのはその逆です。

しかし、そのような正確な境界を見つけることはできますか?もしそうなら、どのように?

4

3 に答える 3

2

わかりました、私は今問題をより明確に把握しており、@ walkytalky の提案に触発されて、より精巧な答えがあります。

あなたはそれを述べ、直線セグメントに沿っp1て移動します。これらのセグメントが、との両方が常に新しいセグメントを同時に開始p2するように配置されているかどうかはわかりません。ただし、いつでも線分を 2 つの線分 (勾配が同じ) に切断して、とが常に新しい線分を同時に開始できるようにすることができます。p1p2p1p2

p1が線A-Bに沿って移動し、パラメータが 0 から 1 になるのp2に沿って (同時に) 移動すると仮定します (つまり、時間はの真ん中との真ん中にあります)。C-Dtt=0.5p1A-Bp2C-D

Axポイントの x 座標とAyy 座標をと で表すことによりA( 、 、 についても同様に) B、Cとをの関数として次のようにD表すことができます。p1p2t

p1(t) = (Ax + t*(Bx - Ax), Ay + t(By - Ay))
p2(t) = (Cx + t*(Dx - Cx), Cy + t(Dy - Cy))

(たとえば、 がt=0にAx + t*(Bx - Ax)評価されAx、 がにt=1評価される場合Bx)。

各「a-vertex-is-passing-by-between-p1-and-p2」時間を見つけるには、次のようにします。

障害物頂点ごとに、 、、が互いに一直線になるようv=(Vx, Vy)に を見つける必要があります。tp1(t)p2(t)v

tこれは、次の方程式 (2 つの方程式、2 つの未知数、およびk)を解くことによって行うことができます。

Vx=p1(t).x + k*(p2(t).x - p1(t).x)
Vy=p1(t).y + k*(p2(t).y - p1(t).y)`

k0 と 1 の間にある場合、ポリゴンの頂点vは実際には (延長された)線と (延長された) 線の間にあります。も 0 と 1 の間にある場合、ポイントがこれらのセグメントに沿って移動する間、頂点は実際には線によって通過します ( 1.3 などの場合、ポイントはすでに新しいセグメント上にあるため)。A-BC-Dtvp1-p2t

すべての「a-vertex-is-passing-by- between-p1-and-p2」時間が計算されると、残りを計算するのは簡単な作業です。(つまり、「見えるようになる」、「見えなくなる」、または「どちらでもない」タイプのパスかどうかを判断します):

すべてのペアt0とt1連続する頂点通過時間について、ラインp1((t1-t0)/2)-p2((t1-t0)/2)にポリゴン エッジとの交差がないかどうかを確認します。交点がない場合、ポイントは全期間 ( t0-t1) 見通し内にあります。

于 2010-05-05T13:55:13.810 に答える
1

2 つの線が交差しているかどうかを確認するのは簡単です。これを使用して、ライン (p1、p2) と各ポリゴン エッジの交点を確認します。交差点がある場合、ライン (p1, p2) は何らかの障害物によって遮られています。

時間間隔 (p1 と p2 が見通し内にない) が必要な場合は、t の異なる値 (できれば比較的小さな差) と、「visible-t」と「invisible-t」の間で上記のチェックを行うことができます。 -t" eps などの十分に小さいしきい値に達するまで、バイナリ検索を実行できます。

于 2010-05-05T10:38:47.853 に答える
1

可視性の変化は、障害物の頂点が Point1-Point2 ライン セグメント上にある場合にのみ発生します。したがって、そのようなすべての頂点衝突の時間を計算します。(直感的には、エンドポイントが直線的に移動するため、これは比較的単純なテストであるはずですが、実際に確認する必要があります。後で試して戻ってきます。)

これで、衝突時間のセットが有限になりました。それぞれについて、セグメントが他の障害物のエッジと交差するかどうかを確認します。存在する場合、そのエッジが可視性を管理し、時間は可視性の境界ではありません。そうでない場合は、(t-ε) と (t+ε) で可視性をチェックして、変化の性質を判断できます。

頂点が連続ストレッチの接続線上にある場合など、一部のエッジ ケースではポリシーが必要になります。これらはすべて、ポイント (および端から見たエッジ) が不透明かどうかという問題に要約されると思います。

アップデート

頂点の衝突を特定するプロセスは、確かにかなり簡単です。t で少し面倒な二次方程式を解くだけです。動きの区分的セグメントごとに頂点ごとにこれを行う必要があるため、n 頂点と m 期間のコストはO(n*m)になると思います。(位置関数の期間が同期していない場合は、同期するように細分化する必要があります。)

1 つの期間のみを考慮し、t を [0,1] の範囲にスケーリングします。各位置関数は t で線形であるため、定義x1(t) = x10 + x1m * t(つまり、x10は開始値、x1mは勾配)、 、 、 についてもy1(t)同様x2(t)ですy2(t)。頂点V = (vx, vy)の場合、V が点を結ぶ線分上にある時間 (存在する場合) は、式At^2 + Bt + C = 0で与えられます。ここで、

A = x1m * y2m - x2m * y1m
B = vx * (y1m - y2m) + vy * (x2m - x1m)
     + x10 * y2m - x20 * y1m
     + y20 * x1m - y10 * x2m
C = vx * (y10 - y20) + vy * (x20 - x10)
     + x10 * y20 + x20 * y10

（またはそのようなもの。封筒の裏からの転記エラーの可能性を考えると、実装する前に自分で作業することを強くお勧めします!)

この解が [0,1] の範囲にある場合、ボブはあなたのおじです。に減少する0 = 0か、またはそのようなものである場合、ポイントは常にライン上にあり、その場合はポリシーを検討する必要があります.

于 2010-05-05T12:00:07.603 に答える