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

Question

给定点集的 Delaunay 三角剖分，我应该如何索引我的三角剖分以进行快速点定位？

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

这很慢。关于如何提高此搜索效率的任何想法？

Answer 1

任务完成，这就是我最终完成它的方式:

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

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

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

4) 如果三角形相交，检查水平线与三角形相交多少次。

5) 如果相交1次，则表示三角形中的点。否则，不在三角形中。

引用:

Fast generation of points inside triangulated objects obtained by cross-sectional contours