如何找到包含给定点的 delaunay 三角剖分面

Question

我已经绘制了n随机点（黑点）并使用了 delaunay 三角剖分，现在我想插入m随机评估点（红点），所以我需要计算评估点位于哪个三角形内。

计算三角形每个点的顶点的方法是什么？

Answer 1

对于给定的三角形 ABC，如果一个点与点 C 位于直线 AB 的同一侧，与点 A 位于直线 BC 的同一侧，并且与点位于直线 AC 的同一侧，则该点位于三角形内部B 是。您可以针对每个三角形预先优化此检查并检查所有三角形，直到找到它所在的三角形。有关更多详细信息，请参阅此页面。

为了节省计算量，您可以计算每个三角形的点的最小和最大 X 和 Y 坐标。如果某个点的 X 和 Y 坐标不在最小值和最大值范围内，您可以立即跳过检查该三角形。如果该点不在包围三角形的矩形内，则该点不能在其内部。