问题标签 [polyhedra]

假设有一个表示对象A的多面体，并且想要得到它的凹度。

这样做的一个选项包括计算对象A的凸包CH并将差异CH - A拆分为连通分量。

为此，我尝试在 CGAL 中使用 Nef Polyhedrons 模块。这允许将A和CH转换为 Nef 多面体，以便轻松应用设置差异等布尔运算。

一旦作为 Nef 多面体获得差值，其mark在场中标记为 1 的体积应该表示差值的有限连通分量，并且可以使用函数 转换回多面体convert_inner_shell_to_polyhedron。

从理论上讲，这种方法应该可以正常工作，但在实践中，当使用的多面体是从 STEP 文件转换为定义多面体的三角形网格的结果时，就会出现问题。事实上，以 STEP 文件中的四边形面为例。在转换过程中，必须至少转换成两个三角形。问题在于，当将生成的三角形保存到表示转换后的网格的文件（例如 OFF 文件、STL 或 OBJ）中时，它们可能会因为顶点坐标近似而失去共面性。

这会在计算 Nef 多面体差异时导致以下不良行为：

• 产生了一些非常薄的体积，因为四边形的对角线之一（假设四边形已被分成两个三角形）已经“移动”到多面体的内部；
• 该函数convert_inner_shell_to_polyhedron打印一条错误消息，例如

  lookup_halfedge()：输入错误：面 11 与面 0 共享从顶点 2 到顶点 1 的半边。

第一个行为不是一个大问题：转换为多面体的每个体积都可以检查其厚度并最终丢弃。然而，第二个返回一个空的多面体，据我所知，没有办法获得所需的体积。

所以我问你解决这个问题的方法。在这里，我报告了我对此所做的一些观察：

• CGAL 多面体允许使用多边形面而不是三角形面，因此可以将 STEP 文件转换为多边形网格：这应该允许保持相同面的点的共面性。但是，我找不到不通过三角形网格就可以执行转换的软件；
• 直接将 STEP 文件转换为 CGAL 多面体实例。我认为这种方法在合理的时间内远非负担得起。
• 实现一些方法来纠正相邻面的点的共面性。这可能是一种可行的方法，但是在手动改变多面体顶点的位置时可能会出现一些其他问题。

我有一个点云，我将它作为一系列点导入到 pyntcloud 库中，它是一个完全 3D 的点云，因为它的边界形成了一个体积。

我计算法线

我想生成一个实体对象，最好是多面体，我查看了 CGAL 绑定和 pymesh，但我没有找到可行的解决方案。有任何想法吗？

数据结构如下

我正在使用 qt-creator 创建一个应用程序，它读取 .off 文件并预览它的 polygon 。我想存储顶点、半边和邻接列表以添加或删除特定顶点并存储添加和删除操作。

任何帮助或建议的链接？

我是 cgal 的新手，我需要检查两个 Polyhedron_3 的交集，我知道存在一个名为 intersection_Polyhedron_3_Polyhedron_3() 的函数，但我不知道如何实现它。

谁能举例说明如何使用此功能或其他方式检查两个 Polyhedron_3 的交集？

我想列举线性规划的所有基本可行解。我怎么能用纸浆做到这一点？

我已经阅读了 PuLP文档，但不知道如何去做。您的帮助将不胜感激。

假设我们在不考虑其目标函数的情况下对混合整数线性规划有以下公式。即一组

$$X = {(x,y) \in \mathbb{R}^n \times \mathbb{Z}^m \; | \; 斧头 +Bz <= d}$$

（我不知道如何在这里放置乳胶代码......）

还假设约束 Ax + Bz <= d 也可以写成逻辑函数的形式（即满足给定条件时返回 true 的函数）。

现在，我想对集合 X 中的一组点进行采样，只需给出指定的尺寸常数 m 和 n。

我虽然使用蒙特卡洛类型算法的一种方法，但由于它看起来像是一种蛮力并且可能需要很多时间来处理复杂的约束，所以我决定不使用它们。

使用 PYTHON 是否有更好的解决方案？

谢谢 ！

我正在尝试使用 CGAL 4.13 和以下代码片段对多面体的面进行三角测量，该代码片段在标准输入上采用 OFF 格式的多面体定义文件：

但是，我观察到以下警告：

CGAL 警告：检查违规！表达式：false 文件：/usr/include/CGAL/Constrained_triangulation_2.h 行：902 说明：您使用的是精确数字类型，使用 Constrained_triangulation_plus_2 类将避免级联交集计算并且效率更高 此消息仅在没有 CGAL_NO_CDT_2_WARNING 时显示定义。

请参阅https://www.cgal.org/bug_report.html上的错误报告说明

并且三角测量失败。消息Triangulation failed!和多面体定义一样被打印出来，它清楚地显示了一些具有 5 个甚至 7 个顶点的面。

不幸的是，多面体的 OFF 表示为 8070 行，我未能创建一个更小的示例来重现该问题。所以我把它上传到这里。它在那里只能使用 30 天，如果有人可以建议一个更好的上传位置，我会考虑的。

编译后，例如

g++ -O3 tri.cpp -o tri -lCGAL -lgmp -lmpfr -Wall

该问题可以通过

./tri < poly.off

我不确定三角测量的失败是否与警告有关；我怎么能用这个Constrained_triangulation_plus_2类CGAL::Polygon_mesh_processing::triangulate_faces()呢？这可能吗？人脸三角剖分不是什么复杂的事情，这怎么可能一开始就失败呢？

我正在尝试将层转换为存储在 postgis 中的多面体。在这个例子中，我有一个从 0,0,0 到 1,1,1 的立方体，下面的脚本为 postgis 引入了一个几何图形，它就在那里，没问题，但是我去计算体积，它给出了以下错误：

询问：

错误：

对象是一个 0,0,0 到 1,1,1 的立方体，这里它是一个顶点和三角形的数组。

顶点：

三角形定义为：

我把这个转换脚本放在一起，把它添加到 postgis 中：

结果是：

它看起来不错，postgis 接受它作为多面体表面，但我如何确保立方体构造正确？PS和postgis 3D查看器在那里，我在做这个盲人。

假设我在 Blender 中有一个立方体或更复杂的封闭三角对象，我怎么能将它存储在 postgis 中？

Postgis 通过众所周知的文本 (wkt) 将 3D 几何图形存储为多面体或锡。有什么方法可以将搅拌机对象放入 postgis 中？

我想随机生成不需要凸的多面体。这样做最有效的方法是什么？

我可以想到一种生成随机凸多面体的算法，但无法找到生成非凸多面体的方法。如何生成一般多面体？

更进一步，将我的问题推广到 n 维空间，如何随机生成有界有限多面体？