问题标签 [computational-geometry]

这是一些代码：

从手册：

“边没有显式表示，它们只是通过两个面的邻接关系隐式表示。每条边都有两个隐式表示：与索引为 i 的顶点相对的面 f 的边可以表示为f 的邻居 (i) 的边缘。"

这对我来说很好......但是我如何使用CT::Finite_edges_iterator上面给出的代码中的 a 来获得边缘的末端顶点？

更新： 我设法想出了这个解决方案：

我仍在寻找更好的方法来做到这一点。

我想要一种算法来计算 4 个 2D 点的凸包。我已经查看了通用问题的算法，但我想知道是否有 4 点的简单解决方案。

我正在使用 GPC 将多边形分解为三角形。然而，GPC 在生成三角形时非常明显地创建了额外的顶点。有没有办法避免这种情况？

我有几个 1000 的三角形连接在 2D 网格中。它代表水流。该网格是一个 delaunay 三角剖分。我需要将三角形合并回最少量的简单多边形，这样每个多边形都被限制为没有内部孔。输出多边形应该是相同的形状。

有没有已知的算法来完成这个？

可能重复：查找最大子矩阵算法

我需要帮助解决一个问题。

给定一个在每行MxN中用字母 (az) 表示的板，我必须找到其中只有 2 种字母的最大区域。该区域必须为矩形。这是一个例子：MN

输出将是 6，因为只有 2 种字母的最大矩形区域在上角 AAA-ABB，只有 A 和 B（2 种）。

我使用财富算法找到一组点的 Voronoi 图。我得到的是一个线段列表，但我需要知道哪些线段形成封闭的多边形，并将它们放在一个由它们周围的原始点散列的对象中。

找到这些的最快方法可能是什么？我应该从算法中保存一些关键信息吗？如果是这样呢？

这是我在 Java 中从 C++ 实现移植而来的财富算法实现here

（我知道它不会编译，需要初始化数据结构，并且它缺少导入）

我想要的是这样的：

我能想到的最直接的蛮力方法是创建图中点（边的端点）的无向图，每个点都有一个条目，每个边都有一个连接点（没有重复）然后去查找该图中的所有循环，然后对于共享 3 个或更多点的每组循环，丢弃除最短循环之外的所有循环。但是，这太慢了。

我有一个 3D 表面（想想 xy 平面）。飞机可以倾斜。（想想坡路）。

给定定义表面的 3D 坐标列表（Point3D1X、Point3D1Y、Point3D1Z、Point3D12X、Point3D2Y、Point3D2Z、Point3D3X、Point3D3Y、Point3D3Z等），如何计算表面的面积？

请注意，我的问题类似于在 2D 平面中查找区域。在二维平面中，我们有一个定义多边形的点列表，使用这个点列表我们可以找到多边形的面积。现在假设所有这些点都具有z这样的值，即它们在 3D 中被提升以形成一个表面。我的问题是如何找到那个 3D 表面的面积？

这是一个与此处类似的问题。

给定定义表面的 3D 坐标列表（Point3D1、Point3D2、Point3D3等），如何计算表面的质心？

在 2D 中，计算由以下公式给出：

那么3D模拟呢？

我读过关于 kd-trees 的文章，但是当空间的维度很高时它们效率低下。我有一个值数据库，我想找到查询的某个汉明距离内的值。例如，数据库是一个 32 位数字的列表，我想找到与查询值相差小于 3 位的所有数字。

我在某处听说过 MultiVariate Partition 树，但找不到好的参考。我知道 min-Hash 给出了一个很好的近似值，更好，但我想要一个准确的答案。

我有打包 2 个任意多边形的问题。即我们有2个任意多边形。我们要找到这个多边形的这种位置（我们可以进行旋转和移动），当包围这个多边形的矩形具有最小的面积时。

我知道，这是一个 NP 完全问题。我想选择一种有效的算法来解决这个问题。我正在寻找 No-Fit-Polygon 方法。但是我在任何地方都找不到用于查找两个任意多边形的 NFP 的简单而清晰的算法。