程序员经验分享-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

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

  • 检查有效的 IMEI

    有人知道如何检查有效的 IMEI 吗 我找到了一个可以检查此页面的功能 http www dotnetfunda com articles article597 imeivalidator in vbnet aspx http www do

  • Python Pandas：沿一列比较两个数据帧，并返回另一个数据帧中两个数据帧的行内容

    我正在处理两个 csv 文件并作为数据框 df1 和 df2 导入 df1 有 50000 行 df2 有 150000 行 我想将 df2 的 时间 与 df1 求时间差并返回所有列的值 对应相似的行 保存在df3中 时间同步 例如 35

  • “包含字符串”的快速索引

    在我的应用程序中 我有多达数百万个短字符串 大部分短于 32 个字符 我想实现一个带有附加列表的搜索框 该列表仅包含包含在搜索框中输入的整个字符串的元素 如何预先建立索引来快速找到此类字符串 所有排序的 STL 容器都会检查整个字符串 对于

  • 如何在 C# 中以编程方式创建柔和的颜色？

    根据所需的颜色数量均匀分布地生成它们 如果指定的计数为 8 则看起来像这样 List

  • 当给定块大小时反转单链表

    有一个单连接链表 并给出了块大小 例如 如果我的链表是1 gt 2 gt 3 gt 4 gt 5 gt 6 gt 7 gt 8 NULL我的块大小是4然后反转第一个4元素 然后是第二个 4 个元素 问题的输出应该是4 gt 3 gt 2 g

  • Python 旅行商贪婪算法 [关闭]

    Closed 这个问题需要调试细节 help minimal reproducible example 目前不接受答案 因此 我为旅行推销员问题创建了一种排序 并按 x 坐标和 y 坐标进行排序 我正在尝试实施贪婪搜索 但无法做到 此外 每

  • heapq.nlargest 的时间复杂度是多少？

    我在看演讲者说 获得t列表中最大的元素n元素可以在O t n 这怎么可能 我的理解是创建堆将是O n 但是复杂度是多少nlargest本身就是O n t or O t 实际的算法是什么 在这种情况下 说话者是错误的 实际成本是O n log

  • 是否有加权水库采样的算法？ [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 当数据流中的点具有相关权重时 是否有一种算法可以执行水库采样 Pavlos Efraimidis 和 Paul Spirakis 的算

  • 在一个区域中拟合二维多边形的算法？

    这有标准吗 算法名称 说 我有 10 个不同大小的多边形 我有一个特定大小的区域 我想知道如何填充该区域中的最多多边形 以及它们是如何拟合的 笔记 多边形可以根据限制集进行旋转 一个可能的名称是包装问题 http en wikipedia

  • 覆盖二维平面上给定点的最小圆

    问题 覆盖 2D 平面上给定 N 个点的圆的最小可能直径是多少 解决这个问题最有效的算法是什么 它是如何工作的 这是最小圆问题 http en wikipedia org wiki Smallest circle problem 请参阅参考

  • 用于查找最近邻居的空间划分算法如何工作？

    为了找到最近的邻居 空间分区 http en wikipedia org wiki Nearest neighbor search Space partitioning是算法之一 它是如何工作的 假设我有一组 2D 点 x 和 y 坐标 并

  • sigmoid 的导数

    我正在使用反向传播技术创建一个神经网络进行学习 我知道我们需要找到所使用的激活函数的导数 我正在使用标准 sigmoid 函数 f x 1 1 e x 我已经看到它的导数是 dy dx f x f x 1 f x 这可能是一个愚蠢的问题 但

  • 颜色变换器功能上的堆栈溢出错误

    我有两种颜色 红色 和 鲑鱼色 我需要动态创建面板以及面板背景颜色 这些颜色必须介于两种颜色之间 红色 public Color x y protected void Page Load object sender EventArgs e

  • 我如何开始玩五子棋？

    我读到Gomoku http en wikipedia org wiki Gomoku它可以使用 Minimax 和 Alpha Beta 剪枝算法来实现 所以 我阅读了这些算法 现在了解了游戏将如何解决 但是当我坐下来编写代码时 我面临着

  • 数组所有可能的组合

    我有一个字符串数组 ted williams golden voice radio 我希望这些关键字的所有可能组合采用以下形式 ted williams golden voice radio ted williams ted golden

  • Z 算法背后的直觉

    Z算法是一种复杂度为O n 的字符串匹配算法 一种用例是从字符串 B 中查找字符串 A 的最长出现次数 例如 overdose from stackoverflow 将会 over 您可以通过使用组合字符串调用 Z 算法来发现这一点 ove

  • while循环的时间复杂度是多少？

    我正在尝试找出 while 循环的时间复杂度 但我不知道从哪里开始 我了解如何找到 for 循环的复杂性类别 但是当涉及到 while 循环时 我完全迷失了 关于从哪里开始有什么建议 提示吗 这是一个问题的示例 x 0 A n some a

  • 有向未加权图中的最长非循环路径

    什么算法可用于找到未加权有向无环图中的最长路径 动态规划 http en wikipedia org wiki Dynamic programming 它也被引用于最长路径问题 http en wikipedia org wiki Long

  • 找到一个数字所属的一组范围

    我有一个 200k 行的数字范围列表 例如开始位置 停止位置 该列表包括除了非重叠的重叠之外的所有类型的重叠 列表看起来像这样 3 5 10 30 15 25 5 15 25 35 我需要找到给定数字所属的范围 并对 100k 个数字重复该

  • 从列表中选择项目以求和

    我有一个包含数值的项目列表 我需要使用这些项目求和 我需要你的帮助来构建这样的算法 下面是一个用 C 编写的示例 描述了我的问题 int sum 21 List

随机推荐

  • 并发更新期间的 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

热门标签