2

長方形に収まるすべてのセグメントを見つけるためのデータ構造が必要です (C# では、それが主な問題でなくても)。

たとえば、セグメント [(0,0) , (10,10)] は、(5,5) から始まるサイズ (1,1) の長方形内になければなりません。

私は kdtree を試しましたが、彼の点の 1 つが長方形の中にある場合にのみセグメントを返します。セグメントを実線として認識しません。

この検索を効率的に行うには、どのようなデータ構造が必要ですか?
非常に標準的なように見えますが、検索しましたが、このケースについては何も見つかりませんでした!

問題の寸法: 6000 のセグメント、平均 20 の線セグメントが長方形内にある

重複の並べ替え:

4

3 に答える 3

1

非点オブジェクト (線分は点オブジェクトではない)の場合、 R ツリーは kd ツリーよりも適している場合があります。少数の線分 (<50) がある場合は、それらをベクトルに格納し、常にすべての線分をテストするのが最も速い方法です。

于 2011-12-19T11:48:25.110 に答える
0

私はあなたの問題の標準的なアルゴリズムを知りませんが、私の頭に浮かんだ最初のアイデアは、長方形を4本の線として表すことです。多くの線分がある場合は、すべての線分と線の交点を見つけます（線分を並べ替えて線分を作成し、それらの座標を「マージ」します）。
つまり、N * log（N）+ M * Log（M）です。ここで、N-線分の数、M-平方の数です。

その後、正方形と交差する線分を（SquareHorizLine1Intersections UNION SquareHorizLine2Intersections）INTERSECT（SquareVerticalLine1Intersections UNION SquareVerticalLine2Intersections）として見つけることができます。

ここでも、集合の共通部分と結合の複雑さはK * LogKです。ここで、Kは集合のサイズです。または、データ構造「二項ヒープ」を使用する場合は、単にlog（K）にすることもできます（フィボナッチヒープもあり、さらに効率的です）。

したがって、このアルゴリズムはN * log（N）の複雑さを持つカイクに見えます。それがお役に立てば幸いです...それとももっと良いものが必要ですか？

于 2011-12-19T11:52:49.707 に答える
0

延長された線分を (y 切片、勾配) などとしてパラメータ化してみることができます。特定の線分と交差する延長線のスペースは、線が点であるかのように照会できる (y 切片、勾配) 空間内の形状を形成します。（縦線は特例扱い）

四角形の境界線セグメントのいずれかと交差する線の結合を取り、延長されていないときに実際には四角形を横切らないセグメントを除外します。

// we will intersect against three of the rect's borders (the 4th's results are redundant)
borders = {(TopLeft, TopRight), (TopRight, BottomRight), (BottomRight, BottomLeft)}
// each border forms a shape in (y, slope) space defined by two intersecting half spaces
// we query the line space using something standard like kd-trees
lines1 = Union(borders.ForEach(LineSpace.Inside(ShapeOfSegmentInIntersectSpace(?border))))
// now filter out lines that don't cross the rect when extended
// since we already know they intersect when extended, the check is pretty simple
lines2 = lines1.Where(?line.BoundingRect.Intersects(rect))
于 2011-12-19T15:26:19.213 に答える