问题标签 [delaunay]

我目前正在研究一个将 2D 点集修改作为子问题的项目。点集本身将包含几个点簇，我需要以某种方式将它们彼此分开，然后在它们的簇壳内放松它们的点。或者，获取集群的外壳点并将它们用作域并在其中分布（大致）均匀间隔的点就足够了。所以可以跳过放松。作为最坏的情况，我需要处理几个点集，包括约 100k 个顶点，因此使用的算法应该很快。我知道这个主题的复杂性，这就是为什么我不想重新发明轮子，而是尽可能使用现有代码。到目前为止，我发现了以下内容：

1. 用于点集松弛：Fortunes/Sullivans “Sweep Line”算法：据说是最快的单线程voronoi 图构造器。然而，代码似乎很难扩展，并且默认情况下可提取的信息不包含 voronoi 单元外壳数据（它们的顶点位置），至少需要计算质心并进行下一次松弛迭代。此外，矩形以外的任何域都将不可用。

2. CVT：一组用于创建 voronoi 图的多功能库。它支持点的松弛，也支持用户指定区域内的点集。

3. CGAL：具有基本 MP 支持的广泛框架，但显然没有集成的松弛方法。我需要为每个点集子集群创建一个 delaunay 三角剖分，并将其提供给一个 voronoi 适配器，然后给我提供迭代器来查询 voronoi 细胞外壳数据以进一步放松。就我通过文档而言，它应该支持域（几千页:)

4. 还有一些，例如 Voro++，它似乎主要在 3D 中工作；三角形，它使用区域约束从给定域创建 delaunay 三角剖分，以便可以使用三角形顶点作为结果点。

好的，目前在我看来，CVT 应该满足我的需求，同时保持这一切都非常简单。但我不确定，所以问题是：有没有人有过点集松弛实施的经验，最好是使用域？哪些现有代码更可取？

谢谢毛皮建议！t

在给定一组点的情况下，我很难找到有关如何构造 Delaunay 三角剖分的算法的简单而完整的解释。谁能向我解释或将我重定向到一些以简单方式解释算法的资源？

谢谢

当应用于三角 3d 曲面图时，我看到 MATLAB R2011b 中的数据光标出现不稳定的行为：单击某些点会选择完全不同的点。圆柱体示例：

然后启用数据游标模式并尝试选择前面一列的最上面的点。在我的安装中，MATLAB 不会选择光标下的点，而是随机选择一个不同的点。

这是一个错误还是我做错了什么？

我正在尝试关注有关 delaunay 三角剖分的对话，但我无法获得与图片中 axel 相同的结果。我真的很想知道如何只在脸上绘制网格？我还需要知道这个循环的作用是什么，“点”的类型到底是什么？

谁能帮帮我吗。谢谢 ：）

如何从 Delaunay 三角测量中删除大于我需要的距离？

示例数据：

绘制地图：

使用 tri.mesh() 进行Delaunay 三角剖分- 包（tripack）

如何仅提取较短的距离？我不需要那些大的，你肯定知道我的意思是什么距离。在 tri.mesh() 函数中是否有一些论点可以做到这一点？或者它可以在它之后完成？

距离甚至存储在这个对象中吗？

I have computed a Delaunay triangulation using DelaunayTri() in Matlab R2010b. Now I would like to burn a subset of the triangles (i.e. 12200 triangles) into a matrix (Raster). Is there any fast/efficient way of doing this?

I have tried using both poly2mask() and inpolygon() to select pixels inside the triangles, but this is rather slow.

我有一个共享边的所有三角形的列表。如何绘制 voronoi 图？我遍历 Delaunay 三角形并将其与顶点 1 = 顶点 2 和顶点 2 = 顶点 1 进行比较，即 如果有相同的边缘。它还检查顶点 1 = 顶点 1 和顶点 2 = 顶点 2 的时间。在等式中，两边都是不同的三角形。这是来自 boywer watson 算法的相同循环。

我开发了一个代码，它采用一组 3D 坐标，并执行三角测量以生成凸包/Delaunay。

这很顺利，使用德鲁奈三角剖分，我可以使用 tsearchn 测试点是否包含在给定的体积中。

现在我想取两个这样的 3D 体积，并测试它们是否相交。此外，我想知道体积 A 与体积 B 相交的百分比。

我认为我可以在其中一个体积内生成一个网格点，然后使用 tsearchn 将它们测试到另一个。但我想知道是否有人知道更方便的方法。或者有做类似分析的建议。

非常感谢！

编辑...示例代码

对于此示例代码，shapeA将 50% 与shapeB.
我在代码末尾包含了一个部分，显示了tsearchn
我知道我可以通过增加形状的点数并使用测试它们来解决我的问题tsearchn

假设我有一个受约束的 Delaunay 三角剖分，其中刻面与某个“标签”（某些抽象属性）相关联。我想从约束中删除与共享相同标签的构面相关的边缘。什么是有效的方法，以及如何确保在移除约束后获得的方面保持其标签？

这是从 CGAL 示例中提取的一段代码，以说明我的目的：

我从那里看到了几种可能性：

1. 通过在原始三角剖分中插入仅连接具有不同标签的面的约束来构建新的 CDT。
2. 使用变体cdt.remove_constrained_edge(fh, i, out)来恢复可能受约束删除影响的方面，并相应地处理它们（但它仍然会留下迭代器无效的问题）。
3. 使用 BFS/DFS 遍历 facet 并结合前面的评论，但我仍然需要知道哪个排队/堆叠的 facet 受到每个约束删除的影响。
4. 在遍历期间使用 aset而不是queue/ stack，这样我就可以从我需要访问涉及已删除约束的构面的句柄中删除（在删除之前），因为在删除之后它们可能会失效（如果发生翻转）。

那么，StackOverflow 对此有何看法？

我有一个 3D 点云，我使用 Matlab 的函数 DelaunayTri 将其转换为 Delaunay 三角剖分。现在我有一个 3D 测试点，想在 Matlab 中计算该点与三角测量之间的最小距离。

到目前为止，我一直在考虑使用 Matlab 中 DelaunayTri 类的nearestNeighbor(...) 成员函数来找到三角剖分中离我的测试点最近的点，然后计算它们之间的距离。那是一些东西，但这不是我真正想要的。

三角剖分上离我的测试点最近的点通常不是三角剖分的顶点，而是三角形面上的某个位置。我怎样才能找到这一点？

谢谢！！！