이러한 유형의 문제를 해결하는 데는 여러 가지 방법이 있지만 각각 다른 장단점이 있습니다. - 두 사각형이 교차하는 경우, 중복이
사각형 쌍 사거리 + 지역 합계 사각형의 모든 쌍에
봐 : 여기에 그들 중 일부입니다. 사각형 영역을 추가하고 합계가 캔버스 영역과 일치하는지 확인하십시오. 영역이 일치하지 않으면 간격이 있습니다.
회화 이것은 당신이 언급 한 방법은 다음과 같습니다 캔버스의 크기를 가진 2 차원 배열을 만들 수 있습니다. 그런 다음 직사각형을 반복하고 어레이에 "페인트"합니다.
이 접근 방식의 최적화 중 하나는 좌표 압축입니다. 사각형 ([10,20], (15,25), [(7,3), (15,25)])이 있다고 가정 해 봅시다. 별개의 x 좌표 (7, 10, 15)를보고 (0, 1, 2) 및 고유 한 y 좌표 (3, 20, 25)로 다시 매핑하고 다시 매핑 할 수 있습니다 (0, 1, 2). 그런 다음 직사각형 [(1,1), (2, 2)] 및 [(0,0), (2,2)]로 남겨 지므로 그림에 대해 3x3 배열 만 필요합니다. 26x26 정렬.
스윕 라인 알고리즘
는 '재미'지점에서 중지 및 영역을 점유하는 추적을 유지, 왼쪽에서 오른쪽으로 선을 스윕.
2D 범위 나무
효율적 직사각형 범위에서 쿼리를 수행 할 수있는 데이터 구조.
어느 것을 골라야합니까?
당신이 가지고있는 직사각형의 수, 지역에서의 분포도, 알고리즘의 속도, 얼마나 복잡합니까? 등 내가 언급 한 처음 두 알고리즘은 다음과 같습니다. 후자의 두 개보다 훨씬 간단하기 때문에 거기에서 시작하는 것이 좋습니다.
추가 정보
당신이 이러한 알고리즘에 대한 자세한 내용을 보려면 원하는 경우 온라인 "사각형 조합"를 검색해보십시오. 가장 효율적인 솔루션은 스윕 라인 알고리즘입니다.
- What is an Efficient algorithm to find Area of Overlapping Rectangles
- http://compgeom.cs.uiuc.edu/~jeffe/open/klee.html
- J. L. 벤틀리, 알고리즘 클레의 사각형 문제 : 다음 은 스윕 라인 알고리즘에 대한 참조의 몇 가지 있습니다. 게시되지 않은 메모, 컴퓨터 과학과, 카네기 멜론 대학, 1977 참조 3. 일반적으로 사각형 조합의 행 청소 알고리즘의 원본 소스로 제공,하지만 난 사실을 찾지 못했음을 인정해야한다
종이가 온라인이기 때문에 아마 "미공개"입니다 ...
이 숙제입니까? –
가능한 한 자세히 설명하여 문제를 다시 설명하는 것이 좋습니다. 문제를 진술 할 수 없다면 해결책을 찾기가 매우 어렵습니다. –
은 x/y 축에 평행 한 직사각형의 가장자리입니까, 아니면 어떤 방향으로있을 수 있습니까? – PeskyGnat