各正方形に対してユーザーが指定した座標と辺の長さに応じて、正方形の円周を画面に出力するプログラムを作成しています。
下の正方形が上の正方形によって隠されるように、正方形が重なっている場合は、正方形が互いに重なっている必要があります。
正方形の順序は、プログラムに入力された順序に従って設定されます (最初が下)。
例えば：
&&&&
& &
& &$$$
&&&& $
$
$ $
$$$$$
私が思いついた最良のアルゴリズムは、各正方形の時間計算量が O(n^2) であることです。
正方形を「非透明」にする方法について何か提案はありますか?
あなたO(n^2)が言及しているアルゴリズムは、おそらく古典的な「ペインターのアルゴリズム」であり、正方形を下から上に次々とレンダリング (「ラスタライズ」) するだけです。これは完全に優れたアルゴリズムであり、コンピュータ グラフィックスで広く使用されています。ただし、どの「ラスター」アルゴリズムでも、O(n^2)正方形あたりの時間の複雑さは同じになります。
しかし、漸近的に高速なアルゴリズムが必要な場合は、「ベクトル」アルゴリズムを探す必要があります。つまり、正方形のエッジで機能するが、内部の処理に時間を無駄にしないアルゴリズムです。このようなアルゴリズムを構築する 1 つの方法は、最終的な可視エッジ レイアウトをベクトル形式で事前に計算してから、可視エッジのみを画面に描画することです。
そのようなものを実装するには、各正方形を最初に 4 つのエッジのセットで表す必要があります。次に、スイープ ラインアルゴリズムの 1 回のパスで、見えないエッジが削除されます。その後、画面に表示されている残りのエッジをレンダリングできます。このアルゴリズムは、スイープとエッジ除去ロジックを実装する必要があるため、「画家のアルゴリズム」よりもはるかに複雑になります。しかし、この特定の問題 (特に直交幾何学を扱うことを考えると) については、それほど難しくありません。
PS ここでの 1 つの重要な点は、後者のアプローチは、すべての正方形が事前にわかっている場合にのみ機能するということです。つまり、オフラインの問題にのみ適用できます。オンラインの問題を扱っている場合、つまり、入力から四角形を受け取ったらすぐに描画する必要があり、事前にすべての四角形を把握していない場合、通常、ここで何かを改善しようとする理由はありません。ペインターのアルゴリズムを使用するだけです。