计算相交矩形的周长和面积？
Cod*_*ork 5 algorithm tree intervals
我搜索了很多,但我没有找到适合这种情况的好答案.我们有一些水平或垂直的矩形.它们可以随机放在页面上.它们可以重叠或具有共同边缘或彼此分开.我想找到一个带有O(nlogn)的算法,它可以找到这些矩形的周长和面积.这些图片可能会使问题变得清晰.
我认为间隔树可能有所帮助,但我不确定如何.
它可以通过扫描线算法完成.
我们将从左到右扫描一条假想线.我们会注意到直线和矩形集之间的交点表示一组间隔的方式,并且当我们遇到矩形的左边或右边时它会发生变化.
假设交点在x坐标x1和x2之间不变.然后,如果交点的长度后X1是大号,该线将已经横扫等于(面积×2 - X 1)*大号,通过扫描从X1至X2.
例如,您可以将x1视为左侧蓝线,将x1视为下图中的右侧蓝线(我从您那里偷走并修改了一下:)):
应该清楚的是,我们的扫描线的交点在这些点之间不会改变.然而,蓝色交叉点与红色交叉点完全不同.
我们需要一个包含这些操作的数据结构:
insert_interval(y1, y2);
get_total_length();
这些很容易用段树实现,所以我现在不再详述了.
现在,算法将如下所示:
- 取所有垂直线段并按x坐标对它们进行排序.
- 对于每个相关的x坐标(只有出现在矩形边缘的坐标才重要):
- 设x1为先前的相关x坐标.
- 设x2为当前相关的x坐标.
- 设L是我们的数据结构给出的长度.
- 将(x2 - x1)*L添加到总面积总和中.
- 从数据结构中删除x = x2段的所有右边缘.
- 将x = x2段的所有左边缘添加到数据结构中.
由左及右我的意思是一个矩形的边.
这个想法仅用于计算区域,但是,您可以修改它以计算周长.基本上你会想知道交叉点在某个x坐标处变化之前和之后的长度之间的差异.
算法的复杂性为O(N log N)(尽管它取决于您可能获得的值的范围,这很容易处理).
您可以在TopCoder上找到有关扫描线算法的更多主题的更多信息.
您可以阅读有关在PEG判断维基上使用分段树的各种方法.
这是我(非常古老)算法的实现,作为SPOJ问题NKMARS的解决方案:实现.