如何查找包含给定分

我已经绘制n随机点（黑点）和使用德劳内三角德劳内三角面，现在我想插m随机评估点（红点）所以我需要计算评估点位于哪个三角形内部。如何查找包含给定分

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

2013-04-12 Chris Seymour

您给这个问题提供了一个“三角测量”标签。这是否意味着三角形不相交？他们是否形成了一些对象的三角剖分（如果可能，指定它）？ – unkulunkulu

你可以看看SciPy，看起来它有一些问题的实现。你可以从这里开始http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Delaunay.html – unkulunkulu

我对你的问题做了一个实质性的编辑，使它具体关于delaunay三角剖分（因为它是一个专题）。当然，您可以自由回滚，但我认为这更合适:)当然，现有的答案仍然适用，但我认为更有效的算法存在于delaunay三角剖分中。 – unkulunkulu

对于给定的三角形，ABC，一个点在三角形内，如果它是上线AB的相同侧的点C是，在BC线的相同侧作为点A，并且在相同AC线的一侧为B点。您可以预先优化每个三角形的检查，并检查它们，直到找到它所在的三角形。有关更多详细信息，请参见this page。

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

来源

2013-04-12 10:31:40

如果三角形的数量非常大，则可能需要建立四叉树结构，以便更快地搜索需要检查的相关三角形。 –

没有四叉树，也没有bruteforce检查，有一个简单的图遍历方法，只从任意随机顶点开始沿着三角形的边缘走。 – WhitAngl

@WhitAngl你能提供一个参考吗？ –

我会假设三角形除了共同的边缘不相交。

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

更可靠的方法是：

查找最接近边缘点
选择的一个三角形触及此边缘
做一次检查该三角形（该点位于同一侧第三个三角形顶点）
如果“inside” - 返回这个三角形
如果“outside” - 如果没有其他三角形返回另一个三角形（或“nothing”）

即使由于计算错误而返回错误的三角形，仍然只有一个三角形，并且点会接近它以接受这样的错误。

对于＃1，您可以像Michael Wild所建议的那样使用四叉树。

来源

2013-04-12 10:57:04 maxim1000

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

CGAL实现了2D和3D三角测量。所得到的数据结构能够使用从给定点的步行来定位任何点。例如参见that chapter of the manual。 CGAL是一个C++库，但它有python bindings。

来源

2013-04-12 13:32:11 lrineau

Delaunay三角剖分对许多事情都很有用，而不仅仅是空间搜索。所以我不同意实现*必须具有位置功能。 –

我很抱歉我的措辞。当我说：“你的Delaunay三角剖分实现必须具有位置功能”时，“必须”应该是“可能”。 – lrineau

这个简单的例子进行三角测量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形象化（代码略）：

enter image description here

虚线青色线现在连接点与三角形的它规定内的顶点进行内插。黑线是凸包，实线是青色三角形。

来源

2013-04-14 14:56:22

如何查找包含给定分

回答

相关问题