计算一组重叠段覆盖的总面积的算法？

Question

我有一个可能重叠区间的端点列表,我想要一种有效的方法来计算k区间所覆盖的总面积k=1,2,... (不进行所有成对比较).或者,这不可能吗？

例如,假设x是起点列表,y是终点列表,并且x[i] < y[i],和

x = (1.5, 2, 3, 5)
y = (3, 4, 4, 6)

使得至少一个区间所覆盖的总面积为3.5,并且至少两个区域所覆盖的总面积为1.

谢谢,ph.

Answer 1

这是来自计算几何的经典线扫描问题.

在每个起点放置+1,在每个终点放置-1.然后想象从负无穷大到正无穷大的数字线上行走.

每当你遇到+1时,你的身高会增加1.每当你达到-1时,你的身高就会降低.当您在数字线上从p1移动到p2时,将p2 - p1(长度扫描)添加到给定高度所覆盖的数量.

然后你将得到一个由每个高度精确覆盖的长度直方图.如果要处理"至少两个间隔"的情况,可以累计总数.