直線多角形

直線多角形は、すべての辺が直角に交わる多角形です。したがって、各頂点の内角は 90° または 270° のいずれかになります。直線多角形は等角多角形の特殊なケースです。

多くの場合、別の定義が望ましいです。直線多角形は、直交座標の軸に平行な辺を持つ多角形です。多角形の集合について話すとき、この区別は重要になります。後者の定義は、集合内のすべての多角形の辺が同じ座標軸に揃っていることを意味します。2 番目の定義の枠組みの中では、直線多角形の 水平エッジと垂直エッジについて話すのは自然です。

直線多角形は、直交多角形とも呼ばれます。他に使用されている用語には、等方向、 軸平行、軸指向多角形などがあります。これらの形容詞は、このタイプの多角形が長方形である場合に混乱が少なく、軸平行長方形という用語が好まれますが、直交長方形や直線長方形も使用されています。

直線多角形のクラスの重要性は、次の点から生じます。

• 設計と製造が簡単なため、集積回路 マスク レイアウトで形状を表現するのに便利です。製造されるオブジェクトの多くは、直交多角形になります。
• 多角形の観点から表現される計算幾何学の問題では、直交多角形に限定すると、より効率的なアルゴリズムが実現できる場合がよくあります。直交多角形のアート ギャラリー定理がその例であり、任意の多角形の場合よりも効率的なガード カバレッジを実現します。

直線多角形には、水平方向と垂直方向の2 種類のエッジがあります。

• 補題: 水平辺の数は垂直辺の数に等しい (すべての水平辺の次には垂直辺が続き、その逆も同様であるため)。
  • 系: 直交多角形には偶数の辺があります。

直線多角形には2種類の角があります。小さい方の角度（90°）が多角形の内側にある角は凸角と呼ばれ、大きい方の角度（270°）が内側にある角は凹角と呼ばれます。^[1]

ノブとは、2つの端点が凸角である辺のことである。アンチノブとは、2つの端点が凹角である辺のことである。^[1]

単純な直線多角形は、穴がなく、連続した境界が 1 つしかないため、 穴なし多角形とも呼ばれます。これには、次のような興味深い特性があります。

1. 凸角の数は、凹角の数より 4 つ多くなります。その理由を理解するには、多角形の境界を時計回りに (右手を多角形の内側に、左手を外側にして) 移動すると想像してください。凸角では右に 90 度回転し、凹角では左に 90 度回転します。最後に、360 度回転して元の地点に戻る必要があります。したがって、右に回転する数は左に回転する数より 4 つ多くなければなりません。
   • 帰結: すべての直線多角形には少なくとも 4 つの凸角があります。
2. ノブ（2つの凸角を結ぶ辺）の数は、反ノブ（2つの凹角を結ぶ辺）の数より4つ多い。その理由を確認するために、Xを凸角の数、Yを凹角の数としよう。前の事実により、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となる。^[2]
   • 帰結: すべての直線多角形には少なくとも 4 つのノブがあります。

直線多角形は、多角形の辺と平行な辺を持つ有限個の正方形または長方形で覆われる（多角形被覆を参照）。ある直線多角形Pに含まれる正方形/長方形には、いくつかの種類がある：^[1]

多角形P内の最大正方形とは、 P内の他のどの正方形にも含まれないP内の正方形のことです。同様に、最大長方形とは、 P内の他のどの長方形にも含まれない長方形のことです。

正方形sがPにおいて最大となるのは、 sの隣接する辺の各ペアがPの境界と交差する場合です。両辺の証明は背理法によって行われます。

• s内の特定の隣接ペアがPの境界と交差しない場合は、このペアは境界に向かってさらに押し進められるため、sは最大ではありません。
• s がP内で最大でない場合、 P内にs を含むより大きな正方形が存在します。このより大きな正方形の内部にはsの隣接する辺のペアが含まれており、したがってこのペアはPの境界と交差しません。

最初の方向は長方形にも当てはまります。つまり、長方形sが最大である場合、 sの隣接する辺の各ペアはPの境界と交差します。2 番目の方向は必ずしも当てはまりません。長方形は、隣接する 3 つの辺でもPの境界と交差し、4 番目の辺で引き伸ばされる可能性があるため、最大ではない場合があります。

系: P内のすべての最大の正方形/長方形には、 2 つの反対の辺上に、 Pの境界と交差する少なくとも 2 つの点があります。

コーナースクエアとは、多角形P内の最大の正方形sで、 sの少なくとも 1 つのコーナーがPの凸コーナーと重なるものです。すべての凸コーナーには、それを覆う最大の (コーナー) 正方形が 1 つだけ存在しますが、1 つの最大正方形が複数のコーナーを覆うこともあります。すべてのコーナーには、それを覆うさまざまな最大長方形が存在する場合があります。

多角形P内の区切りの正方形とは、 P − sが連結されていないP内の正方形sのことです。

• 補題：単純な直線多角形において、突起を含まない最大の正方形はセパレータである。^[3]突起を含む正方形はセパレータである場合もそうでない場合もある。異なるセパレータ正方形の数は無限であり、無数である場合もある。たとえば、長方形では、短辺の1つに接していないすべての最大の正方形はセパレータである。

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

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

正方形は連続線と区切り線の両方になることはできません。一般的な多角形には、連続線でも区切り線でもない正方形が存在する可能性がありますが、単純な多角形にはそのようなことは起こりません。^[1]

1. 単純な直線多角形の場合、すべての最大の正方形は区切り線または連続線のいずれかになります。これは長方形の場合にも当てはまり、すべての最大の長方形は区切り線または連続線のいずれかになります。
2. 正方形ではない単純な直線多角形には、少なくとも 2 つの連続線が存在します。

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

最も単純な直線多角形は、軸に沿った長方形、つまり 2 辺が x 軸に平行で、2 辺が y 軸に平行な長方形です。最小外接長方形も参照してください。

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

長方形でない直線多角形は凸ではありませんが、直交凸になることがあります。「直交凸直線多角形」を参照してください。

単調な直線多角形は、直線でもある 単調な多角形です。

Tスクエアは、興味深い特性を持つ一連の直線多角形から生成されるフラクタルです。

それらのほとんどは一般多角形にも当てはまるが、より効率的なアルゴリズムが期待されるため、別途検討する必要がある。

• 直交範囲検索
• 直交凸包の構築
• 直交多角形に対するブール演算（交差や結合など）
• 直線障害物間の動作計画/経路計画/ルーティング
• 視認性の問題（照明の問題）
• 最大の空の四角形

直線多角形に関して特に興味深いのは、与えられた直線多角形を単純な単位（通常は長方形または正方形）に分解する問題です。分解問題にはいくつかの種類があります。

• 被覆問題では、結合すると多角形と等しくなる最小の単位 (正方形または長方形) のセットを見つけることが目標です。単位は重なり合う場合があります。「多角形被覆」を参照してください。
• パッキング問題では、その目標は、多角形にその和集合が含まれる、重複しない単位の最大集合を見つけることです。和集合は多角形よりも小さくなる場合があります。
• 分割問題では、その目的は、結合がポリゴンと正確に等しい、重複しない単位の最小セットを見つけることです。「ポリゴン分割」を参照してください。

• 直交多面体。直交多角形を 3D に自然に一般化したものです。

• Franco P. PreparataおよびMichael Ian Shamos ( 1985 )。計算幾何学入門。Springer。ISBN 0-387-96131-3初版、第2刷、訂正・増補、1988年。第8章「長方形の幾何学」