程序员经验分享-hwhale

快速轴对齐单元格遍历算法

2023-12-14
  • 给定一个轴对齐的正方形，分为四个大小相等的单元格 A、B、C 和 D。
  • 给定一条从点 s1 到点 s2 的线段。

查找该段（如果有）遍历的单元格（按遍历顺序排序）的最快方法是什么？

sketch of cells

在上面的例子中，正确的结果是：

  • 第 1 段：[D]
  • 分段 2：[A，B]
  • 第 3 段：[C、D、B]
  • 第 4 段：[]
  • 片段 5：[C]

你可以试试“一种用于光线追踪的快速体素遍历算法”作者：Amanatides 和 Woo。

它旨在处理大型网格，但该原理也对您的应用程序有用。

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

Algorithm

languageagnostic

geometry

aabb

快速轴对齐单元格遍历算法 的相关文章

  • 有人可以解释以下异或属性

    我的一个论坛提到给定的数组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

  • 时间复杂度和运行时间有什么区别？

    时间复杂度和运行时间有什么区别 它们是一样的吗 运行时间是指程序运行所需的时间 时间复杂度是对输入大小趋于无穷大时运行时间渐进行为的描述 您可以说运行时间 是 O n 2 或其他什么 因为这是描述复杂性类和大 O 表示法的惯用方式 事实上

  • 类是否应该有静态和非静态成员

    我试图找出一个类何时适合同时具有静态和非静态函数 又名 obj new ClassA obj gt doOOPStuff something ClassA doStaticStuff Note This example is done in

  • 如何仅使用单个数组在 JavaScript 中模拟调用堆栈

    我正在看维基百科页面 https en wikipedia org wiki Call stack在调用堆栈上 并尝试理解这个图像 据我所知 哈哈 const memory memory 0 3 top of stack pointer m

  • 在常数空间中创建 1..N 的随机排列

    我正在寻找枚举固定空间中数字 1 N 的随机排列 这意味着我无法将所有数字存储在列表中 原因是 N 可能非常大 超过可用内存 我仍然希望能够一次遍历这样一个数字的排列 只访问每个数字一次 我知道对于某些 N 可以这样做 许多随机数生成器随机

  • 使用并集查找（又名不相交集）检测图是否是二分图

    我正在 Spoj 上做一个问题 基本上可以简化为检测图是否是二分图 我正在尝试使用 dfs 为图表着色 但它太慢了 有人评论这个 没有 bfs 没有 dfs 没有二部图 简单的并查集就可以做到 确实速度很快 提示 1 偶数长度的环不会影响两

  • 有没有办法在 JTS 中将自相交多边形转换为多重多边形？

    取无效多边形POLYGON 0 100 100 100 0 0 100 0 0 100 一个带有未声明交点的煮蛋定时器形状 许多说明说 JTS 可以使用以下命令创建此版本的有效版本 buffer method Geometry input

  • 如何检查是否存在可能的路径？

    我正在开发一个基于 javascript 的实验性游戏 玩家必须在二维平铺地图上移动才能退出 请随意检查这个小提琴并演奏 http jsfiddle net moonlife 74vLd 我只是随机放置障碍物 但有时障碍物会挡住玩家和出口之

  • 2d 图像点和 3d 网格之间的交点

    Given 网格 源相机 我有内在和外在参数 图像坐标 2d Output 3D 点 是从相机中心发出的光线穿过图像平面上的 2d 点与网格的交点 我试图找到网格上的 3d 点 This is the process From Multip

  • shell脚本中关联数组的时间复杂度

    我想知道在 shell 脚本中使用关联数组时如何构造 实现 另外 我想知道基于 shell 脚本的关联数组的时间复杂度是否是最佳的 因为我们可以使用字母和数字作为它们各自的键 编辑 他们使用什么哈希函数 如果您使用关联数组 则不能通过 使用

  • 具有 2 个属性的背包算法。如何在 3d 数组中实现它？

    当有超过 1 个属性时 我无法理解背包问题 当有 1 个属性时 我必须编写一个使用具有 2 个属性的背包算法的程序 老师告诉我们 它必须在 3d 数组中完成 错误的实现将导致 O 2 n 处理时间 我无法想象这样的数组会是什么样子 假设这是

  • 归并排序中递归树的高度log(n)+1是怎么来的

    我按照 stackoveflow 的建议阅读了一些问题和答案 我正在遵循 cormen 的 算法简介 一书进行自学 那本书里已经解释得很清楚了 但唯一没有解释的是如何在合并排序分析中计算树的高度 如果在后面的章节中对此进行解释的话 我仍然在

  • 实施二分查找有哪些陷阱？ [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 二分查找比看起来更难实现 虽然二分搜索的基本思想相对简单 但细节可能出人意料地棘手 Donald Knuth 新的二分搜索实现中最有可

  • 在java中使用BUBBLE SORT对二维字符串数组进行排序

    类似的问题已经被问过 但从来没有关于二维字符串数组 因此在尝试了很长时间之后我找不到我想要的 我正在尝试使用 BubbleSort 对 java 中的 2D 字符串数组进行排序 作为输入 我收到一个二维字符串数组 一个表 以及您应该排序的

  • 以 O(1) 计算汉明权重 [重复]

    这个问题在这里已经有答案了 在二进制表示中 汉明权重是 1 的数量 我偶然发现了网络并找到了一个 O 1 的答案 v v v gt gt 1 0x55555555 v v 0x33333333 v gt gt 2 0x33333333 in

  • 二维滑动窗口最小值/最大值

    假设我们得到一个大小为 NxN 的像素整数矩阵和一个整数 k 窗口大小 我们需要使用滑动窗口找到矩阵中的所有局部最大值 或最小值 这意味着 如果某个像素与其周围窗口中的所有像素相比具有最小 最大 值 则应将其标记为最小 最大 有一种著名的滑

  • 什么是拉姆达？

    有人可以很好地描述什么是 Lambda 吗 我们为它们设置了一个标签 它们涉及 C 问题的秘密 但我还没有找到一个很好的定义和解释来解释它们是什么 闭包 lambda 和匿名函数不一定是同一件事 匿名函数是任何没有 或者至少不需要 自己名称

  • 使用面向对象的分析和设计对电梯进行建模[关闭]

    Closed 这个问题是基于意见的 help closed questions 目前不接受答案 当涉及到面向对象的设计和分析时 有一组问题似乎在面试和课堂上很常见 这是其中之一 不幸的是 我在大学的 OOP 教授从未真正给出过答案 所以我一

  • 动态规划 (DP) 中的重叠子问题是什么？

    为了使动态规划适用 问题必须具有两个关键属性 最优子结构 and 重叠子问题 1 https en wikipedia org wiki Dynamic programming 对于这个问题 我们只关注后一个属性 有各种不同的定义重叠子问题

  • 数量重新分配逻辑 - 具有外部数据集的 MapGroups

    我正在研究一种复杂的逻辑 需要将数量从一个数据集重新分配到另一个数据集 在例子中我们有Owner and Invoice 我们需要从数量中减去Invoice准确地Owner匹配 在给定汽车的给定邮政编码处 减去的数量需要重新分配回同一辆车出

随机推荐

  • 并发更新期间的 Hibernate StaleObjectStateException

    我在 Java J2EE Web 应用程序中使用 Hibernate 3 5 2 和 Spring Core 3 0 1 当不同的用户同时更新同一记录时 我收到 StaleObjectStateExcpetion 事务由 javax per

  • 带有 2 行文本的 Windows Phone 8.1 AppBarButton 图标

    我想知道如何使 AppBarButton 图标具有 2 行文本 我想让它像 Windows 日历中一样 AppBarButton 不在其图标中显示文本或任意 Xaml 它必须是来自字体 位图或路径的符号 对于这样的日历显示 最好使用位图 由

  • 如何在 Isabelle 中定义偏函数？

    我尝试用以下方法定义偏函数partial function关键词 它不起作用 这是最能表达直觉的 partial function tailrec oddity nat gt nat where oddity Zero Zero oddit

  • 如何通过 Google Apps 日历脚本向访客发送邀请

    我正在尝试通过 Google Apps 脚本将访客添加到日历活动 并在我的脚本添加访客后立即发送邀请 但我找不到向客人发送电子邮件邀请的方法 var events calendar getEvents start date end date

  • firebase实时数据库安全规则允许特定用户

    我当前的 Firebase 实时安全规则如下 rules users read true indexOn email user id read true write auth null user id auth uid 它们翻译为只有经过身

  • ASIHTTPRequest 支持的 RestKit 对象映射

    我们必须支持一些使用 ASIHTTPRequest 运行的旧代码 但我们希望 RestKit 提供对象映射和核心数据支持 有谁知道有什么方法可以将这两者 粘合 在一起吗 我想象使用 ASIHTTPRequest 来处理请求 然后有人手动将有

  • 双精度重载运算符=

    是否可以重载 double 类型的 运算符 我有以下内容 double operator double a Length b return a b getInches 12 b getFeet 3 2808 0 9144 它抛出以下错误 d

  • 在视图上创建遮罩效果

    我想在 UIView 上创建遮罩效果以完成以下任务 我将在屏幕中显示一个密封的盒子 用户将能够触摸 刮擦 屏幕以显示该图像 UIView 后面的内容 类似于那些彩票 你应该刮掉结果顶部的一些封面材料 如果有人能指出我正确的方向那就太棒了 我

  • 如何更改 UITableView 的高度以适应其动态内容？

    我有一个 UITableView 其中包含一个单元格 该单元格又 包含一个 TTTextEditor Three20 控件 它的所有意图和目的都是 UITextView 我使用 TTTextEditor 以便用户可以输入动态数量的文本 并且

  • xcode 中的调试符号是什么

    什么是调试符号 用法是什么 能够将带有调试符号的应用程序提交到应用程序商店吗 请帮忙 提前致谢 dSym 在您归档项目时生成 您无需为此做任何事情 它允许你符号化你的崩溃日志 否则它只是毫无意义的内存地址 它是构建代码和源代码之间的链接

  • Android 弹出菜单填充父级

    我尝试设置弹出菜单来填充网格上的孔项目 目前它看起来像所附的第一张图片 下一张是我想要的效果 My code private void showPopupMenu View view inflate menu ContextThemeWra

  • 使用 Laravel 5.3 的 Amazon SES 403 Forbidden SignatureDoesNotMatch

    我正在使用 Laravel 5 3 EC2 和 SES 发送电子邮件 配置 邮件 php driver gt env MAIL DRIVER smtp host gt env MAIL HOST smtp mailgun org port

  • 存储性能不良：原因不明

    是什么原因造成的错误的存储属性 成员 resetQueryStatus Employee employeeId 上的 employeeId 例外 例外似乎出现在我的连接点处 Database public class FireEvacuat

  • 获取 18 号下一次出现的日期

    好的 所以我需要使用 PHP 来获取下一次出现 18 号的日期 例如 假设我在 2011 年 12 月 28 日运行了脚本 我需要一些能够输出 2012 年 1 月 18 日的代码 如果是 2011 年 4 月 9 日 我需要将代码吐出 2

  • 为什么括号会导致对象解除绑定？

    当我用括号包围一个新对象调用并立即调用它的方法时 Node 或者一般来说只是 v8 将抛出 TypeError this getName 不是函数 错误 如果我不将它包裹在括号中 则不会抛出任何错误this已正确绑定 function Gr

  • 使用javascript 下载base64 数据| IE11 [重复]

    这个问题在这里已经有答案了 我正在尝试使用 JavaScript 中的 window location href 下载 base64 数据 它在 Chrome 中工作正常 但相同的代码在 IE11 中不起作用 您能否让我知道解决方法或解决方

  • 连接单元格

    我有两个细胞 A 100x2 double 80x2 double 50x2 double B 100x5 double 80x5 double 50x5 double 我怎样才能将它们连接起来以获得类似的东西C cat 2 A B 对于每

  • 将编辑文本字段中的文本添加到电子邮件中

    我有一个应用程序 希望与我们联系 以便用户输入姓名 地址 电话号码和评论部分 然后他们将单击 撰写邮件 按钮 它将自动将文本加载到电子邮件中 已经解决了一些代码 但不确定如何将编辑文本中的文本放入我的电子邮件消息中 任何人对我如何做到这一点

  • 为什么 unittest.mock.ANY 不能与 Django 对象正常工作？

    我在 Django 中编写了一个测试 并且我using unittest mock ANY忽略字典中的某些值 这是测试 from django test import TestCase from django contrib auth im

  • 快速轴对齐单元格遍历算法

    给定一个轴对齐的正方形 分为四个大小相等的单元格 A B C 和 D 给定一条从点 s1 到点 s2 的线段 查找该段 如果有 遍历的单元格 按遍历顺序排序 的最快方法是什么 在上面的例子中 正确的结果是 第 1 段 D 分段 2 A B

热门标签