작은 사각형으로 구성된 영역을 더 큰 사각형으로 나누는 방법은 무엇입니까?

Question

입력으로 0 또는 1 인 값의 2D 그리드를 사용한 알고리즘을 어디로 가려고합니까?

보다 실용적인 설명에서 : 나는 많은 사각형으로 표시되는 그리드를 그리고 있으며, 사이클링에 소요되는 시간을 줄이기 위해 인접한 사각형을 가능한 한 사각형으로 결합하는 방법을 찾고 싶습니다. 각각 정사각형과 그림을 그립니다.

최대 효율이 필요하지 않으며 속도가 더 중요합니다.

부록 : 분명히 내가 찾고있는 것은 Tesselation이라는 기술인 것 같습니다. 이제이 특정 사례에 대한 좋은 설명 만 찾기 만하면됩니다.

부록 2 : "1"사각형의 분포는 완전히 무작위이므로 "1"사각형의 경계는 불규칙하고 경우에도 연결되지 않습니다. 이러한 불규칙한 모양을 식별하고 일반 사각형으로 나누어야합니다.

정답 : 속도와 효율 사이의 최상의 균형을 얻으려면 그리드 데이터를 사용하여 빈/부분적으로 채워진 상태 값을 갖는 각 노드와 함께 쿼드 트리를 채우는 것이 최적입니다.

Answer 1

나는 OpenGL과 함께 3D 박스의 빠른 복셀 시각화를 위해 비슷한 일을했습니다.

나는 왼쪽 상단에서 시작하여 빈/채워진 깃발을 보관했습니다. 그런 다음 다른 깃발로 상자에 닿을 때까지 사각형을 오른쪽으로 확장하려고했습니다. 나는 아래 방향으로 똑같이했다.

채워진 경우 사각형을 그립니다.

상자가 다시있는 경우, 마지막 사각형에 의해 유도 된 세 가지 Remaing 직사각형 모두에 대한 절차를 재귀 적으로 반복하여 오른쪽, 하단 및 하단입니다.

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

Answer 2

살펴보십시오 Dobb 박사의 포털에서 나온이 기사 상황에서 최대 사각형을 찾는 데. 매우 효율적인 알고리즘에 대한 매우 상세한 논의이며, 반복적으로 반복하면 문제를 해결할 수 있다고 생각합니다.

Answer 3

최소 제곱 수를 찾고 있지 않기 때문에 여전히 알고리즘을 간단하게 유지하는 타협을 사용하는 것이 좋습니다.

최상의 솔루션은 데이터에 따라 다르지만 간단한 대안 중 하나는 한 행을 따라 상자를 수집하는 것입니다. 즉:

0 0 1 1 1 0 0 0 1 1 1 1 0

결과 :

skip 2
draw 3
skip 3
draw 4
skip 1

이렇게하면 캐싱이 필요없이 상자를 그리는 통화 횟수가 줄어 듭니다 (즉, 상자를 즉석에 만들 수 있습니다).

더 큰 상자를 만들려면 처음 1을 찾을 수있는 역 추적 알고리즘을 제안하고 모든 방향으로 상자를 확장하려고합니다. 상자 목록을 작성하고 사용한대로 1 : S를 지우십시오.

Answer 4

그래서 당신은 '온'사각형의 직사각형 경계를 찾고 있습니까?
내부 또는 외부 바운드를 원하십니까?
즉. 경계에는 'on'사각형 만 가지고 있어야합니까, 아니면 사각형이 그룹에 모든 'on'사각형을 포함하기를 원합니까?

Answer 5

나는 비슷한 문제를 해결해야했고, 알고리즘은 들쭉날쭉 한 배열을 지원하고, 심하게 테스트하고 댓글을 달았지만 Joel-in-Gö의 제안보다 느립니다.https://stackoverflow.com/a/13802336