사각형 영역을 최대 영역의 하위 영역으로 분할

Question

사각형/사각형을 작은 영역으로 분할하고 각 하위 영역의 최대 영역을 적용하는 것은 꽤 쉽습니다. 영역을 측면 길이가 sqrt (max_area) 인 영역으로 나누고 남은 부분을주의해서 처리 할 수 ​​있습니다.

그러나 사변형으로 나는 곤란하다. 제가 모퉁이의 각도를 모른다 고 가정 해 봅시다. 네 점 모두가 같은 평면에 있다고 가정합시다. 또한 작은 영역이 모두 같은 크기 일 필요는 없습니다. 내가 가진 유일한 요구 사항은 각 개별 영역의 영역이 최대 영역보다 적다는 것입니다.

이렇게 쉽게 만들 수있는 특정 데이터 구조가 있습니까?
알고리즘을 찾을 수 없습니까?

이렇게하려면 쿼드 트리를 사용할 수 있습니까? 나는 나무에 엄청난 지식이 없지만 구조를 구현하는 방법을 알고 있습니다.

나는이 일을 할 때 GIS 작업을 염두에두고 있지만 쿼드를 분할하는 알고리즘에는 아무런 영향을 미치지 않을 것이라고 확신합니다.

Answer 1

결과 영역이 충분히 작아 질 때까지 긴 측면에서 쿼드를 반으로 반복적으로 분할 할 수 있습니다.

Answer 2

사변형이 볼록면 실제로 동일한 둘레를 갖는 두 개의 동일 면적 조각으로 나눌 수 있습니다! 이것은 공정한 분할이라고하며, The Open Problems Project에 설명되어 있습니다 (조각 수는 더 많지만 두 조각으로 해결됩니다).

비구 조형 사분면의 경우 두 개의 균등 분할로 으로 분할 선을 찾는 것이 어렵지 않습니다.
나는 이것이 작동 할 것이라고 믿는다 : 하나의 반사 꼭지점을 통과하는 선을 통과시키고 그 꼭지점을 똑같이 구획 할 때까지 회전시킨다. 영역을 두 개의 동일한 반쪽으로 분할하는 것이 유일한 목표 인 경우 볼록 다각형의 경우에도 동일한 방법이 적용됩니다.

일반적인 문제 (임의의 다각형의 경우)는 "다각형의 햄 샌드위치 섹션"이라는 이름으로되어 있습니다. 사실, 나는 정확한 제목의 종이를 썼다.