javascript - 使用彼此相邻堆叠的多边形包围多个单独的点集

Question

我正在处理坐标点(区域中的许多点)(x，y)或(lat，lon)的数据集，这些点属于多个类别。我想做的是从据我所知被称为凹或非凸的那些点获取区域的多边形，而且这些多边形必须彼此相邻，它们之间没有间隙。

这些是初始点(示例)

这是我想要的大概结果

现实生活中的例子是欧洲地缘政治 map ，如果您拥有所有国家/地区的所有地址，并且想要以多边形形式获取每个国家/地区的面积并最终得到 map 。

我遇到了许多与从点集中获取多边形相关的问题，但无法在我的场景中使用它。如果您需要更多信息，请告诉我。感谢您的帮助。

Answer 1

您可以使用Voronoi tesselation输入空间的。不过，你拥有的不是点，而是点集。基本上，您获取空间中的每个点，然后查看距离它最近的点。然后它获得与该点相同的“类”。为了获得更平滑的输出，您可以查看 N 个最近点中的 k 个多数。这意味着使用位图图像而不是 2D 坐标，但您会得到一些可行的东西。然后，您可以使用更简单的图像处理技巧(边缘检测、二进制集操作等来获取边缘，然后可能将它们叠加在图像上)。

作为替代方案，您可以对每个数据集运行凸包算法，然后尝试修复重叠区域。