gpt4 book ai didi

algorithm - 计算相交矩形的周长和面积?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:45:54 27 4
gpt4 key购买 nike

我搜索了很多,但没有找到适用于这种情况的好的答案。我们有一些水平或垂直的矩形。它们可以随机放置在页面上。它们可以重叠或具有共同的边缘或彼此分开。我想找到一个 O(nlogn) 的算法,可以找到这些矩形的周长和面积。这些图片可能会使问题变得清晰。

enter image description here

我认为区间树可能有帮助,但我不确定如何。

最佳答案

这可以通过扫线算法来完成。

我们将从左到右扫过一条假想线。我们会注意到线和矩形集之间的交点表示一组间隔的方式,并且当我们遇到矩形的左边缘或右边缘时它会发生变化。

假设 x 坐标 x1x2 之间的交点不变。然后,如果 x1 之后的交点长度为 L,则直线扫过的面积等于 (x2 - x1 ) * L,从 x1 扫描到 x2

比如你可以看下图左边的蓝线是x1,右边的蓝线是x1一点点 :)): enter image description here

很明显,我们的扫描线 的交点在这些点之间没有变化。然而,蓝色的十字路口与红色的十字路口截然不同。

我们需要一个包含这些操作的数据结构:

insert_interval(y1, y2); 
get_total_length();

这些很容易用线段树实现,所以我现在不会详细介绍。

现在,算法会是这样的:

  1. 获取所有垂直线段并按其 x 坐标对它们进行排序。
  2. 对于每个相关的 x 坐标(只有显示为矩形边缘的坐标才重要):
    • 设 x1 为之前相关的 x 坐标。
    • 设 x2 为当前相关的 x 坐标。
    • 令 L 为我们的数据结构给出的长度。
    • 将 (x2 - x1) * L 添加到总面积之和。
    • 从数据结构中删除所有具有 x = x2 段的边。
    • 将所有具有 x = x2 段的 边添加到数据结构中。

是指矩形的边。

此想法仅用于计算面积,但是,您可以修改它以计算周长。基本上,您会想知道交叉点在某个 x 坐标处发生变化之前和之后的长度之间的差异。

算法的复杂度为 O(N log N)(虽然它取决于您可能获得的输入值的范围,但这很容易处理)。

您可以在 TopCoder 上找到有关扫描线 算法的广泛主题的更多信息。 .

您可以在 PEG judge wiki 上阅读有关使用线段树 的各种方法的信息.

这是我的(非常老的)算法实现,作为 SPOJ problem NKMARS 的解决方案: implementation .

关于algorithm - 计算相交矩形的周长和面积?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14505668/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com