问题标签 [computational-geometry]

我正在使用http://www.compgeom.com/~piyush/scripts/triangle/中的 triangle++ 包装类来对点云进行三角测量，以便使用 OpenGL 进行可视化。我能够输入我的观点并计算三角测量。之后，我还能够通过顶点迭代器访问顶点，它在包中包含的 main.cpp 示例中是如何显示的。现在我想通过面迭代器访问顶点（main.cpp 中还有一个示例）。我想遍历所有面并获得每个面的三个顶点。有人已经这样做了吗？我一直在尝试修改包装类约 2 天，但没有成功。

提前非常感谢！塞巴斯蒂安

给定一组数据点，在它们之上创建一个kdtree，但是这个 kdtree 是唯一的吗？

如何测试一条线是否有一个位于三角形内（而不是边缘）的点。（全部为 2D）。

目前我想我会这样做：

• 将直线和三角形的每一边定义为 Ax+By+C=0，并有一个 xrange。
• 检查这条线是否与三角形的任何一条线相交。
• 如果是，请检查它是否不在行尾。

有一个更好的方法吗？

完成 2D 三角剖分后，一些三角形具有相同的颜色，我想重新组合它们以绘制类似颜色的图形路径。我发现如果我只是一个一个地绘制三角形，一些图形渲染器会显示三角形之间的接缝（至少在涉及抗锯齿和/或透明度的情况下）。

那么如何获取一组（非重叠）三角形并生成可能包含孔和不相交多边形的图形路径？

盲目地将三角形添加到图形路径实际上非常适合填充（当然不是用于描边），但是导出那些额外的内部点感觉不合适。

我目前正在尝试构建设备在运行期间覆盖的区域。此过程的第一步似乎是构建覆盖区域的多边形。由于图案不是标准形状，凸包通过跳到可能的最大覆盖区域夸大了覆盖区域。

我发现一篇论文似乎涵盖了非凸包生成的概念，但没有讨论如何在高级语言中实现这一点。 http://www.geosensor.net/papers/duckham08.PR.pdf

有没有人见过用于构造非凸壳或凹壳的直接算法，或者可能有任何 python 代码来实现相同的结果？

我尝试了主要是 qhull 的凸包，边缘大小有限，成功率有限。我还注意到一些无法分发的许可库，所以不幸的是，这不在讨论范围内。有更好的想法或食谱吗？

我正在开发一个应用程序，其中实体位于地球上的位置。我想要一组数据，我可以从中确定一个点包含在哪些区域中。

区域可能是以下类型：

• 大陆
• 国家
• 湖
• 海
• 非军事区
• 沙漠
• 冰架

……等等。

我设想将每个区域表示为一个多边形。对于任何给定的点，我会测试它是否包含在每个多边形中。非常欢迎替代想法。

我也希望找到包含部分或全部这些边界的公共领域数据集。

其中一些多边形将非常详细（可能比我需要的更详细），因此我需要有效执行这些计算的技巧。我期望简化 2D 多边形的方法也会很有用。这类事情的最佳实践是什么？

任何人都可以推荐这些数据的任何好的资源、任何特定的编程方法或现有的软件库来做这种事情吗？

编辑

我应该指出，区域的数据集将是相当静态的，因此如果可以提高性能，预计算是一个不错的选择。

我有一个 3D 多边形网格和一个相应的 2D 多边形网格（实际上来自UV 贴图），用于将几何图形映射到 2D 平面上。给定平面上的一个点，我如何有效地找到它所在的多边形，以便将该 2D 点映射回 3D？

我能想到的最好方法是将多边形存储在 2D 区间树中，并使用它来获取候选多边形。有没有更简单的方法？

澄清一下，这不适用于着色器。我实际上是在进行 2D 物理模拟并将其渲染为围绕 3D 网格。为了绘制每个对象，我需要弄清楚 3D 中的哪个点对应于它的真实 2D 位置。*

大多数迭代算法需要一个初始的空三角形来让球滚动。似乎一个常用的技巧就是使超三角形与点集相比非常大。

但根据“数值配方：科学计算的艺术”：

“......如果距离只是有限的（到边界点），则构造的三角剖分可能不是非常德劳内。例如，在不寻常的情况下，它的外边界可能会略微凹入，具有直径数量级的小负角“真实”点集除以到“虚构”（边界）点的距离。

那么有哪些选项可以用无穷远处的点来增加笛卡尔坐标，而不必将所有输入转换为不同的坐标系，例如齐次坐标？这些点如何与通常的几何谓词 CCW 和 Incircle 相匹配？

Incircle (a,b,c) Infinity -> False。假设 a,b,c 是有限的。

但是当 a,b,c 之一是无穷远点时呢？圆变成半平面然后测试变成逆时针检查吗？如果外接圆上有 2 个或更多点是无限的怎么办？圆圈是否扩展成一个完整的平面，导致测试始终为真？CCW呢？您如何根据在无穷远处有一个或多个点的线对点进行分类？

目前，我正在开展一个项目，该项目试图通过将连通性指定为最小欧几里德距离来对数据集中的 3d 点进行分组。我现在的算法只是简单的对原始洪水填充的 3d 改编。

再次为新种子运行此代码片段，_img.queryRadius() 是使用 ANN 库的固定半径搜索：

我对这段代码的问题是它运行 waaaaaaaaaaaaaaaay 对于大型数据集来说太慢了。如果我没记错的话，这段代码将对每一个点进行搜索，搜索时间为 O(NlogN)，时间复杂度为 (N^2*log(N))。

除此之外，如果我从 KD 树中记得，删除相对昂贵，而且不删除点也会产生问题，因为每个点都可以被靠近它的每个邻居搜索数百次。

所以我的问题是，有没有更好的方法来做到这一点？特别是随着数据集线性增长的方式？

感谢您提供的任何帮助

编辑 我曾尝试使用像 dash-tom-bang 所说的简单排序列表，但结果甚至比我以前使用的要慢。我不确定它是否是实现，或者它只是太慢了，无法遍历每个点并检查欧几里得距离（即使只使用平方距离。

人们可能还有其他想法吗？我现在真的很难过。

我想找到具有百万个顶点的两个多边形之间的最小距离（而不是它们顶点之间的最小距离）。我必须找到第一个形状的每个顶点与另一个形状的所有顶点之间的最短距离的最小值。类似于Hausdorff Distance，但我需要最小值而不是最大值。