사각형에서 오버랩을 계산하고, 히트 맵으로 결과를 표시합니다.

Question

특정 영역에서 겹치는 사각형 목록 ((x0, y0, x1, y1) 좌표)이 있습니다. 나는 각각의 겹치는 영역의 색이 히트 맵과 같아야한다. 더 많은 직사각형이 겹치면 더 어두워 지거나 (더 가볍거나 더 빨갛다 - 상관 없다) 그 색은 겹쳐 져야한다. 지역.

이것은 팬더에서 쉽게 수행 할 수 있지만 너무 많은 O (N_ 픽셀)을 필요로합니다. 대신에 직사각형의 수에 따라 비용이 달라 지므로 수천 번 속도를 올릴 수있는 방법이 있어야합니다. (팬더)에

예 :

import pandas as pd 
import seaborn as sns 
import matplotlib.pyplot as plt 

coords = [(1, 1, 4, 4), (2, 3, 6, 6), (2, 1, 3,2), (5, 3, 6, 7), (4, 3, 6, 7), (8, -5, 10, -2), (6, 0, 8, 3)] 

heatmap = pd.DataFrame() 
for box in coords: 
    area = pd.DataFrame(1, index=range(box[0], box[2]), columns=range(box[1], box[3])) 
    heatmap = heatmap.add(area, fill_value=0) 

heatmap = heatmap.fillna(0).astype(int) 
with sns.axes_style('white'): 
    plt.figure(figsize=(10,10)) 
    ax = sns.heatmap(heatmap, cmap=plt.cm.jet, xticklabels=100, yticklabels=100) 
    ax.set(title="Heatmap of overlapping rectangles") 
    plt.show() 

표시이 :

Answer 1

은 청소 알고리즘을 사용합니다.

상단 모서리의 세로 좌표를 증가시켜 사각형 정렬 (y 축 아래쪽). 활성 목록 (즉, 수평선을 만나는 직사각형 만 포함하는 목록)을 구현합니다 (줄이 떨어짐에 따라 업데이트를 처리하는 것은 쉬운 일입니다).

바이너리 검색 트리를 사용하여 교차 된 직사각형의 왼쪽과 오른쪽 끝점을 정렬 된 순서로 유지할 수 있습니다.

이제 목록을 검색하고 만난 엔드 포인트를 계산하여 겹치기 수를 결정할 수 있습니다. 채울 다각형을 재구성하기 위해 약간의 노력이 필요하지만, 전체 절차는 M 직사각형의 시간 O (M 로그 M)에서 수행되어야합니다.

---

부록 :

구현이 매우 간단 비 최적 어쨌든 유용한 방법이 있습니다.

모서리의 모든 x와 y를 따로 정렬하는 경우 모든 값을 해당 순위로 바꿔 자연체에 매핑 할 수 있습니다. 그런 다음 가장 작은 직사각형이 단일 픽셀 인 컴팩트 래스터 이미지로 압축됩니다.

중복 카운트를 얻으려면 모든 사각형을 칠하는 것으로 충분합니다. 그런 다음 N² 픽셀의 전체 해상도 이미지 대신 M² 픽셀을 고려해야합니다 (예 : 49 픽셀). 페인팅 작업은 압축 된 좌표의 사각형 영역 합계에 비례합니다.

트릭은 실제 좌표에서도 작동합니다.