すべてのセグメントを矩形にするためにデータ構造が必要です（主な問題ではないにしてもC＃で）。線分の検索に最適なデータ構造は何ですか？
例として、セグメント[（0,0）、（10,10）]はサイズ（1,1）で（5,5）から始まる矩形内になければなりません。
私はkdtreeを試しましたが、ポイントの1つが矩形内にある場合はセグメントのみを返します。セグメントが連続線として表示されません。
この検索を効率的に行うには、どのような種類のデータ構造が必要ですか？
非常に標準的なように見えますが、このケースでは検索しましたが、何も見つかりませんでした。
問題寸法：重複の6000個のセグメント、平均20線分が矩形である
分類：非点オブジェクトについて
（ラインセグメントはポイントオブジェクトではありません）R-treeはkd-treeよりも適しています。少数の線分（< 50）をベクトルに格納し、それらのすべてを常にテストするのが最速の方法かもしれません。
問題の標準的なアルゴリズムはわかりませんが、私の頭に浮かんだ最初のアイデアは、四角形を4行で表し、多くの線分がある場合 - すべての線分と線の交点を見つけます線分と線分をソートして座標を「マージ」します）。
N * log（N）+ M * Log（M）です。ここでNは線分の数、Mは正方形の数です。もし
再設定交点とunitions KはのサイズであるK * LogKの複雑さを有する（SquareHorizLine1Intersections UNION SquareHorizLine2Intersections）INTERSECT（SquareVerticalLine1Intersections UNION SquareVerticalLine2Intersections）として正方形と交差する線分を見つけることができる。その後
セット。また、データ構造「二項ヒープ」（さらに効率的なフィボナッチヒープもあります）を使用する場合は、単にログ（K）してください。
このアルゴリズムは、KikeがN * log（N）の複雑さを持つように見えます。私はそれが助けてくれることを願っています。
拡張線分を（y切片、勾配）または同様のものとしてパラメータ化することができます。与えられた線分と交差する延長線の間隔は、線が点であるかのように照会できる（y切片、勾配）空間の形を形成します。
rectの境界線セグメントのいずれかと交差する線の和集合を取ってから、それらが延長されていないときに実際に矩形を横切っていないセグメントをフィルタリングして除外します。
// 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))
あなた自身で作成してみませんか？それはまっすぐ私に見えます。 –
"落ち込む"とは、セグメントが長方形と交差することを意味しますか？ –
さて、交差は1つのケースであり、もう1つはセグメントが矩形内にentierlyである場合です –