程序员经验分享-hwhale

Voronoi 图、Delaunay 三角剖分 - 数据结构

2023-12-09

我想计算 Voronoi 及其对偶 Delaunay 三角剖分。我正在使用 Watson Bowyer 算法。之后我的目标是计算 alpha 形状（凹壳）。所以我需要快速访问给定点的 voronoi 单元，邻居......

您的 Voronoi/Delaunay 算法使用了哪些数据结构？我考虑过使用具有联合查找操作的不相交集数据结构，这样我就可以“绑定”到一个父级，原始数据集中的点 p，Vp 中的点集。然而，Voronoi 图中的一个点“属于”多个 Voronoi 单元。

你有什么建议，或者你能暗示一些好的参考吗？

Regards.


我建议你看一下半边数据结构：

http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml

半边数据结构被用于许多应用程序和框架中。它的一种实现可以在 GEL 框架中找到：

http://www2.imm.dtu.dk/projects/GEL/

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

Algorithm

datastructures

geometry

Delaunay

Voronoi

Voronoi 图、Delaunay 三角剖分 - 数据结构 的相关文章

  • WPF 3D - 在复杂几何体上映射渐变画笔

    我想问是否有人知道如何在 WPF 3D 中的复杂对象上映射渐变画笔 结果应该类似于 matlab 中的 3D 图像 例如 3D 函数 假设您有一些想要可视化的 3 维数据 并且想要通过颜色区分某些级别的值 给定一个 GradientBrus

  • 模式识别算法

    过去我必须开发一个充当规则评估器的程序 你有一个先行词和一些后续词 动作 所以如果先行词评估为真 则执行的动作 当时我用的是修改版RETE算法 http en wikipedia org wiki Rete algorithm RETE 有

  • 找到一个恰好出现了 N/2 次的数字

    这是我的面试问题之一 给定一个包含 N 个元素的数组以及元素出现的位置正好 N 2次 其余 N 2 个元素是unique 您如何找到运行时间更好的元素 请记住 元素未排序 您可以假设 N 是偶数 例如 input array 10 2 3

  • 在 O(n) 时间内对列表中的数字方块进行排序？

    给定一个按排序顺序排列的整数列表 例如 9 2 0 2 3 我们必须对每个元素进行平方并按排序顺序返回结果 所以 输出将是 0 4 4 9 81 我可以找出两种方法 O NlogN 方法 我们将每个元素的平方插入哈希集中 然后将元素复制到列

  • 寻找 5 字节 PRNG 的种子

    这是一个古老的想法 但从那时起我就无法找到一些相当好的方法来解决它提出的问题 所以我 发明 了 见下文 一个非常紧凑的 在我看来 性能相当好的 PRNG 但我无法找出算法来为其在大位深度上构建合适的种子值 我当前的解决方案只是暴力破解 它的

  • 单词预测算法

    我确信有一篇关于此问题的帖子 但我找不到提出这个确切问题的帖子 考虑以下 我们有字典可供使用 我们收到了许多单词段落 我希望能够根据此输入预测句子中的下一个单词 假设我们有几个句子 例如 你好 我的名字是汤姆 他的名字是杰瑞 他去了没有水的

  • 二分查找问题？ [复制]

    这个问题在这里已经有答案了 可能的重复 实施二分查找有哪些陷阱 https stackoverflow com questions 504335 what are the pitfalls in implementing binary se

  • 如何发现“贪婪”算法？

    我正在读一本关于 贪婪 算法 但我很难发现它们解决真正的 顶级程序员 问题 If I know给定的问题可以用 贪婪 算法来解决 因此编写解决方案非常容易 然而 如果我没有被告知这个问题是 贪婪的 我就无法发现它 用 贪婪 算法解决的问题有

  • 几何：找到两点之间特定距离的点

    这类似于这个问题 https stackoverflow com questions 328107 how can you determine a point is between two other points on a line se

  • 期望最大化算法的数值示例[重复]

    这个问题在这里已经有答案了 由于我不确定给出的公式 有人可以提供 EM 算法的简单数字示例吗 一个非常简单的具有 4 或 5 个笛卡尔坐标的坐标就可以了 那这个呢 http en wikibooks org wiki Data Mining

  • 如何改进 PHP 分页算法？

    我正在研究 PHP 中的分页算法 我可以猜测它需要改进的空间 所以我想对如何改进它有一些想法 无论是从 UI UX 的角度清理代码本身 还是你能想到的任何其他东西 该算法应输出如下所示的分页 1 2 3 6 7 8 97 98 99 or

  • 将两个大数作为字符串相除，而不使用java中的Bignumbers

    我需要在不使用 Biginteger 的情况下划分两个大整数 因为数字不能存储在原始类型中 因为我需要从给定的字符串中逐个字符地执行此操作 我已经创建了一个名为 BigNumber 的类 用这个类我可以 Add multiply 比较两个内

  • 将列表映射到霍夫曼树，同时保留相对顺序

    我在霍夫曼树上的搜索算法方面遇到问题 对于给定的概率分布 无论输入数据的排列如何 我都需要霍夫曼树相同 这是发生的情况与我想要的情况的图片 基本上我想知道是否可以保留列表中项目与树的相对顺序 如果不是 为什么会这样 作为参考 我使用霍夫曼树

  • 给定一个零索引数组 & 该数组的平衡索引[关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 给出一个由 N 个整数组成的零索引数组 A 该数组的平衡索引是任何整数 P 满足 0 P 例如 考虑以下由 N 8 个元素组成的数组

  • WPF 中的填充弧

    I am trying to draw a figure something like this 我需要为每个弧段都有一个独特的元素 我可以根据需要处理事件并重新着色 我有点不确定如何在 WPF 中创建正确的几何图形 我可以根据圆的半径和与

  • 内部有图像的 CSS 响应式圆圈

    蓝色div有固定的高度和响应宽度 里面应该有一个相同高度的圆形图像 这是我尝试过的 https jsfiddle net xnkkrhnt 1 https jsfiddle net xnkkrhnt 1 如何使完美的中心圆始终为蓝色 div

  • 快速查找具有最大总不同元素的列表列表的子集

    给定元组列表的列表 我想找到列表的子集 该子集最大化不同整数值的数量 而不重复任何整数 该列表看起来像这样 x 1 2 3 8 9 10 15 16 2 3 10 11 9 10 11 17 18 19 20 21 22 4 5 11 12

  • 通过保留和复制来复制向量，还是通过创建和交换来复制向量更有效？ [复制]

    这个问题在这里已经有答案了 我正在尝试有效地复制向量 我看到两种可能的方法 std vector

  • 我可以在线性时间内检查有界列表是否包含重复项吗？

    假设我有一个Int列表 其中元素已知是有界的 并且列表已知不长于它们的范围 因此它完全有可能不包含重复项 如何才能最快地测试是否是这种情况 我知道nubOrd https hackage haskell org package contai

  • 查找按降序排序的向量中严格小于某个键的第一个元素

    据我了解 可以使用 find if STL 算法函数来完成此任务 如下所示 long long int k k key scanf lld k auto it find if begin v end v k auto e return e

随机推荐

热门标签