计算矩形重叠,将结果绘制为热力图

2024-03-28 13:57:30 发布

您现在位置:Python中文网/ 问答频道 /正文

我有一个矩形列表(坐标为(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()

显示以下内容:

Rectangles Overlap


Tags: importbox区域dataframe列表asrangeplt
1条回答
网友
1楼 · 发布于 2024-03-28 13:57:30

使用扫描算法。在

通过增加矩形上边缘的纵坐标(y轴向下)对矩形进行排序。实现一个活动列表,即只包含与水平线相交的矩形的列表(当行向下时处理更新很容易)。在

可以使用二叉搜索树将相交矩形的左端点和右端点按排序顺序排列。在

现在,通过扫描列表并计算达到的端点,可以确定重叠的数量。重建要填充的多边形需要一些额外的工作,但整个过程必须在M个矩形的时间O(M logm)内完成。在

enter image description here


附录:

有一个非最优但无论如何有用的方法是非常容易实现的。在

如果将角点的所有x和y分别排序,则可以将它们映射到自然值,用其秩替换每个值。然后你的游乐场压缩成一个紧凑的光栅图像,其中最小的矩形是一个像素。在

要获得重叠计数,只需绘制每个矩形就足够了。然后,您只需要考虑M²像素的图像,而不是N²像素的全分辨率图像(如果是对齐,则考虑M²;在您的示例中,是49像素)。在压缩坐标系中,绘制工作与矩形面积之和成正比。在

这个技巧也适用于真实坐标。在

相关问题 更多 >