直線ポリゴン

直線ポリゴンは、エッジの交点がすべて直角になっているポリゴンです。したがって、各頂点の内角は90°または270°です。直線ポリゴンは、等辺ポリゴンの特殊なケースです。

多くの場合、別の定義が望ましい： 直線ポリゴンは、デカルト座標の軸に平行な辺を持つポリゴンです。区別は、ポリゴンのセットについて話すときに重要になります。後者の定義は、セット内のすべてのポリゴンの辺が同じ座標軸に揃えられることを意味します。 2番目の定義のフレームワーク内では、直線ポリゴンの水平エッジと垂直エッジについて話すのが自然です。

直線ポリゴンは、 直交ポリゴンとも呼ばれます。使用されている他の用語は、 iso-oriented 、 axis-aligned 、およびaxis-orientedポリゴンです。これらの形容詞は、このタイプのポリゴンが長方形である場合に混乱が少なく、 軸に合わせた長方形という用語が推奨されますが、 直交長方形と直線長方形も使用されます。

直線ポリゴンのクラスの重要性は、以下から来ています。

これらは、設計と製造が簡単なため、集積回路マスクレイアウトで形状を表現するのに便利です。製造されたオブジェクトの多くは、直交ポリゴンになります。
ポリゴンの観点から述べられた計算ジオメトリの問題は、多くの場合、直交ポリゴンに制限されると、より効率的なアルゴリズムを可能にします。例は、直交ポリゴンのアートギャラリー定理によって提供されます。これにより、任意のポリゴンの場合よりも効率的なガードカバレッジが得られます。

要素

直線ポリゴンには、水平と垂直の 2つのタイプのエッジがあります。

補題：水平方向のエッジの数は、垂直方向のエッジの数に等しくなります（すべての水平方向のエッジの後に垂直方向のエッジが続き、逆も同様です）。
- 系：直交ポリゴンのエッジの数は偶数です。

直線ポリゴンには2つのタイプのコーナーがあります。小さい角度（90°）がポリゴンの内側にあるコーナーを凸と呼び、大きい角度（270°）が内側にあるコーナーを凹と呼びます。

ノブは、2つの端点が凸状の角であるエッジです。 アンチノブは、2つの端点が凹型のコーナーであるエッジです。

シンプルな直線ポリゴン

単純な直線ポリゴンは、穴がなく、連続した境界が1つしかないため、 穴なしとも呼ばれます。いくつかの興味深い特性があります：

凸状の角の数は、凹状の角の数よりも4つ多くなります。理由を確認するために、ポリゴンの境界を時計回りに（右手はポリゴンの内側に、左手は外側に）トラバースすることを想像してください。凸状の角で、右に90度回転します。凹面のコーナーでは、左に90度回転します。最後に、360°全体を回転させて元のポイントに戻る必要があります。したがって、右折の数は左折の数よりも4多い必要があります。
- 結果：すべての直線ポリゴンには、少なくとも4つの凸状コーナーがあります。
（2つの凸角部を結ぶ辺）ノブの数がantiknobsの数よりも4以上である（二凹状の隅を結ぶ辺）は、Xが凸角部及びY凹形コーナーの数の数とする、なぜ参照.TO。前の事実により、 X = Y + 4です。 XXを凸コーナーの数、それに続く凸コーナーを、 XYを凸コーナーの数に続いて凹コーナー、 YXおよびYYを同様に定義します。その後、明らかにX = XX + XY = XX + YXおよびY = XY + YY = YX + YYです。したがって、 XX = X-XY = X-（Y-YY）= YY +（XY）= YY + 4です。
- 結果：すべての直線ポリゴンには少なくとも4つのノブがあります。

直線ポリゴンの正方形と長方形

直線ポリゴンは、ポリゴンのエッジに平行なエッジを持つ正方形または長方形の有限数でカバーできます（ポリゴンのカバーを参照）。特定の直線ポリゴンPに含まれるいくつかのタイプの正方形/長方形を区別することができます。

ポリゴンPにおける最大の正方形は、P内の任意の他の正方形に含まれていないPに正方形です。同様に、最大の長方形はPの他の長方形に含まれない長方形です。

複数の隣接する縁の各対は、Pの境界を交差する場合正方形Sは Pで最大です。両側の証拠は矛盾によるものです。

sの特定の隣接するペアがPの境界と交差しない場合、このペアは境界に向かってさらにプッシュされるため、 sは最大ではありません。
sが Pで最大でない場合は、Sを含有するPが大きい正方形があります。この大きな正方形の内部にはsの隣接するエッジのペアが含まれているため、このペアはPの境界と交差しません。

第1の方向は、即ち、矩形についても真である：矩形Sが最大である場合、Sの隣接する縁の各対は、Pの境界と交差します。 2番目の方向は必ずしも正しいとは限りません。長方形は3つの隣接する辺でさえPの境界と交差できますが、4番目の辺で引き伸ばすことができるため、最大ではありません。

推論：P内のすべての最大の正方形/長方形は、Pの境界を交差する二つの対向するエッジに、少なくとも2つの点を有します。

隅角は、Sの少なくとも一つの角部がPの凸型の角部に重なるようポリゴンPの最大正方形sです。すべての凸角には、それを覆う最大（角）正方形が1つだけありますが、単一の最大正方形は複数の角を覆う場合があります。すべてのコーナーについて、それをカバーする多くの異なる最大の長方形があるかもしれません。

複数接続されていない-ポリゴンPにおけるセパレータ四角は PがそのようPに正方形sです。

補題：単純な直線の多角形では、ノブを含まない最大の正方形がセパレーターです。ノブを含む正方形は、セパレーターである場合とそうでない場合があります。異なるセパレータの正方形の数は無限であり、数え切れない場合さえあります。たとえば、長方形では、短い方の辺のいずれにも触れない最大の正方形がすべてセパレーターです。

連続正方形は、 sの境界とP の境界との交差が連続するような、多角形Pの正方形sです。最大連続体は常に角の正方形です。さらに、最大の継続子には常にノブが含まれます。したがって、継続子の数は常に有限であり、ノブの数によって制限されます。

含まれるノブの数とその内部構造に基づいて、いくつかの異なるタイプの継続子があります（図を参照）。連続体のバルコニーは、他の最大の正方形で覆われていないポイントとして定義されます（図を参照）。

正方形は、継続者でも分離者でもありません。一般的なポリゴンでは、連続体でもセパレータでもない正方形が存在する場合がありますが、単純なポリゴンではこれは起こりえません。

単純な直線ポリゴンでは、すべての最大の正方形がセパレーターまたは継続体です。これは、長方形にも当てはまります。すべての最大長方形は、セパレーターまたは継続体のいずれかです。
正方形ではない単純な直線ポリゴンには、少なくとも2つの連続体があります。

単純なポリゴンの最大の正方形とツリーのノードの間には興味深い類似性があります。継続子はリーフノードに似ており、セパレータは内部ノードに似ています。

特殊なケース

最も単純な直線ポリゴンは、軸に沿って配置された長方形です。x軸に平行な2つの辺とy軸に平行な2つの辺を持つ長方形です。参照：最小境界矩形。

ゴリゴンは、辺の長さが連続した整数である直線多角形です。

長方形ではない直線ポリゴンは決して凸状ではありませんが、直角に凸状になる場合があります。 直交凸正多角形を参照してください。

単調な直線ポリゴンは、 直線的な単調なポリゴンです。

T-squareは、興味深いプロパティを持つ一連の直線ポリオンから生成されたフラクタルです。

汎化

直交多面体-直交ポリゴンを3Dに自然に一般化したもの。
直線性

直線ポリゴンを含むアルゴリズムの問題

それらのほとんどは、一般的なポリゴンについても同様に述べられますが、より効率的なアルゴリズムの期待は、別個の考慮を必要とします

直交範囲検索
直交凸包構造
直交ポリゴン（たとえば、交差と結合）のポリゴンのブール演算
直線的障害物間の運動計画/経路計画/ルーティング
視認性の問題（照明の問題）
- 直線的なアートギャラリーの問題
最大の空の長方形

矩形分解

直線ポリゴンに特に興味深いのは、与えられた直線ポリゴンを単純な単位（通常は長方形または正方形）に分解する問題です。分解の問題にはいくつかのタイプがあります。

問題をカバーする際の目標は、ユニオンがポリゴンと等しい最小単位のセット（正方形または長方形）を見つけることです。ユニットは重複する場合があります。ポリゴンカバーを参照してください。
パッキング問題の目標は、ユニオンがポリゴンに含まれる重複しないユニットの最大セットを見つけることです。ユニオンはポリゴンよりも小さい場合があります。
分割問題の目標は、結合がポリゴンと完全に一致する、重複しないユニットの最小セットを見つけることです。