python - 如何找到包含给定点的德劳内三角剖分面

Question

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

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

Answer 1

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

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

Answer 2

我会假设三角形除了公共边外不相交。

您不想独立检查每个三角形（或它们的子集）。主要原因是计算错误 - 由于它们，您可能会在多个三角形（或零）的“内部”得到答案，这可能会破坏程序的逻辑。

更健壮的方法是：

1. 找到离点最近的边
2. 选择接触此边缘的三角形之一
3. 对该三角形进行一次检查（该点与第三个三角形顶点位于同一侧）
4. 如果“内部” - 返回这个三角形
5. 如果“外部” - 在此边缘返回另一个三角形（如果没有其他三角形，则返回“无”）

即使你会因为计算错误而返回错误的三角形，仍然只有一个三角形，并且点将离它足够近，可以接受这样的错误。

对于＃1，您可以使用 Michael Wild 建议的四叉树之类的东西。

Answer 3

Delaunay 三角剖分本身就是一种搜索数据结构。您的 Delaunay 三角测量实现可能具有定位功能。您是如何计算点的 Delaunay 三角剖分的？

CGAL实现了 2D 和 3D 三角测量。生成的数据结构能够使用从给定点步行来定位任何点。例如参见手册的那一章。CGAL 是一个 C++ 库，但它有python 绑定。

Answer 4

这个简单的例子对 10 个随机点进行三角剖分，生成另外 3 个随机点，如果它们落在三角形内，则给出顶点：

import numpy as np
from pyhull.delaunay import DelaunayTri

def sign(a,b,c):
    return (a[0]-c[0])*(b[1]-c[1])-(b[0]-c[0])*(a[1]-c[1])

def findfacet(p,simplice):
    c,b,a = simplice.coords
    b1 = sign(p,a,b) < 0.0
    b2 = sign(p,b,c) < 0.0
    b3 = sign(p,c,a) < 0.0
    return b1 == b2 == b3

data = np.random.randn(10, 2)
dtri = DelaunayTri(data)

interpolate = np.random.randn(3, 2)

for point in interpolate:
    for triangle in dtri.simplices:
        if findfacet(point,triangle):
            print "Point",point,"inside",triangle.coords
        break

matplotlib用于可视化（代码省略）：

青色虚线现在连接点，以插入它所在的三角形的顶点。黑线是凸包，青色实线是德劳内三角剖分。