问题标签 [polyhedra]

我有一个 3D 凸多边形。为简单起见，让它成为一个有顶点的正方形，(0,0,0),(1,1,0),(1,1,1),(0,0,1).。我需要按逆时针顺序排列这些顶点。我在这里找到了解决方案。建议确定多边形中心的角度并对其进行排序。我不清楚这将如何工作。有没有人有办法解决吗？我需要一个强大的解决方案，甚至在顶点非常接近时也可以工作。

一个示例 MATLAB 代码将不胜感激！

我想计算随机多边形的面积和随机多面体的体积。谷歌搜索让我找到了曲面细分和蒙特卡洛方法。但是，我只对精确计算感兴趣，而不是通过收敛进行近似。可能有人知道确切的公式，或者有一个链接到描述这些公式的页面？

这些公式不需要应用于奇异的多边形或多面体。如果它们适用于简单的（非相交边）凸形，我已经很满意了。除了顶点坐标列表之外，我不想使用其他任何东西，[(x1, y1), ..., (xn, yn)]或者[(x1, y1, z1), ..., (xn, yn, zn)]可能以特定顺序排列。

我能够阅读Fortran、C/C++和。因此，用任何这些语言编写的或用伪代码编写的算法都受到好评。PythonMATLAB

为了模拟流体中的移动障碍物，我需要计算平行六面体和立方体以及任意多面体和立方体的相交体积。我正在使用 CGAL 库的 Nef_polyhedron。由于我必须在 10.000 个时间步中的每一个中进行大约 90.000 个交集，因此我遇到的主要问题是它太慢了。在我的实现中，90.000 个十字路口需要 20 分钟。

我几乎不可能进行这样的模拟。在一秒钟内，应该可以执行 100 个时间步长。这是cgal的限制，问题还是由于我的编程错误？有人能告诉我它应该有多快，是否有更快（简单）的方法来计算交叉点？

我刚刚开始使用 CGAL 计算沿折线的 minkowski 和 - 基本上是“滑行”操作。这里有一个很好的例子：

http://doc.cgal.org/latest/Minkowski_sum_3/index.html#Minkowski_sum_3Glide

不幸的是，一旦折线的某些点相等，我就会遇到麻烦。例如对于一个封闭的环：

结果是

回溯看起来像这样：

可能，Nef Polyhedra 不允许相交。

有没有办法解决这个问题？非常感谢您的帮助。

我尝试运行此代码以显示 3D 网格输出由于某种奇怪的原因，显示了 nf 和顶点数的输出，但之后它给出了分段错误；Moar 输出行未写入 std。知道为什么吗？

我开始使用 CGAL 演示来寻找两个多面体的交集。当两个多面体共享一些顶点和边时，我遇到了一个问题。该程序带有“分段错误”调用。我认为问题与共享顶点有关，因为对于其他情况，我认为没有问题。我的多面体是例如菱形三面体或截短的三面体（后者是凹面的）。是演示程序的问题还是CGAL算法本身的问题？

输入我使用的 OFF 文件： https ://www.dropbox.com/s/nywdv80yzr0wpxp/henley_3D.off https://www.dropbox.com/s/slxzfwhchpuix2p/henley_shift_3D.off

我在以 Win7 x64 作为主机的 VirtualMachine 下使用 CGAL 和 Ubuntu 10.04。

我将不胜感激您的任何帮助。最好的，拉德克

在可转移效用特征函数博弈（合作博弈论）中，最著名的解决方案概念是博弈的核心，定义为任何联盟都无法改进的可行收益分配的集合。在几何上，核心是一个封闭的凸多面体： http: //www.jstor.org/stable/2630190

在这些游戏中，收益分配要么在核心，要么不在。TUGlab 工具集有一个命令可以计算支付分配是否在核心中： http ://webs.uvigo.es/mmiras/TUGlab/ 但是没有命令可以告诉你确切的一定的收益分配距离是核心。如果核心的几何表征是一个封闭的凸多面体，那么应该有一种方法可以将点与该多面体之间的几何距离计算为特征函数的“到核心的距离”。不幸的是，我没有找到任何论文真正向我展示了我可以在 MATLAB 中实现的计算这个距离的公式或算法。

我的猜测是斯蒂芬卡梅隆的代码中可能有一个计算两个多面体之间距离的线索。但我的问题应该比这更简单：只是一个点和一个多面体之间的距离。最后，我需要一个 MATLAB 程序，将 a) 特征函数和 b) 收益分布作为输入，然后将收益分布与特征函数核心之间的距离作为输出。当然假设核心是非空的。

我目前想知道是否有一种通用算法来检查一组平面多边形，而不是三角形，是否构成一个防水多面体。每个多边形都有一个方向（法线向量）。一个简单的解决方案就是说是或否。更高级的版本是指出多面体“开放”的边缘。我对如何接近多面体并不感兴趣。

我想指出，我的“洞”不一定小，例如，立方体的一个面可能会丢失。因此，“欠采样校正”算法似乎不是正确的方法。此外，我说的是大约 100 - 1000 个，而不是 1000000 个多边形，因此计算时间应该不是问题。

任何提示或提示？

亲切的问候，策展人

假设有n 个3 维对象（多面体）。计算所有对象的交集 O(n ^ 2) 的最快方法是什么？

现在，我正在使用一个基本上强制 T(n) 等于 n ^ 2 的库：

这实际上需要 n ^ 2 个步骤。

我能想到的唯一更快的方法仍然是 O(n ^ 2)，但是 T(n) = n(n+1) / 2，或 (n*n + n) / 2。

这是伪代码：

这样我们就不必检查两个对象是否相交两次。我知道我正在迭代的列表中有大约 3000 个对象。该算法需要 4501500 步，而原始算法需要将近两倍，即 9000000 步。

我错过了什么吗？这是我们能得到的最好的吗？

我有 20 到 30 个随机生成的 3D 点作为定义多面体的顶点。我曾尝试使用DelaunayTri(points)枚举面并使用叉积的行列式来计算和求和四面体体积，但我不确定它是否适用于非凸面的多面体。

另一种可能的方法是将凹多面体划分为凸多面体（通过检测凸包内的点），但这种不相交划分的算法让我望而却步。

另外，如何绘制这样一个凹形船体？