问题标签 [computational-geometry]

我正在实施 Voronoi 图以直观地找出地图中最近的位置。现在我只想在画布中使用整数坐标 (x,y) 来做到这一点。

问题是 - 我对这个算法真的很困惑。我读了计算几何书，关于财富算法的更多理论。我现在真的很困惑。当我要进行编码时，这对我来说似乎很复杂。

请建议我非常简单地实现 voronoi 图（具有给定坐标）。请建议我使用简单的 java 或 python 或方案代码，最好不要使用哈希、多线程、Delaunay Traingulation、花哨的颜色等。

在没有多线程或哈希映射的情况下，是否可以使用 Fortune 算法实现 Voronoi 图？

我正在编写一个需要实现中轴提取的程序，其中 Delaunay 三角剖分是其中的一个步骤。外部中轴是不需要的，因此打算移除相应的外部三角形。幸运的是，我找到了一个有很多图表的页面，也提示了确定内部和外部德劳内三角形的方法（“基于折线周长”），但这只是一个提示，没有详细解释。有人知道算法吗？

编辑：我忘了提到初始点是从封闭多边形的边界采样的，我的目的是确定每个德劳内三角形是否在多边形内。

我的任务是弄清楚如何找到多边形的中心线。我的谷歌搜索让我相信我需要的是所谓的“中间轴”。像这样：

_{（来源：kiev.ua）}

根据我所阅读的内容，可以通过使用 2D Voronoi 图构造算法来生成我需要的内容。

我在 codeplex (FortuneVoronoi) 上找到了 Voronoi 算法的 C# 版本，在将我的多边形应用到它之后，我得到了这个：

替代文字 http://www.carbonatlas.com/geonotes/gaia_voronoi.png

绿色是原始多边形。橙色是 Voronoi 顶点，黑色线条是 voronoi 边缘。

我可以在这些顶点中看到我需要的东西，但我不确定下一步需要过滤掉所有我不需要的东西。

我很感激你能提供的任何帮助。

我将如何“膨胀”多边形？也就是说，我想做类似的事情：

要求是新的（膨胀的）多边形的边缘/点与旧的（原始）多边形的距离相同（在示例图片上它们不是，因为那时它必须使用弧来膨胀顶点，但是让我们暂时忘记这一点；））。

我正在寻找的数学术语实际上是向内/向外多边形偏移。+1 balint 指出这一点。另一种命名是多边形缓冲。

我的搜索结果：

以下是一些链接：

• 多边形偏移策略综述
• 多边形偏移，问题
• 缓冲多边形数据

我有一个与此非常相似的问题：

如何知道一条线是否与C#中的平面相交？

我正在寻找一种方法（在 C# 中）来判断一条线是否与任意多边形相交。

我认为Chris Marasti-Georg 的算法非常有帮助，但缺少最重要的方法，即线对线交叉。

有谁知道完成 Chris Marasti-Georg 代码的线交叉方法或有类似的方法？

在 C# 中是否有内置代码？

此方法适用于使用禁区功能增强的 Bing 地图算法。生成的路径不得穿过禁区（任意多边形）。

有一个点列表，我如何找到它们是否按顺时针顺序排列？

例如：

会说它是逆时针（或逆时针，对某些人来说）。

我有一些凸多边形存储为点的 STL 向量（或多或少）。我想非常快速地对它们进行镶嵌，最好是尺寸相当均匀的碎片，并且没有“条子”。

我打算用它把一些物体炸成小块。有谁知道一个很好的库来细分多边形（将它们划分为较小的凸多边形或三角形的网格）？

我已经查看了一些我已经在网上找到的，但我什至无法编译它们。这些学术类型并没有过多考虑易用性。

我需要一个库来处理项目中的计算几何，尤其是布尔运算，但几乎每个功能都是有用的。我能找到的最好的库是CGAL，但这是我在没有垃圾收集的情况下会犹豫的那种项目。

您可以推荐哪些语言/库对？到目前为止，我最好的选择是将 CGAL 导入 D。还有一个为 CGAL 制作 Python 绑定的项目，但它非常不完整。

我想解决在线编程竞赛中的几何问题。但每当我读到它们时，我都觉得太难了。请推荐一些我可以研究计算几何的书籍和资源。

给定平面上的一组点，找出其中任意两个点形成的最短线段。

我怎样才能做到这一点？简单的方法显然是计算每个距离，但我需要另一种算法来比较。