网格二维三角剖分

Question

我正在尝试制作一个程序，在空间中的一个点找到包含它的网格中的三角形。中间有一个步骤。但我正在努力寻找另一种方法，因为它效率不高。

:

对于K是一个三角形，i是这个三角形的一个顶点，能够找到这个顶点的邻边和对边。困难的部分是，它需要在O(nt)或O(ntlog2(nt))中完成我的网格中的所有三角形。我想使用无序映射来存储每个三角形的所有边，这样我就可以在O(1)中找到我要找的三角形，所以对于O(nt)中的所有网格。

但我不知道如何编码我的无序映射，以便有两个顶点的值在第一列和三角形的数字在第二和第三列。

我的网格属性是:

 public:
  //attribut
  std::vector<Sommet> m_Sommet; // Sommet's array
  std::vector<Triangle> m_Triangle; //Triangle's array

Answer 1

您应该使用与网格相关的分区结构，边界卷层次结构非常容易计算，轻量级且高效(您可以查看本页中的各种排序算法)。如果你的网格是静态的，那么kd-tree应该更快，但也更复杂。