问题标签 [computational-geometry]

我有两个点（一条线段）和一个矩形。我想知道如何计算线段是否与矩形相交。

我确实在高性能集群上从事理论化学工作，通常涉及分子动力学模拟。我的工作解决的问题之一涉及 N 维（通常 N = 2-5）超​​球体的静态场，测试粒子可能会与之发生碰撞。我正在寻找优化（阅读：大修）用于表示球体领域的数据结构，以便我可以进行快速碰撞检测。目前，我使用一个简单的指针数组，指向一个 N 成员结构（中心的每个坐标双精度）和一个最近邻列表。我听说过八叉树和四叉树，但还没有清楚地解释它们是如何工作的，如何有效地实现它们，或者如何使用它们进行快速碰撞检测。考虑到我模拟的大小，内存（几乎）不是对象，但循环是。

我正在开发一个游戏，我创建了一张随机的省份地图（风险或外交）。为了创建该地图，我首先生成一系列半随机点，然后计算这些点的 Delaunay 三角剖分。

完成后，我现在正在寻找创建点的 Voronoi 图，作为省边界的起点。我此时的数据（不是双关语）由原始的一系列点和 Delaunay 三角形的集合组成。

我在网上看到了很多方法来做到这一点，但其中大多数都与 Delaunay 的派生方式有关。我很想找到一些不需要集成到 Delaunay，但可以仅根据数据工作的东西。如果做不到这一点，我正在寻找相对几何新手可以理解的东西，而不是最佳速度。谢谢！

我正在寻找几何算法的任何好的资源；

像两条线交叉等简单的东西很容易（而且很容易找到），但我想找到一些算法来解决更棘手的事情，例如找到通过将给定多边形扩展一定量而形成的形状; 具有弯曲侧面等的形状的快速算法。

有什么好的建议吗？谢谢！

我在搜索将凹多边形分解为最少数量的凸组件的算法时找到了计算几何算法库。网站外的链接和大量的谷歌结果表明它有 python 绑定，这真的很方便，但是所有的链接都死了！这是怎么回事？我现在在哪里可以得到它？

从手册页XFillPolygon：

• 如果shape是Complex，路径可能会自相交。请注意，路径中的连续重合点不会被视为自相交。

• 如果shape是Convex，则对于多边形内的每一对点，连接它们的线段不会与路径相交。如果客户端知道，指定Convex可以提高性能。如果为非凸路径指定凸路径，则图形结果未定义。

• 如果shape是Nonconvex，则路径不会自相交，但形状不是完全凸的。如果客户知道，指定Nonconvex而不是Complex可能会提高性能。如果为自相交路径指定Nonconvex，则图形结果未定义。

我在填充方面遇到了性能问题XFillPolygon，正如手册页所建议的，我要采取的第一步是指定多边形的正确形状。为了安全起见，我目前正在使用Complex 。

是否有一种有效的算法来确定多边形（由一系列坐标定义）是凸的、非凸的还是复杂的？

如何计算三角形（指定为三个 (X,Y) 对）和圆 (X,Y,R) 之间的相交面积？我做了一些搜索无济于事。这是为了工作，不是为了学校。:)

在 C# 中它看起来像这样：

我正在寻找一种简单的（如果存在）算法来找到球体表面上一组点的 Voronoi 图。源代码会很棒。我是一个德尔福人（是的，我知道......），但我也吃 C 代码。

我试图弄清楚有哪些算法可以从 3D 范围数据进行表面重建。乍一看，Ball pivoting algorithm ( BPA ) 和Poisson 曲面重建似乎是更成熟的方法？

• 除了 BPA 和泊松曲面重建算法，该领域还有哪些成熟的、更稳健的算法？
• 推荐的研究出版物？
• 有可用的源代码吗？

我想确定一个多边形并实现一个算法来检查一个点是在多边形内部还是外部。

有谁知道是否有任何类似算法的示例可用？