矩形の重なりを計算し、結果をヒートマップとしてプロットする

Question

特定の領域で重複する四角形のリスト（（x0、y0、x1、y1）としての座標）があります。私はそれらのオーバーラップで、余分なひねりを加えて描画したい：それぞれのオーバーラップ領域の色はヒートマップのようにする必要があります：より矩形がオーバーラップしている場合は、より暗く（またはより軽く、エリア。

これはPandasで簡単に行うことができますが、あまりにも多くのO（N_pixels）がかかります。代わりに、長方形の数に応じてコストがかかり、その結果、何千ものスピードアップをする方法があるはずです。

例（パンダで）：

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 Log M）ですべての手順を実行する必要があります。

---

補遺：

実装するのは非常に簡単である非最適とにかく便利なアプローチがあります。

コーナーのすべてのxとyを別々に並べ替えると、それらをナチュラルにマップして、すべての値をそのランクで置き換えることができます。次に、最小の四角形が1つのピクセルであるコンパクトなラスターイメージに、プレイグラウンドが圧縮されます。

オーバーラップ数を取得するには、すべての長方形をペイントすれば十分です。次に、N²ピクセルのフル解像度イメージの代わりに、それらのM²を考慮する必要があります（アライメントの場合は少なく、例の場合は49ピクセル）。塗装作業は、圧縮座標の矩形領域の合計に比例します。

このトリックは実際の座標でも機能します。