私は、線の並びの境界ボックスを（平行線なしで）計算したいと思います。境界ボックスには、線の配置のすべての交点が含まれている必要があります。O（n log n）時間での線配置の境界ボックス
私はいくつかの研究を行い、境界ボックスを計算することはO（n log n）時間で可能でなければならないことを何度も発見しました。残念ながら私はこの主張の原因を見つけることができませんでした。
私はO（n log n）時間でこの問題を解決するアルゴリズムを考案しようとしましたが、今までできませんでした。私はエンベロープを計算するために二重性を使用しようとしましたが、残念ながら、エンベロープは必ずしも最低と最高の交差点を含むわけではありません。
誰かがそのようなアルゴリズムを見つける場所やその仕組みを知っていれば、私は感謝します。
O（n log n）時間で実行できます。すべての交差点を確認する必要はありません。最高と最低のx座標とy座標を持つものを見つけるだけです。
ここで私が思いついたのです。私たちは同じ講義をしていると思いますが、これは私が手に入れようとしているものなので、このソリューションを使用したい場合は貼り付けてください。
左側の結合のためのアルゴリズム：
1）ポイントライン双対Lに応じたポイントにラインを作る：Y = MX + C => L * =（M、-c）。 O（n）
2）x座標で注文します。 3）最初の2つの点の線を最も低い傾きの線として保存します。 4）ポイントを通過し、2つのポイントP [i]およびP [i + 1]のラインが、以前に保存された最も低いスロープよりも低いスロープを有する場合、そのラインを最も低いスロープを有するラインとして保存する。 O（n）
5）もう一度二重性を使って線を点にします。O（1）
6）その点のx座標を左端として返します。 O（1）
斜線が最も小さい行は、最小のx座標との交点を表します。右辺は同じであるが、最も高い傾きで動作する。上下限のアルゴリズムを得るためには、以下のように決定するためにl：y = mx + c => l * =（-c、m）（基本的には平面を90度回転させる）斜面を見ることによって最も低い交差点と最も高い交差点にもなります。
スティープスロープを見つけるために、すべての交点を見る必要はありません。x座標で隣り合っている線を見るだけで十分です。
'最も低い傾きの線は、最も低いx座標の交点を表します。 ' - nice。あなたはなぜ* "* x *の二重隣人"（ "勾配の元の隣人"）だけが考慮される必要があると主張できますか？ – greybeard
私はあなたが何を意味するのか分かりません...なぜ私は2点のすべての組み合わせではなく、x座標でソートされたリスト内で互いに隣り合っている点だけを見て説明しますか？ – PelicanFive
@greybeard勾配（A）<勾配（B）および交点pを有する2つの線AおよびBを考える。勾配（A）<勾配（X）<勾配（B）の第3行Xは、pの左右に2つの交点を持つか、または新しい交点はpに等しくなります。どちらの場合も、pを無視することができます。 – Lucius
私はいくつかの研究を行い、 境界ボックスを計算することはO（n log n）時間で可能でなければならないことを数回見つけました。
私はその前提に挑戦します。 n行の場合、O（n^2）個の交点を持つケースを構築できます。これらすべての交点を検索し、それらの周りにバウンディングボックスを構築することは、実行時に、少なくとも二次でなければなりません（オメガ（N^2））
単純に次のような方法で問題にアプローチできます。
使用をBentley–Ottmann algorithmを使用して、ラインのすべての交点を見つけます。 k個の交点を有するn本のラインが与えられると、このアルゴリズムはランタイムの複雑さがO（（n + k）log n）となる。交差点がたくさんある場合は、単純なアルゴリズム（線の各ペアの交点を計算する）が速くなり、O（n^2）になります。
すべてのk個の交差点で実行し、すべての交差点の境界ボックスを取得するために各次元で最小値と最大値を見つけます。これにはO（k）の実行時間があります。
セグメントまたは無限のライン？ – MBo
'no parallel lines'（ソート）は無限の呪文です。*そうでないかぎり、プレーン軸*に平行な線はありません。 – greybeard