哪种洪水填充算法性能更好?

2024-03-13

我正在尝试实现一种与洪水填充类似的算法。问题是我不确定应该以什么方式实现它,例如递归-非递归。
我知道每一种都有其缺陷,但其中一种必须比另一种更快。当非递归每次分配 4 个新点时,递归会在堆栈上打开新函数。
非迭代的示例:

Stack<Point> stack = new Stack<Point>();
    stack.Push(q);
    while (stack.Count > 0)
    {
        Point p = stack.Pop();
        int x = p.X;
        int y = p.Y;
        if (y < 0 || y > h - 1 || x < 0 || x > w - 1)
                continue;
        byte val = vals[y, x];
        if (val == SEED_COLOR)
        {
                vals[y, x] = COLOR;
                stack.Push(new Point(x + 1, y));
                stack.Push(new Point(x - 1, y));
                stack.Push(new Point(x, y + 1));
                stack.Push(new Point(x, y - 1));
        }
    }

编辑:我将在 600X600 像素地图上应用以下算法。尽管洪水填充不会应用于整个地图,但每次迭代应覆盖地图的 30% - 80% 左右。我的观点是发现高度图中的边缘并标记这些边缘以供进一步使用。


制作一个掩码 - 一个并行的 2 维字节数组。未检查区域字节为 0,对于淹没区域的新边界,其值为 1。对于淹没区域的内部,值为 2。并保留当前边界点的列表。

在外循环的任何一端,您都有带有标记的当前边界、内部和外部区域以及边界点数组的蒙版。因此,您将仅检查边界上的新点。在检查边界点的第一个数组列表时,您正在创建第二个边界数组列表和第二个掩码。在下一步中,您将重新创建第一个边框数组和蒙版。沿着这条路,我们可以使用简单的while循环而不是递归,因为你在任何步骤检查的数据结构都非常简单。

顺便说一句,您忘记检查新点的坐标是在绘制的边框上还是在整个矩形的边框上。

至于循环遍历所有相邻点,看我的算法here https://codereview.stackexchange.com/a/8947/11012

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

哪种洪水填充算法性能更好? 的相关文章

  • O(n^2) 与 O (n(logn)^2)

    时间复杂度是O n 2 or O n logn 2 better 我知道当我们简化它时 它就变成了 O n vs O logn 2 and logn lt n 但是关于logn 2 n is only less than log n 2 f
  • 在哪里可以找到有关双三次插值和 Lanczos 重采样的好读物?

    我想用 C 实现上述两种图像重采样算法 双三次和 Lanczos 我知道现有的实现有几十种 但我仍然想制作自己的实现 我之所以这么做 部分原因是我想了解它们是如何工作的 部分原因是我想为它们提供一些主流实现中没有的功能 例如可配置的多 CP
  • 包装一个采用 std::function 的函数,以便传递采用更多参数的函数

    Problem 我有一个函数double subs std function
  • 如何在 R 中创建没有情节的图例?

    这是一个艺术项目 我创建了一个包含 5 种不同颜色的许多点的散点图 我想创建一个与绘图完全分开的图例 因为它不在绘图上 也不在绘图旁边 而是在它自己的窗口中 因此我可以将图例保存为它自己的 pdf 文件 这样我就可以将我的情节和图例分开打印
  • 如何从横滚、俯仰和偏航获取相机向上矢量?

    我需要从滚动角 俯仰角和偏航角 以度为单位 获取相机的向上矢量 以获得正确的外观 我已经尝试了几个小时不同的事情 但没有运气 这里的任何帮助将不胜感激 横滚 俯仰和偏航定义 3 轴旋转 从这些角度 您可以构建一个 3x3 变换矩阵来表达该旋
  • 随机排列

    我无法找到一种随机洗牌元素的好方法std vector经过一些操作后 恢复原来的顺序 我知道这应该是一个相当简单的算法 但我想我太累了 由于我被迫使用自定义随机数生成器类 我想我不能使用std random shuffle 无论如何这没有帮
  • 在大文件中查找重复项

    我有一个非常大的文件 大约有 1500 万个条目 文件中的每一行都包含一个字符串 称为键 我需要使用 java 查找文件中的重复条目 我尝试使用哈希图并检测重复的条目 显然 这种方法向我抛出了 java lang OutOfMemoryEr
  • 埃拉托斯特尼筛法是生成 1 到 N 素数的最佳算法吗?

    我在一次采访中被问到这个问题 我使用埃拉托色尼筛子概念和数组实现了一种算法 有没有更好的方法来解决这个问题 对于不知道筛子的人 请点击以下链接 http en wikipedia org wiki Sieve of Eratosthenes
  • 计算总和等于 k ​​的子集数量

    给定一个数组 我们需要找出总和恰好等于给定整数 k 的子集的数量 请针对这个问题提出一个最佳算法 这里不需要实际的子集 只需计数即可 该数组由整数组成 可以是负数也可以是非负数 例子 数组 gt 1 4 1 10 5 绝对值总和 gt 9
  • n的渐近增长选择下限(n/2)

    如何找到 n select Floor n 2 的渐近增长 我试过 使用扩展并得到它等于 n n 1 floor n 2 1 n floor n 2 知道我该如何从那里去吗 感谢任何帮助 更喜欢提示而不是答案 我同意上面的答案 但想提供更多
  • typescript 类型最大递归限制为 9

    我终于成功创建了一个通用类型 它为我提供了 json 键列表 值的所有可能组合 我什至准备了一种限制递归的方法 type EditAction
  • CSR 矩阵 - 矩阵乘法

    我有两个方阵A and B 我必须转换B to CSR Format并确定产品C A B csr C 我在网上找到了很多关于CSR 矩阵 向量乘法 http www mathcs emory edu cheung Courses 561 S
  • 大小为 n 的数组,其中一个元素 n/2 次

    给定一个由 n 个整数组成的数组 其中一个元素出现超过 n 2 次 我们需要在线性时间和恒定的额外空间中找到该元素 YAAQ 又一个数组问题 我有一种偷偷的怀疑 这类似于 在 C 中 We don t need an array publi
  • 如何以最小化每个分区总和的最大值的方式对整数数组进行分区?

    输入是正整数或空整数的数组 A 和另一个整数 K 我们应该将 A 划分为 K 个连续元素块 我所说的 划分 是指 A 的每个元素都属于某个块 并且 2 个不同的块不包含任何共同元素 我们将块的总和定义为该块的元素的总和 目标是在 K 个块中
  • 为每个英文单词生成唯一序列号的算法

    对于应用程序 我需要为每个英语单词生成唯一的序列号 最好的方法是什么 一个限制是序列号生成算法应该在普通台式计算机中非常有效 Thanks 你有所有可能的单词的列表吗 如果是 则从第一个字的 0 开始 每个字将序列号加 1 如果不是 那么保
  • 单词预测算法

    我确信有一篇关于此问题的帖子 但我找不到提出这个确切问题的帖子 考虑以下 我们有字典可供使用 我们收到了许多单词段落 我希望能够根据此输入预测句子中的下一个单词 假设我们有几个句子 例如 你好 我的名字是汤姆 他的名字是杰瑞 他去了没有水的
  • 沿着长数据序列在固定大小的移动窗口中查找中值

    给定一个数据序列 可能有重复项 一个固定大小的移动 窗口 从数据开始处每次迭代时移动窗口 序列 使得 1 从窗口中删除最旧的数据元素并添加新数据 元素被推入窗口 2 求每次移动时窗口内数据的中位数 以下帖子没有帮助 有效地找到随机序列的中值
  • 如何使用 Java2D 创建硬件加速图像?

    我正在尝试创建一个快速图像生成器 它可以执行大量 2d 转换和形状渲染 因此我尝试使用 BufferedImage 然后获取 Graphics2D 对象来执行所有绘图 我现在主要关心的是 make 速度非常快 所以我创建一个像这样的 Buf
  • 如何从 Unix 命令行递归解压目录及其子目录中的档案?

    The unzip命令没有递归解压缩档案的选项 如果我有以下目录结构和档案 Mother Loving zip Scurvy Sea Dogs zip Scurvy Cures Limes zip 我想将所有档案解压缩到与每个档案同名的目录
  • 重新安装后使用 pandas dataframes 时出现问题

    我已经重新安装了 Python 和 Anaconda 现在面临以下问题 在我将 pkl 文件加载到数据帧并尝试 查看 该文件后 如下所示 df pd read pickle example pkl df 我收到错误 AttributeErr

随机推荐

  • 在Android项目中使用开源库

    我是 Android 编程的初学者 我正在使用 android studio 现在我想知道从 gitHub 安装开源库的最佳方法是什么 我的问题是从组织原则的角度来看 我应该为每个库创建一个新包并将所有库源代码按原样放入该包中吗 该包应该位
  • 导入类型时 Sveltekit Typescript 解析错误

    我在一个全新的 Sveltekit 项目中有这个非常简单的组件
  • Spring data mongodb 使用 MongoTemplate 从文档中删除属性

    我有一个如下所示的文档 id ObjectId 5864ddd8e38112fd70b89893 class com apic models UserReg name xxx email email protected cdn cgi l
  • REQUEST_URI 与显式路径和文件名不匹配

    真的很困惑 因为形式和语法看起来都很好 REQUEST URI 的 RewriteCond 与显式路径和文件名不匹配 隔离时 REQUEST FILENAME 的 RewriteCond 匹配得很好 我已经使用 phpinfo 验证了 RE
  • 尽管同时实现了 hashCode() 和 equals(),HashSet 仍添加了重复条目

    我有以下课程 class Point double x y constructor and other functions here public boolean equals Point p if p null return false
  • Node.js 存档器需要通过 glob 排除文件类型的语法

    使用 archiver js 适用于 Node js 我需要从递归 多子目录 存档中排除图像 这是我的代码 const zip archiver zip zlib level 9 const output await fs createWr
  • Python 脚本 - 连接到 SSH 并运行命令

    我已经知道有 Python 的 ssh 模块 但这不是我正在寻找的 我想要的是一个 python 脚本来执行以下操作 gt 连接到 用户输入 SSH 主机 gt 使用凭据 由用户提供 连接 gt 在 SSH 主机上运行命令 telnet 到
  • 使用 ST25 android SDK 进行 NFC 标签密码保护

    我正在与ST25 标签 更具体地说是 type5 标签 ST25DV64K 适用于 Android 的 ST25 SDK 有一些有趣的示例和教程 我仍然在努力使用文档末尾提供的代码示例here https www st com resour
  • MySQL - 如何使用 LIKE 搜索精确的单词匹配?

    我使用此查询来选择数据 mysql query SELECT FROM products WHERE product name LIKE search 唯一的问题是 它有时会选择比我想要的更多的东西 例如 我想选择产品 BLA 但我的查询也
  • Internet Explorer 11 与 Asp.Net 4.0 的会话问题

    我遇到一个奇怪的问题 我在 asp net 4 0 中开发了一个网站 它在所有浏览器上都能正常工作 因为我也在处理会话 因此用户必须登录才能使用该网站 在 Internet Explorer 11 上 当您访问网站 url 时 它会在 ur
  • 快速for循环与睡眠

    我有一个 Swift 4 ios 应用程序 按下按钮时会显示随机消息和照片 这工作正常 但我想创建一个无限循环来在按下按钮时显示随机消息 照片 我尝试了多种方法来实现这一目标 但没有一个有效 在主线程完成之前 标签和图像视图似乎不会更新 下
  • 让 ScrollView 与自动布局和情节提要一起使用

    我正在尝试为我想要构建的应用程序制作一个非常简单的布局 但我似乎正在努力使用 ScrollView 并通过 Storyboard 让它工作 基本上我正在尝试构建以下内容 我已经使用几个教程完成了约束 但它要么不滚动 要么看起来错误 有什么建
  • 与 React 内联自定义 `::-webkit-scrollbar`

    我怎样才能申请 webkit scrollbar在 React 中使用内联样式将伪元素添加到组件 你不能写pseudo内联选择器 需要在css中添加 参考这个link https developer mozilla org en US do
  • 关闭时 SqlDependency 订阅不会从 dm_qn_subscriptions 中删除

    My SQL依赖关系工作正常 当应用程序退出时 代理队列和服务会正确删除 我确实执行SqlDependency Stop 按照终止进程之前的建议 但我注意到由SQL依赖关系应用程序关闭后 仍保留在表 sys dm qn subscripti
  • watir-webdriver 黑色屏幕截图

    我正在使用 watir webdriver 浏览我的网站并在不同的浏览器中抓取屏幕截图 有时 在 IE 中截取的屏幕截图尺寸正确 但颜色全黑 同时运行的 Firefox 测试看起来不错 browser driver save screens
  • Javascript window.open 不工作

    好的 我正在尝试登录推特 这段代码中没有打开窗口 收到警报的响应不为空 并且是指向登录屏幕的链接 有任何想法吗 var url twitter login php var con createPHPRequest con open POST
  • 参数和列表哪个更好

    我当前的代码如下 它是作为代理暴露给客户端的WCF服务方法 public UnifiedDTO GetAllCardTitle string trainSymbolOrCarLocation DateTime startDate DateT
  • 为什么应用程序安装了两次?

    当我运行 Android App Studio 时 单元格是应用程序 安装 两次 有两个应用程序 一个称为 SplashScreenActivity 另一个称为 Doctor Quiz 我的应用程序 两者是平等的 如果我卸载一个 另一个也会
  • 在 django 1.7 中包含静态 js 文件

    这是一部分settings py STATIC URL static STATICFILES DIRS os path join BASE DIR static HTML 模板 load staticfiles vendor jquery
  • 哪种洪水填充算法性能更好?

    我正在尝试实现一种与洪水填充类似的算法 问题是我不确定应该以什么方式实现它 例如递归 非递归 我知道每一种都有其缺陷 但其中一种必须比另一种更快 当非递归每次分配 4 个新点时 递归会在堆栈上打开新函数 非迭代的示例 Stack