问题标签 [geometry]

我正在寻找一种算法或库（更好）将多边形分解为三角形。我将在 Direct3D 应用程序中使用这些三角形。最好的可用选项是什么？

这是我到目前为止发现的：

1. 本迪斯科的笔记
2. FIST：多边形的快速工业强度三角剖分
3. 我知道CGAL提供三角测量，但不确定它是否支持孔。

我真的很感谢在这方面有经验的人的一些意见。

编辑：这是一个二维多边形。

这是此处发布的问题的延续： Finding the center of mass on a 2D bitmap讨论了在布尔矩阵中查找质心，如给出的示例。

假设现在我们将矩阵展开为这种形式：

如您所见，我们现在有 4 个质心，用于 4 个不同的集群。

鉴于只有一个质心存在，我们已经知道如何找到质心，如果我们在这个矩阵上运行该算法，我们将在矩阵中间得到一些点，这对我们没有帮助。

什么是找到这些质量簇的好、正确和快速的算法？

.NET 框架以执行几何计算的类的方式提供什么（如果有的话）？例如，计算两点之间的距离（表示为 (x,y)）或求解直角三角形的未知边或内角？（我知道这两个都很容易解决；我只是以这些为例）。

如果没有内置任何内容，是否有人知道任何可能有用的开源或第三方库？

在给定指定宽度的情况下，从大约 5,00 个坐标中找到位于点路径内的坐标集的最佳方法是什么。例如，一架飞机跟随几个航路点。

有没有一种好方法可以按照与路线相同的顺序对它们进行排序。

计算速度比准确性更重要，因为我正在考虑生成建议列表。

从我所看到的来看，我认为这并不简单，而且问题有点宽泛，但欢迎任何建议/指针，例如：

1. 存储纬度/经度或使用球坐标的最佳方式
2. 在坐标集中有额外的聚类信息
3. 可以使用某种转换来简化范围检查
4. 订购积分的最佳方式是什么

这里是比对路径上的几个等距点进行圆形/方形检查更好的方法吗？

给定两个具有整数坐标的二维二次贝塞尔曲线，找到它们的交点的最佳方法是什么？同样有趣的是，如果它们不相交，则提前拒绝。如果它更容易，可以假设它们在 x 和 y 中都是单调的。只有可以通过细分输入曲线的整数表示的交点才有效。

假设二维空间中的一系列点不自相交，那么确定所得多边形面积的有效方法是什么？

作为旁注，这不是家庭作业，我不是在寻找代码。我正在寻找可以用来实现我自己的方法的描述。我有关于从点列表中拉出一系列三角形的想法，但我知道有很多关于凸多边形和凹多边形的边缘情况，我可能无法捕捉到。

给定一组点s （一组 x,y 坐标）和一条由连接一组点l的线段组成的路径，描述一种有效的算法，该算法可用于从s中找到点的子集，它们是在路径l的指定距离d内。

这方面的一个实际应用可能是沿着城市之间的公路旅行路径在 10 英里范围内的任何地方查找餐馆列表。

例如，在下图中，绿色点将包含在搜索结果中。

解决方案在 C# 中是首选，但基于 SQL 的方法可能会获得奖励积分 :-)

从手册页XFillPolygon：

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

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

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

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

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

处理 2D 构造区域几何的最佳工具/库（任何语言）是什么？

也就是说，一个库使用或多或少的任意二维形状并提供联合、交集、差异和异或。

我的基线是java.awt.geom.Area类，如果速度慢的话也可以使用。外面有什么更好的？我特别感兴趣的是 Java、ActionScript/Flex 和 C 库，但我对任何人都开放。

如果你有一个 center(center_x, center_y)和 radius的圆radius，你如何测试一个给定的坐标点(x, y)是否在圆内？