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

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(使用前将#替换为@)

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

  • 交换两个向量之间的值,使两个向量的 max_element 之和最小

    这是 Codechef 的问题 但请耐心等待 https www codechef com ZCOPRAC problems ZCO16001 https www codechef com ZCOPRAC problems ZCO16001
  • c中使用递归的strlen函数

    我对递归主题很陌生 我一直在尝试使用递归编写 strlen 函数 这就是我尝试过的 int strlen char str int i if str i 0 return i 1 return strlen str i 我尝试了一些非常相似
  • 方案中的尾递归幂函数

    我在方案中编写尾递归幂函数时遇到问题 我想使用辅助函数来编写该函数 我知道我需要一个参数来保存累计值 但在那之后我就陷入了困境 我的代码如下 define pow tr a b define pow tr h result if b 0 r
  • 如何动态查找连接组件

    使用不相交集数据结构可以很容易地得到图的连通分量 而且 它只是支持增量连接组件 http www boost org doc libs 1 46 1 libs graph doc incremental components html 然而
  • 如何在 PHP 中递归删除目录及其全部内容(文件+子目录)? [复制]

    这个问题在这里已经有答案了 如何在 PHP 中删除目录及其全部内容 文件和子目录 手册页中的用户贡献部分rmdir http www php net rmdir包含一个不错的实现 function rrmdir dir if is dir
  • 反转二进制网络

    如何反转二元方程 以便找到哪些输入将产生给定的输出 Example Inputs i0 through i8 Outputs o0 through o8 Operators XOR AND 二元方程 1 i0 1 i1 0 i2 1 i3
  • 使用reduce方法的斐波那契数列

    于是 我看到有人用reduce方法来计算斐波那契数列 这是他的想法 1 0 1 1 2 1 3 2 5 3 对应于 1 1 2 3 5 8 13 21 代码如下所示 def fib reduce n initial 1 0 dummy ra
  • Python 给定 k 个分区的整数分区

    我正在尝试寻找或开发Python 的整数分区代码 仅供参考 整数分区将给定整数 n 表示为小于 n 的整数之和 例如 整数5可以表示为4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 我为此找到了许多解决方案 ht
  • 32 位数字中 1 的数量

    我正在寻找一种在 32 位数字中包含 1 数量的方法 之间不使用循环 任何人都可以帮助我并向我提供代码或算法吗 这样做 提前致谢 See Integer bitCount int http java sun com javase 6 doc
  • Scala REPL 中的递归重载语义 - JVM 语言

    使用 Scala 的命令行 REPL def foo x Int Unit def foo x String Unit println foo 2 gives error type mismatch found Int 2 required
  • 线性代数如何在算法中使用?

    我的几个同行都提到 学习算法时 线性代数 非常重要 我研究了各种算法并学习了一些线性代数课程 但我没有看到其中的联系 那么线性代数如何应用在算法中呢 例如 图的连接矩阵可以带来哪些有趣的事情 三个具体例子 线性代数是现代 3D 图形的基础
  • 确定解决迷宫问题的最小线段数

    我有一个问题 我需要定义一个具有最少数量的顶点的多边形 该多边形与不透明的图像中的每个像素相交或包含每个像素 令 N 为图像中的像素数 我唯一的假设是图像的边界 孔 内不能包含透明像素 并且至少有两个像素是不透明的 举个例子 假设我有以下图
  • 如何将无向图转换为 DAG?

    The 维基页面 http en wikipedia org wiki Directed acyclic graph Relation to other kinds of graphs says 任何无向图都可以通过为其顶点选择总顺序并将每
  • 图中的后边

    I m having a hard time understanding Tarjan s algorithm for articulation points I m currently following this tutorial he
  • 寻找距离原点最近的 100 颗恒星的算法

    首先让我提出正确的问题 问 有一个文件包含超过一百万个点 x y 每个点代表一颗星星 a b 处有一颗行星地球 现在 任务是构建一种算法 返回距离地球最近的 100 颗恒星 您的算法的时间和空间复杂度是多少 这个问题在各种采访中被问过很多次
  • 固定大小集以包含给定集的最大数量

    我有大约 1000 组尺寸 1 4 1 3 3 5 6 4 5 6 7 5 25 42 67 100 是否有可能找到包含最大数量的给定集合的大小为 20 的集合 检查每一个100 80 20 集 效率低下 我不太确定这是 NP 完全的 考虑
  • 解释一下从 N 个给定集合中的每一个中给出第 K 个最大数字的示例?

    今天我尝试解决一个Facebook 编程挑战赛 https facebook interviewstreet com recruit challenges 我遇到的挑战是 酒吧问题 可以找到here https github com alo
  • 如何求小于给定数的最大2次方

    我需要找到小于给定数字的最大 2 次幂 我陷入困境 找不到任何解决方案 Code public class MathPow public int largestPowerOf2 int n int res 2 while res lt n
  • 有人可以解释以下异或属性

    我的一个论坛提到给定的数组n数字 arr 0 n 1 以下条件成立 is the xor运算符 f l r f 0 r f 0 l 1 where f l r arr l arr l 1 arr r 我检查了上面的数组数量和不同的值l an
  • 无需构建树即可预测霍夫曼压缩比

    我有一个二进制文件 我知道其中每个符号出现的次数 如果我要使用霍夫曼算法压缩它 我需要预测压缩文件的长度 我只对假设的输出长度感兴趣 而不对单个符号的代码感兴趣 因此构建霍夫曼树似乎是多余的 作为一个例子 我需要得到类似的东西 包含 4 个

随机推荐

  • 在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