CGAL - 在多面体内查找点

Question

我正在使用 CGAL 库来执行几何运算的代码。

我有一个Polyhedron 对象, 并按照[文档][2]中的代码创建了一个网格域。

使用方法 CGAL::make_mesh_3() 创建网格，它是这个[type][3]的对象。

接下来我需要一个表示网格所在空间的普通3D数组。 我需要逐点遍历数组(i,j,k)，并决定这些坐标对应的点(在i、j、k被转换为正确的单位后)是否在由多面体定义的域内。

因此，我使用来自 Triangulation 对象的方法 locate [4] 查找点的位置。该方法返回一个 Cell_Handle [5]和一个 Locate_type (从中可以了解点的位置)

Triangulation类具有其他方法，如 is_cell() 和 is_infinite() 等...

关键是如果我将查询设置为知道点是否在多面体内，例如：

if( tr.is_cell(ch)  && !tr.is_infinite(ch) ) {
    return true;
  }else {
    return false;
  }

ch 是通过查询 locate 返回的 Cell_handle。

只要多面体不是一个复杂对象，它就有效。对于简单的对象（如锥体、球体等），我会得到一个漂亮的输出结果，如下图所示：

Cone

但如果我尝试像一个环面这样的对象，它就不起作用了。在我贴出的 if 语句中，环面上的孔洞被认为在网格内部（环面内部的点会返回“true”），但它们实际上不应该在内部。我已经尝试了其他语句来过滤它，例如：

if ( lt == Tr::INSIDE_CONVEX_HULL && !tr.is_infinite(ch)) {
    return true;
  }

但结果却相同。如果对象有孔或多面体不等于CONVEX_HULL，我得不到我想要的东西。稍加思考，CONVEX_HULL在最好的情况下就是我所得到的。

那么我该如何确定一个点（x,y,z）是否位于多面体内部或网格内部？

有没有办法实现这个目标？

- RolandDeschain

---

也许你可以将多面体分解成凸多边形，并逐个进行测试？ - AndyG

避免“洞”这个问题的方法是什么？比如将我的环面分成两半，对每一部分进行测试？还有其他更通用的想法吗？ - RolandDeschain

Answer 1

如果您已经在网格中定位了您的点，则拥有包含该点的单元句柄。您可以使用C3T3的成员函数is_in_complex(Cell_handle)来确定此单元格是在域内还是域外。

请注意，如果您想直接使用多面体进行操作，则可以使用函数对象Side_of_triangle_mesh。

- sloriot