0

どの方向にも進むことができる2本の平行線があります。それらは同じではないことが保証されています。

私は2Dグリッド（0.0から1.0までの非整数座標を持っていますが、これは問題全体をスケーリングすることで解決できると思います）を持っており、通常の方法で直交して配置されています。

2本の線の間に任意の領域があるすべての正方形のリストを生成するアルゴリズムが必要です。

私の現在のアルゴリズムはひどく非効率的です（2本の線を回転した長方形として表し、すべての正方形でポリゴンとポリゴンの交差をテストします）。それは動作しますが、恐ろしく遅いです。

4

1 に答える 1

2

2 本の線の方向と位置がわかっている場合は、ブレゼンハム ライン アルゴリズムを使用して、いずれかの線が「接触」するすべての「正方形」を計算できます。間に正方形を追加するのは簡単な作業です。2 つの線分が整数の「正方形」で区切られている場合、そのうちの 1 つについてブレゼンハムを解くだけで済みますが、それらの線分が整数でない場合は、両方について解く必要があります (後者も機能します)。線が平行でない場合でも)。

于 2012-11-18T23:22:46.850 に答える