- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我搜索了很多,但没有找到适用于这种情况的好的答案。我们有一些水平或垂直的矩形。它们可以随机放置在页面上。它们可以重叠或具有共同的边缘或彼此分开。我想找到一个 O(nlogn) 的算法,可以找到这些矩形的周长和面积。这些图片可能会使问题变得清晰。
我认为区间树可能有帮助,但我不确定如何。
最佳答案
这可以通过扫线算法来完成。
我们将从左到右扫过一条假想线。我们会注意到线和矩形集之间的交点表示一组间隔的方式,并且当我们遇到矩形的左边缘或右边缘时它会发生变化。
假设 x 坐标 x1 和 x2 之间的交点不变。然后,如果 x1 之后的交点长度为 L,则直线扫过的面积等于 (x2 - x1 ) * L,从 x1 扫描到 x2。
比如你可以看下图左边的蓝线是x1,右边的蓝线是x1一点点 :)):
很明显,我们的扫描线 的交点在这些点之间没有变化。然而,蓝色的十字路口与红色的十字路口截然不同。
我们需要一个包含这些操作的数据结构:
insert_interval(y1, y2);
get_total_length();
这些很容易用线段树实现,所以我现在不会详细介绍。
现在,算法会是这样的:
左和右是指矩形的边。
此想法仅用于计算面积,但是,您可以修改它以计算周长。基本上,您会想知道交叉点在某个 x 坐标处发生变化之前和之后的长度之间的差异。
算法的复杂度为 O(N log N)(虽然它取决于您可能获得的输入值的范围,但这很容易处理)。
您可以在 TopCoder 上找到有关扫描线 算法的广泛主题的更多信息。 .
您可以在 PEG judge wiki 上阅读有关使用线段树 的各种方法的信息.
这是我的(非常老的)算法实现,作为 SPOJ problem NKMARS 的解决方案: implementation .
关于algorithm - 计算相交矩形的周长和面积?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14505668/
我有一个标记的个体列表(Mark 列),这些个体在河流(LocStart 和 LocEnd)范围内的不同年份(Year 列)被捕获。在河上的位置以米为单位。 我想知道一个被标记的个体是否在不同年份之间
我目前正在开发一个事件管理系统,其中数据库存储时隙,如下所示: SlotId | DateTime | Duration -------+-------------------
给定同一个圆的两个圆段:A=[a1, a2] 和 B=[b1, b2],其中: a1、a2、b1、b2 的值介于 -inf 和 +inf 之间 a1 overlap A=[ -45°, 45
试图让两个数据集相交,但我做不到。例如,在我下面的代码中,相交 mySet 和 mySet2 应该产生“1”,因为它们在它们的集合中都有一个值“1”。 var mySet = new Set(); v
给定同一个圆的两个圆段:A=[a1, a2] 和 B=[b1, b2],其中: a1、a2、b1、b2 的值介于 -inf 和 +inf 之间 a1 overlap A=[ -45°, 45
我有两个要相交的集合,并对匹配元素执行求和运算。 例如集合是(在伪代码中): col1 = { {"A", 5}, {"B", 3}, {"C", 2} } col2 = { {"B", 1}, {"
我有一个使用 -setFrameRotation 旋转的 NSView。 (这是必要的,因为 View 响应鼠标事件,如果您仅使用旋转的 NSAffineTransform 绘制 View ,则不会获
我在网上找到了这段代码,显然它对其他人有效,但对我无效?我不知道哪里错了。我做了一个简单的例子,并将我的 Range1 和 Range 2 设为 excel 中的某些单元格, 另外,我想知道是否有办法
确定直线是否与矩形相交的最有效方法是什么? 我正在寻找类似的东西: CGPoint startLine = CGPointMake(5.0f,5.0f); CGPoint endLine = CGPo
QPolygonF有与其他 QPolygonF 并集、相交和相减的方法,但我需要与 QLineF 执行相交测试。 API 中似乎缺少此功能。 我想我可以做这样的事情: if (polygon .con
所以,我尝试使用矩形在游戏中对墙壁进行碰撞,我决定尝试使用 ArrayList 来存储每面墙的矩形,然后我将整个 field 设为一面墙,并且所有我想做的是删除三堵墙,所以我正在执行 shapeLis
鉴于这两个表/集合具有不同的项目组, 我如何找到 set1 中的哪些组跨越 set2 中的多个组? 如何找到 set1 中的组不能被 set2 中的单个组覆盖? 例如对于下表,A (1,2,5) 是唯
我在 Hive 中有两个字符串数组,例如 {'value1','value2','value3'} {'value1', 'value2'} 我想合并没有重复的数组,结果: {'value1','va
谁能给我 tsql 来查找包含起始日期和截止日期的日期。 select * from empc where DateFrom >= p_todate AND DateTo = p_fromdate 关
我正在尝试从分桶列中获取子集,然后获取交集。 这将从原始表中选择其他列。 我也对系列过滤持开放态度。 下面的代码报告 col1 不存在 - 不确定这是正确的方法。 WITH ranges AS (
SELECT friend_id FROM friendships WHERE user_id = 1; Returns: +-----------+ | friend_id | +---------
似乎无法在任何地方找到这个问题的答案。 我的游戏在用户触摸屏幕时开始,手指必须停留在一条路径内,如果它触摸/与边缘相交,那么我希望它运行 [self gameover] 方法。 边缘将是一个 UIIm
我有两个 RDD,一个非常大,另一个小得多。我想用小 RDD 的键在大 RDD 中找到所有唯一的元组。 大 RDD 太大,我必须避免完全洗牌 小型 RDD 也足够大,我无法广播它。我也许可以广播它的
所以我有两个函数的代码。第一个打印一个空的 20x20 板,第二个打印中间的一个字。现在我正在尝试编写一个函数来检查输入的单词是否会与同一字母的另一个单词(如填字游戏)相交。这是前两个函数的代码(此处
我正在一个网站上进行培训,该网站要求我制作一个程序,该程序将询问两个矩形的坐标并检查矩形是否相交。然后,当我发送程序时,网站会对其进行几次测试。它要求 A 矩形的 x 最小值、x 最大值、y 最小值和
我是一名优秀的程序员,十分优秀!