お気づきかもしれませんが、私はこの問題に戻ってきます。この種の問題を解き明かすのが好きなこともありますが、とても簡単に思えるようなエレガントなアルゴリズムを見つけることができなかったので少しイライラしたこともあります。
まあ、だまされてはいけません。これは簡単なポイント操作で解決できる些細な問題ではありませんが、確かにそのように見えます。この理由の一部は、ポイントのみを操作していると思いますが、線分とそれらで囲まれた領域も暗黙的に操作しているためです。これらの線分にも独自の制約があります（つまり、線分は常に1つまたはより多くの閉じたチェーンであり、それらを定義する頂点を除いて交差することはできません）。
また、アルゴリズムは、フィードするあらゆる種類の入力に対して機能する必要があります。つまり、フィードしたポリゴンがアルゴリズムに合わない方向に向いているという理由だけで、答えがない、または間違った答えを生成することは許可されていません。
ただし、できることは、アルゴリズムが受け入れる入力のタイプを制限することです。したがって、入力ポリゴンに軸に位置合わせされたセグメントのみが含まれていることを要求することは完全に有効です。
（「間違った方向に向けられた」と「軸に沿ったセグメントのみ」の違いは、最初の基準はアルゴリズムでテストせずに決定できない漠然とした基準であるのに対し、2番目の要件は可能であるということです）。
要約すると、直線多角形（つまり、軸に沿った線分のみで構成される）を長方形に水平に分割する方法を探しています。
直線多角形の例
計画は次のとおりです。
- ビルディングブロックを選ぶ
- 追加の頂点を許可する
- グリッド上に配置します。
- 不等サイズのグリッドセルでの作業。
- ポリゴンの内側にあるセルはどれですか？
- 長方形の作成。
ビルディングブロックを選ぶ
これらは実装の詳細ですが、これを前もって明確にしておくと、アルゴリズムがどのように機能するかをよりよく理解するのに役立つ場合があります。
コードでは、次のタイプのオブジェクトを基本的な構成要素として使用して、ポリゴンを次のように表現します。
- x座標とy座標で構成されるポイント。（たとえば、Point2D.Doubleを使用します）
- 開始点と終了点で構成されるセグメント（例：Line2D.Doubleを使用）
- セグメントの閉じたチェーンで構成されるポリゴン（たとえば、Line2D.DoubleのArrayListを使用）。1つのセグメントは、次のセグメントの開始点と同じ点で終了します。
また、2次元配列としてモデル化できるグリッドを使用します。
追加の頂点を許可します。
「長方形は、既存の座標で開始および終了する交差する線を使用して形成する必要があります。」と述べました。ただし、ほとんどの直線ポリゴンは、既存の頂点のみを使用して長方形に分割できないことに注意してください。上記の例（および前に提供したキャラバンの例）を参照してください。
したがって、実際には新しい頂点を明示的に作成しない場合でも、この制約を適用する必要があります。
グリッド上に配置します。
思考実験：ポリゴンが長さ10、20、30、または40の（軸に沿った）セグメントのみ、つまり10の倍数で存在する場合はどうなりますか？次に、ポリゴンをグリッドに投影し、ポリゴンの内側にあるグリッドセルを使用して長方形を構成します。また、これらの長方形の寸法を決定するのは簡単です。ポリゴンの内側にある水平方向に連続するセルの数を数え、10を掛けるだけです。それがあなたの幅です。
グリッドに揃えられたポリゴン
ただし、次の点を除いて、良い考えです。
- ポリゴンは、同じまたは複数の長さのセグメントのみで構成されているわけではありません
- どのグリッドセルがポリゴンの内側にあるかをどのように判断しますか？
次に、これらの各問題に取り組みます。
不等サイズのグリッドセルでの作業。
あなたがそれについて考えるならば、すべてのグリッドセルが同じ幅と高さを持つ本当の理由はありません。したがって、ポリゴンが完全に整列するように間隔を空けて配置されたグリッドを考案できます。
グリッドの水平軸の幅を取得するには：
- ポリゴンを構成する頂点のすべてのx座標を収集します。
- 重複を排除し、値が大きくなるにつれて並べ替えます。
- 次に、2つの後続の値の差が、その列の幅を定義します。
ポリゴンに位置合わせされたグリッド
明らかに、セルの高さは同じ方法で決定できます。これらの幅と高さを決定し、それぞれとと呼ばれる2つの配列に格納する必要がありgridWidthsますgridHeights。
セルの数とその寸法がわかったので、グリッドコンテンツのモデリングを開始できます。
ポリゴンの内側にあるセルはどれですか？
ポリゴンは線分のチェーンとして保存されていることに注意してください。グリッドセルがこのポリゴンの内側にあるかどうかを判断するには、偶数のルールを使用できます。ポリゴンの外側*からテストするセルの中心まで線分を作成し、この線分との交点の数を数えます。ポリゴンのセグメント（つまり、Line2D.DoubleのintersectsLine（）メソッドを使用します）。数が偶数の場合はポリゴンの外側にあり、奇数の場合はポリゴンの内側にあります。
*-セルの中心の間に水平線分のみを作成することをお勧めします（例に示すように）。これにより、セグメントの端点と交差するリスクがなくなります。これは、0または2の交差としてカウントされ、カウントの合計を台無しにする可能性があります。 。
したがって、このグリッドgridをブール値の2次元配列としてモデル化します。グリッドの各セルをこのように処理し、対応するスポットをgridtrue（ポリゴンの内側）またはfalse（ポリゴンの外側）としてマークします。
偶数奇数ルールに基づく内側（T）または外側（F）
長方形の作成。
これで、ポリゴンのグリッド表現と、各セルの実際の幅と高さが得られたので、長方形の作成を開始できます。各長方形の幅と高さだけに関心があり、長方形を形成する実際の頂点座標には関心がないと仮定します（これも簡単ですが）。
Foreach row in grid
run_start = null
Foreach cell C in row
if C is marked as true and run_start = null
//Found the start of a new run
run_start = C
else if C is marked as false and run_start != null
//Found the end of a run
The cells [run_start...C] form a horizontal rectangle.
Use the gridWidths and gridHeights arrays to determine the
dimensions, and report this rectangle as a result
//Prepare for the next run
run_start = null
長方形に分割されたポリゴン。
左上の2つの長方形は、同じ開始x座標と終了x座標を共有しているため、1つの長方形と見なすことができることに注意してください。必要に応じて、これらのタイプの長方形をマージする追加のパスを実装できます。
結論
直線ポリゴンをグリッドにマッピングすることで、より高度な幾何学的データ構造に頼ることなく、長方形に水平に簡単に分割できます。
このアルゴリズムをより高速に実行するためにいくつかの最適化が可能であることに注意してください。ただし、現在の入力サイズではそれほど重要ではないと思います。これにより、実装がより困難になります。
