다각형 내부의 축 정렬 사각형 찾기

Question

(꼭 볼록하지 않은) 다각형 내부에 축 정렬 사각형을 찾기위한 좋은 알고리즘을 찾고 있습니다. 최대의 직사각형은 멋지지만 필요하지는 않습니다. "상당히 좋은"직사각형을 찾을 수있는 어떤 알고리즘이라도 괜찮습니다.

다각형에도 구멍이있을 수 있지만 볼록 또는 단순 다각형에서만 작동하는 알고리즘에 대한 포인터도 도움이됩니다.

내 구현에서는 측면에 대한 교차 테스트가 상당히 저렴하지만 "다각형 테스트"는 비용이 많이 들기 때문에 이상적으로 최소화해야합니다.

Answer 1

지금까지 내가 가진 것은 무차별 : 그리드를 만들고 그리드의 포인트가 다각형 안에 있으면 각 코너 나 사이드를 차례대로 확장하여 일련의 직사각형을 만듭니다. 옆구리를 치다. 그런 다음 가장 큰 것을 선택하십시오.

가장 단순하고 (그리고 매우 효과적인) 최적화는 '사각형의 점 찾기'가 타오르는 것처럼 이미 구성된 사각형 중 하나에 포함되지 않았는지 확인한 후에 그리드 점이 다각형에 있는지 여부를 테스트하는 것입니다 빠른. 분명한 이유를 들어

, 이것은 매우 느리고 부정확하다, 우아 언급하지 않기 :

Answer 2

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
볼록위한 알고리즘을 가지고, 참조가 좀 가치가있을 수도 있습니다.
비확산으로 확장 될 수 있는지 확실하지 않습니다.

Answer 3

하나의 해결책은 오목한 다각형을 볼록한 부분으로 분할 한 다음 코발의 링크를 사용하는 것입니다.

정말 근본적인 두 가지 문제가 있으므로 BSP 트리 사용과 같은 히트 테스트 문제에 대한 다른 대안을 고려해 보셨습니까? 폴리에 그리드를 배치하고 각 그리드 스퀘어에 BSP 트리를 구성하여 속도를 더욱 높일 수 있습니다. 또는 각 잎에 최대 하나의 가장자리가있는 kd- 나무?

편집 :

1. :

   KD-나무는 다음과 같은 특성을 가지고 : 나는 (그 사람에게 어떤 유용 할 수 있습니다 경우에도 지루함 출력) KD-나무에 ellaborate 것 이진수입니다.

2. 각 리프가 아닌 노드는 축에 수직 인 평면, 즉 어린이 당 한면을 따라 공간을 분할합니다. 예 : 루트를 공간을 x로 나눕니다. < x0 및 x> = x0
3. 트리 레벨은 다른 축을 따라 번갈아 가며 나타납니다.
   이
   1. 가 분할 정점 선택 : 다음과 같이 트리를 구성,

   가 히트 검출 다각형이를 사용하는 방법 등> Y - 레벨 0 (루트), 레벨 1 X에 수직 분할 을 따라서. (균형 잡힌 나무를 위해 중간에 가까운 곳에 preferrably 어딘가에).

4. 다른 정점을 두 세트로 나눕니다. 하나는 스플릿의 양쪽에 있습니다. 위의 정점은 어느 한 세트에도 들어 가지 않습니다.
5. 가장자리를 세트에도 배치하십시오. 분할 선과 교차하는 모서리는 두 세트로 들어갑니다.
6. 위의 그룹에서 재귀 적으로 자식을 구성합니다.

분할 된 꼭지점을 적절히 선택하면 나무는 log (N)에 가까운 깊이를 가져야합니다. N은 정점의 수입니다. 각 리프 노드에는 최대 하나의 에지가 있습니다. 히트 감지를 수행하려면 :

1. 포인트가 속하는 리프를 찾으십시오.
2. 리프에 모서리가있는 경우이를 가리 키십시오. 그렇지 않다면 그 점이 내부인지 외부인지 분명해야합니다 (나무를 만들 때 잎에이 정보를 저장하십시오).

Answer 4

귀 클리핑은 어떻게 사용합니까? 각 삼각형에서 최대 축 정렬 사각형을 찾을 수 있습니다. 그런 다음 삼각형을 결합하고 사각형을 다시 계산할 수 있습니다.