最適な長方形のハッチングアルゴリズム

Question

特定の領域のオブジェクトがハッチングを通過できるように、全体の行の長さが最短の長方形をハッチングするアルゴリズムを探しています。

たとえば、5x3 cmの長方形があり、幅1 cmの平行線を使用してハッチングすると、ハッチを通過できる最大のオブジェクトは1 cmの正方形です。全体で22 cm（4x3 + 2x5）のハッチ線を使用しました。そのため、1sqcmの面積を渡すために、22cmのハッチ線を使用しました。

アルゴリズムは、現在の22cmからの全体のハッチングラインを最小化するパターンを見つける必要がありますが、1sqcmを超える領域は通過できません（オブジェクトは正方形または長方形の形である必要はなく、全体の領域です問題）。

編集： nlucaroniのリードに続いて、 Honeycomb Conjecture 等しい面積の領域への平面の分割には、少なくとも通常の六角形のグリッドの周囲があることを示しており、私の質問に部分的に答えています。

Answer 1

テッセレーションを形成する図形が必要です。おそらく六角形が最善の策です。ただし、通過する形状がテッセレーションパターンに正確に適合しない場合はどうなりますか？

テッセレーションを調べて、パターン/スクリーン/ハッチが規則的である必要があるかどうか、テスト対象のオブジェクトなどに適合する必要があるかどうかを判断します。

実際に、面積= 1を形成する無限の直線からこれを構築する場合、できることは正方形です（先に進む、辺の比率に関して面積の最大値を見つける、または導関数を取ることによる辺の比率に関する境界）。

あなたの質問はかなり曖昧/不完全です。

Answer 2

きちんとした問題。アルゴリズムは本当にシンプルになると思いますが、「最適」なものが必要です。特定の長さのワイヤの開口サイズを最小化するために使用するスクリーン角度のセット。

実際、これはケーキカットの問題を思い出させます。ここでは、ケーキをxスライスするために最小限の数の直線カットを見つけようとしています。したがって、ソリューションは、各ワイヤについて、通過できる最大のオブジェクトのサイズを最大に縮小しようとする線に沿っている可能性があります。それは最大の「穴」を切ることを意味します。可能であれば、ワイヤーを追加して半分にします。

edit：提案されたアルゴリズムを実際に試してみたところ、単純なバージョンよりも悪い結果が得られました。ワイヤを配置するときは、必ず最小サイズを考慮する必要があります。

Answer 3

長方形をハッチングするとはどういう意味ですか？

質問を言い換えることができますか？

また、言い換えると、アルゴリズムが入力として受け取るべきものと、出力として生成すべきものを述べます。