0

無限の 2D 空間には一連の線があり、各線には始点と終点、および作成時刻がありますLine(p0, p1, t)。

この 2D 空間のトップダウン ビューでレンダリングする必要がある線を見つけたいです (t の値が大きいほど、ビューポートの近くに表示されますが、関連する必要はありません)。

直感的な答えは、「いずれかの点がビューポート座標内にあるかどうかを確認する」ですが、ビューポート領域がカバーするよりも点が離れている場合、これは失敗します。

私が持っていたもう1つのアイデアは、 geohashのようなものを使用することでした。これにより、精度、つまりビューポートの最大ズームレベルが制限されます。アイデアは、交差したセルのハッシュを列挙して保存することです。このようにクエリを実行することは、正しい質問をすることです。

理想的な解決策はありますか？これは以前に解決されましたか？

4

1 に答える 1

0

2 つの条件を確認する必要があると思います。1 つは、ビューポートの長方形が四角形と角 (p0,p1) で重なっているということ、もう 1 つは、ビューポートの四角形のいくつかの角が線分 (p0, p1) を含む線全体の異なる側にあることです。 p1)。

長方形の重なりを見つけるタスクは、R ツリー ( http://en.wikipedia.org/wiki/R-tree )を使用して非常に多数の長方形に対して非常に効果的に解決できます。

2 番目のタスクは、(p1-p0) x (corner_coordinate-p0) の外積の符号をチェックすることに縮小できます (3 番目の座標がゼロに等しい 3 次元ベクトルとして取得される 3 つの量はすべて、結果は垂線に沿ったベクトルになります)方向）。この外積の反対符号のコーナーがあるはずです。

于 2013-02-09T22:42:16.683 に答える