私は本でこの問題を見つけ、必死に解決しようとしています。質問自体は次のとおりです。最大の高さで屋上 (平らでない屋根) を作成します。壁は 90 度の角度または平行です。
私のアプローチ：
私はすべてのエッジポイントを持っています。したがって、スキャンラインアプローチを使用できます。すべてのポイントを x 軸、次に y 軸で並べ替えます。次に、ポイントのリスト全体を調べて、壁に対して 45° の線を引きます。すでに描いた現在の線と交差する線があるかどうかを確認します。一致しない場合は、次のポイントに移動して、壁に対して 45° の別の線を引きます。最後の 2 本の線が交差する可能性が高いので、交点に新しい点を作成します。
私が抱えている問題は、特殊なケースがたくさんあるということです。私が考えていなかったより簡単な方法はありますか？この種の問題により適した他のアルゴリズムはありますか? この種の問題に対するあなたの考えは何ですか?
例:
これは、屋根がどのように見えるかを想像するものです。
多くの人が、何かが欠けているという私の質問の仕方を批判し、実際には入力が欠けていました。したがって、入力として、一連のポイントの例があります:
(0, 0) (6, 0) (6, -2) (8, -2) (8, 8) (-2, 8) (-2, 3 ) (0, 3)
を正しい順序で。
次にやらなければならないことは、写真 1 のようにポイントを配置することです。私の場合は、ポイントを少し右下に配置しました。ここで、どの点が形状内にあり、どの点が形状内にないかを確認する必要があります。これは、ポイントで作成した水平線と垂直線を建物と交差させることで簡単に見つけることができます. 奇数が見つかった場合は、ポイントがフォームにあることがわかります。それ以外の場合は削除します。
このすべての後、見つけた各ポイントから作成できる最大の長方形を見つけようとしています (赤い線)。ここで欠けているのは、右下の長方形に新しいポイントを作成し、左上に別の長方形を作成することです (黄色の線)。私の例で見たように、この例では、長方形の小さい辺を使用して最大の正方形を見つけます。これを 2 で割ると、フォームの最大の高さが得られます。
さらに明確にする必要がある場合は、遠慮なく私に尋ねてください。