有效地找到给定点所在的Delaunay三角剖分面

本文关键字：Delaunay 三角剖分 有效地 | 更新日期: 2023-09-27 18:08:45

给定一个点集的Delaunay三角剖分，我应该如何索引我的三角剖分来快速定位点?

我正在循环所有的三角形。对于每个三角形，我检查给定的点是否在三角形的边界矩形内。如果是，则使用几何方程检查三角形。

这是慢的。有什么办法让搜索更有效率吗?

有效地找到给定点所在的Delaunay三角剖分面

任务完成了，这就是我最后的做法:

1)检查点是否在三角形边界矩形内

2)指定该点作为水平线的起点，以最大宽度结束。

3)检查(1)中的三角形与(2)中的直线的交点。

如果三角形相交，检查水平线与三角形相交的次数

5)相交1次，表示三角形中的点。

参考:

快速生成由横截面轮廓获得的三角化对象内的点

从快速实用到理论上健壮，您可以使用以下三种方法:

  • 构建一个规则网格，其中每个单元格包含一个与之相交的三角形列表。给定一个查询点，在常量时间内确定包含该查询点的单元格，然后仅将您的查询点与该单元格列表中的那些三角形进行比较。

  • 构造一个四叉树，其中每个叶单元包含与其相交的三角形。将查询点定位到四叉树叶需要logtime，但这在速度和内存方面都更有效。

  • 在所有三角形上向下扫描一条水平线。点集中的点对应于事件。在每个事件中，一些三角形开始与横线相交，而其他三角形停止与横线相交。您可以使用不可变(又名持久性)排序映射数据结构来有效地表示这一点。map<double, sweepstate>，其中键是某一事件时横线的y轴截距，sweepstate是线段对的排序列表(对应于三角形的左右边)。给定一个查询点，首先使用它的y值查找一个sweepstate，然后执行单个梯形包容测试。(两条水平扫线和它们之间的两条线段形成一个梯形)

解决此点定位问题的常用方法是高效梯形分解。它使用O(N)空间，在O(N.Log(N))预处理时间之后，将查询时间减少到每点O(Log(N))。

也可能是您的查询点的分布允许使用其他/更简单的方法。

解是一个层次树，即树状图或层次簇。例如，使用欧几里得距离:http://en.m.wikipedia.org/wiki/Hierarchical_clustering。或者您可以使用度量树。

相关文章：