我有一个简单多边形列表（假设有 600 个）（即没有自相交），至少有 4 个点，最多有 3000 个点 我想在 GPU 上计算所有这些多边形的凸包。 Mekman 的凸包算法是运行时间为 O(n) 的简单多边形的流行选择。然而，该算法不是并行的。当然，我可以使用每个输入多边形的一个线程并行计算所有多边形的凸包。但我正在寻找每个多边形平行的东西。 在文献中，我没有找到任何合适的东西。大多数论文都将任意点云作为输入，其中过滤步骤在 GPU 上并行完成。过滤的结果是一个简单的多边形，用作 Melkman 算法的输入。 但由于我已经从一个简单的多边形开始，我需要凸包，所以这没有帮助。
有简单多边形的平行凸包算法吗？
在文献中，我没有找到任何合适的东西。大多数论文都处理任意点云作为输入，
这几乎可以肯定是因为一组多边形的凸包是这些多边形的所有顶点的集合的凸包。
因此，您可以忽略各个顶点的多边形成员资格，而只对所有顶点的集合进行统一并行化（假设您可以使用它）。
当然，正如评论者所建议的那样 - 您使用的算法绝对应该取决于您对数据的了解，即使与我上面写的内容相矛盾。例如，假设您知道所有多边形相对于整体凸包都很小。好吧，在这种情况下，您可以首先将每个多边形视为单个点（选择第一个点），计算这些多边形的凸包，然后丢弃距该包边缘足够远的多边形。