직선 다각형

Rectilinear polygon
이 기사는 직각 폴리곤에 관한 것이다. 유클리드 원소에 지정된 정의는 다각형을 참조하십시오.
직사각형 다각형의 몇 가지 예

직선형 다각형은 가장자리 교차점이 모두 직각인 다각형이다. 따라서 각 꼭지점의 내부 각도는 90° 또는 270°이다. 직사각형 다각형은 동위원소 다각형의 특별한 경우다.

많은 경우에 다른 정의가 선호된다: 직사각형 다각형은 데카르트 좌표의 축과 평행한 면이 있는 다각형이다. 폴리곤 집합에 대해 말할 때 구별이 중요해진다. 후자의 정의는 집합에 있는 모든 폴리곤의 측면이 동일한 좌표 축과 정렬됨을 의미한다. 두 번째 정의의 틀 안에서 직선으로 된 다각형의 수평 가장자리와 수직 가장자리로 말하는 것은 당연하다.

직사각형 다각형은 직교 다각형으로도 알려져 있다. 다른 용어는 ISO 지향, 축 정렬, 축 지향 폴리곤이다. 이러한 형용사는 이러한 유형의 다각형이 직사각형일 때 덜 혼동되며 직교 직사각형과 직교 직교 직사각형도 사용되지만 축 정렬 직사각형이라는 용어를 선호한다.

직선형 다각형의 계급의 중요성은 다음과 같은 것에서 비롯된다.

  • 설계와 제작이 간편해 집적회로 마스크 레이아웃에서 형상 표현이 편리하다. 제조된 많은 물체는 직교 다각형을 초래한다.
  • 폴리곤의 관점에서 기술된 연산 기하학의 문제들은 직교 폴리곤으로 제한되었을 때 보다 효율적인 알고리즘을 가능하게 한다. 직교 폴리곤에 대한 아트 갤러리 정리에 의해 예가 제공되며, 이는 임의 폴리곤에 대해 가능한 것보다 더 효율적인 가드 커버리지로 이어진다.

요소들

직사각형 다각형은 수평과 수직의 두 가지 유형의 가장자리를 가진다.

  • 보조정리: 수평 가장자리의 수는 수직 가장자리의 수와 같다(모든 수평 가장자리는 수직 가장자리로 따르기 때문이고 그 반대의 경우도 마찬가지).
    • 코롤러리: 직교 다각형은 가장자리 수가 짝수다.
X 표시 볼록한 모서리, O 표시 오목한 모서리 파란색 선은 노브, 빨간색 선은 노브 반대, 노란색 선은 노브 어느 것도 아니다.

직사각형 폴리곤은 두 가지 유형의 모서리를 가지고 있다: 작은 각도(90°)가 폴리곤에 내부인 코너를 볼록이라고 하며 큰 각도(270°)가 있는 코너를 볼록이라고 한다. 내부는 오목이라 불린다.[1]

노브는 두 끝점이 볼록한 모서리를 가진 가장자리다. 손잡이는 두 끝점이 오목한 모서리를 가진 가장자리다.[1]

단순직선 다각형

또한 단순한 직선으로 된 다각형은 구멍이 없기 때문에 구멍이 없고 단지 하나의 연속적인 경계만 있기 때문에 구멍이 없는 것으로 불리기도 한다. 그것은 몇 가지 흥미로운 특성을 가지고 있다.

  1. 볼록코너 수는 오목코너 수보다 4개가 더 많다. 그 이유를 보려면 다각형의 경계를 시계방향으로 가로지른다고 상상하십시오(오른손으로 다각형을 안으로, 왼손으로 바깥쪽으로). 볼록한 모퉁이에서 오른쪽으로 90° 돌면, 어느 오목한 모퉁이에서든 왼쪽으로 90° 돌면 된다. 마지막으로 360°를 완전히 돌고 원래 지점으로 돌아와야 한다. 따라서 우회전 횟수는 왼쪽 회전 횟수보다 4회 이상이어야 한다.
    • 코롤러리: 모든 직사각형 폴리곤은 적어도 4개의 볼록한 모서리를 가지고 있다.
  2. 손잡이 수(두 볼록한 모서리를 연결하는 부분)는 반음쇠 수(두 오목한 모서리를 연결하는 부분)보다 4가 더 많다.이유를 보려면 X를 볼록한 모서리의 수로 하고 Y를 오목한 모서리의 수로 한다. 앞의 사실로는 X=Y+4. 볼록한 모서리에 이어 볼록한 모서리의 수를 XX로 하고, 볼록한 모서리에 이어 오목한 모서리를 XY로 하며, YX와 YY를 유사하게 정의한다. 그렇다면 X=XX+XY=XX+YX+YX+YX+YY+Y=XY+YY=YX+YYY. 따라서 XX=X-XY=X-(Y-YY)=YY+(X-Y)=YY+4.[2]
    • 코롤러리: 모든 직사각형 폴리곤은 적어도 4개의 손잡이를 가지고 있다.

직사각형 다각형의 사각형 및 직사각형

직사각형 폴리곤은 폴리곤의 가장자리와 평행한 가장자리가 있는 한정된 수의 정사각형 또는 직사각형으로 덮을 수 있다(폴리곤 피복 참조). 특정 직사각형 폴리곤 P에 포함된 여러 가지 유형의 사각형/직사각형을 구별할 수 있다.[1]

다각형 P의 최대 제곱은 P의 다른 제곱에 포함되지 않는 P의 제곱이다. 마찬가지로, 최대 직사각형은 P의 다른 직사각형에 포함되지 않은 직사각형이다.

각 인접한 가장자리 쌍이 P의 경계를 교차하는 경우 사각 s는 P에서 최대값이다. 양측의 증거는 모순에 의해 다음과 같다.

  • s의 특정 인접 쌍이 P의 경계를 교차하지 않는 경우, 이 쌍은 경계 쪽으로 더 밀리게 되므로 s는 최대치가 아니다.
  • s가 P에서 최대값이 아닌 경우, s를 포함하는 P에 더 큰 정사각형이 있다. 이 큰 정사각형의 내부는 s의 인접 가장자리 쌍을 포함하고 있으므로 이 쌍은 P의 경계를 교차하지 않는다.

첫 번째 방향은 직사각형에도 적용된다. 직사각형 s가 최대일 경우, s의 인접 가장자리의 각 쌍은 P의 경계를 교차한다. 두 번째 방향은 반드시 사실인 것은 아니다: 직사각형은 인접한 세 면에서도 P의 경계를 교차할 수 있고, 네 번째 면에서도 연장될 수 있기 때문에 최대가 될 수 없다.

Corolarary: P의 모든 최대 제곱/직각은 P의 경계를 교차하는 두 개의 반대쪽 가장자리에 최소 두 개의 점을 가진다.

모서리 사각형은 P의 볼록한 모서리와 적어도 s의 한 모서리가 겹치는 폴리곤 P의 최대 제곱 s이다. 모든 볼록한 모서리에 대해, 정확히 하나의 최대(코너) 사각형이 그것을 덮고 있지만, 하나의 최대 사각형이 한 코너 이상을 덮을 수 있다. 모든 모퉁이에, 그것을 덮는 많은 다른 최대 직사각형들이 있을 수 있다.

연속기와 분리기
연속체 유형

폴리곤 P의 구분자 사각형은 P-s가 연결되지 않는 P의 제곱 s이다.

  • 보조정리: 단순한 직선으로 된 다각형에서, 손잡이를 포함하지 않는 최대 제곱은 분리형이다.[3] 손잡이를 포함하는 사각형은 분리기가 될 수도 있고 아닐 수도 있다. 서로 다른 구분 기호 사각형의 수는 무한할 수 있고 심지어 셀 수 없을 수도 있다. 예를 들어, 직사각형에서, 모든 최대 사각형은 짧은 면들 중 하나에 닿지 않는 분리형이다.

연속기 사각형은 s의 경계와 P의 경계 사이의 교차점이 연속되도록 다각형 P의 제곱 s이다. 최대 연속기는 항상 코너 사각형이다. 게다가, 최대 연속기는 항상 손잡이를 가지고 있다. 따라서 연속기 수는 항상 유한하며 노브 수로 제한된다.

포함하는 노브 수와 내부 구조에 따라 몇 가지 다른 유형의 연속기가 있다(그림 참조). 연속기의 발코니는 다른 최대 제곱으로 덮이지 않는 점으로 정의된다(그림 참조).

어떤 사각형도 연속기와 분리기가 될 수 없다. 일반적인 다각형에서는 연속기도 분리기도 아닌 정사각형이 있을 수 있지만, 단순한 다각형에서는 다음과 같은 일이 일어날 수 없다.[1]

  1. 단순직선형 다각형에서 모든 최대 제곱은 분리형 또는 연속형이다. 이것은 직사각형에도 해당된다: 모든 최대 직사각형은 분리형 또는 연속형이다.
  2. 사각형이 아닌 단순한 직사각형 다각형에는 적어도 두 개의 연속체가 있다.

단순한 폴리곤의 최대 제곱과 나무의 노드 사이에는 흥미로운 유사점이 있다: 연속체는 리프 노드와 유사하고 분리기는 내부 노드와 유사하다.

특례

가장 단순한 직사각형인 직사각형은 축 정렬 직사각형이다. 직사각형은 x축에 평행하고 y축에 평행한 2면이 있다. 참고 항목: 최소 경계 사각형.

골리곤(Golygon)은 직선으로 된 다각형이며, 순차적으로 옆면 길이가 연속 정수로 되어 있다.

직사각형이 아닌 직사각형 다각형은 결코 볼록하지 않지만 직교 볼록할 수 있다. 직교 볼록한 직선형 다각형을 참조하십시오.

단조직선 다각형은 또한 직선으로 된 단조직선 다각형이다.

T-제곱은 흥미로운 성질을 가진 일련의 직선으로 된 다각형에서 생성된 프랙탈이다.

일반화

직선 폴리곤과 관련된 알고리즘 문제

대부분은 일반 폴리곤에 대해서도 언급될 수 있지만, 보다 효율적인 알고리즘에 대한 기대는 별도의 고려가 필요하다.

직사각형 분해

직사각형 다각형에 특히 관심이 있는 것은 주어진 직사각형 폴리곤을 단순한 단위(일반적으로 직사각형 또는 사각형)로 분해하는 문제들이다. 분해 문제에는 몇 가지 유형이 있다.

  • 문제를 다룰 때 목표는 조합이 폴리곤과 동일한 최소 단위(제곱 또는 직사각형)를 찾는 것이다. 유닛이 중복될 수 있다. 다각형 덮개를 참조하십시오.
  • 포장 문제에서 목표는 폴리곤에 유니언이 들어 있는 가장 큰 오버랩되지 않는 유닛 세트를 찾는 것이다. 결합은 다각형보다 작을 수 있다.
  • 분할 문제에서 목표는 조합이 폴리곤과 정확히 동일한 최소의 겹치지 않는 단위 세트를 찾는 것이다. 폴리곤 파티션을 참조하십시오.

참조

  • Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer. ISBN 0-387-96131-3. 1st edition: ; 2nd printing, corrected and expanded, 1988., 8장: "직사각형의 기하학"
  1. ^ a b c d Bar-Yehuda, R.; Ben-Hanoch, E. (1996). "A Linear-Time Algorithm for Covering Simple Polygons with Similar Rectangles". International Journal of Computational Geometry & Applications. 06: 79–102. doi:10.1142/S021819599600006X.
  2. ^ "Counting pairs of bits". Stack Exchange. November 17, 2013.
  3. ^ Albertson, M. O.; o’Keefe, C. J. (1981). "Covering Regions with Squares". SIAM Journal on Algebraic and Discrete Methods. 2 (3): 240. doi:10.1137/0602026.