聚类可以帮助我在多边形中均匀分布点吗

Question

你好，这是一个更笼统的问题。我正在编写将提供空中交通预测可视化的程序。我有一个由几个 GPS x、y 坐标组成的多边形，我还有该多边形中的点数据集，它看起来像这样。

我现在的任务是在该多边形中生成新点，但这些新点将以一种均匀分布的方式，我的意思是我希望在该多边形的那些空白区域中生成那些新点。这是我的想法的图片。新点表示为蓝点。

有人告诉我这个任务应该通过聚类来完成，我了解了聚类对数据集的作用以及它的工作原理。但是我无法将其应用于我的问题，我只是无法将其包裹在我的头上。所以我的问题是：这是否可以通过聚类、k-means 或 DBSCAN 或其他方法来实现？我已经尝试了一些基本的东西，但我做不到，所以我只是想问问一般情况下我是否可以通过集群来做到这一点，或者我是否应该为此使用其他一些功能。

Answer 1

三角化你的多边形。你展示的是凸面的，但任何简单的多边形都可以三角化。在每个三角形内生成均匀分布的点，调整区域的密度。这提供了一个均匀的分布 多边形内的随机点。

有一个更简单的算法，但速度较慢。为您的多边形找到一个边界框。在框内生成均匀分布的点，以及 丢弃多边形外的点。 （为此你需要多边形中的点，它在网络上随处可见。） 例如，这个链接。这基本上是@wwii 的评论。

Answer 2

以下技术从头开始实施起来有点困难，但可以确保每个后续生成的点都占据（大致）最大的空白区域的中心，从而使点在多边形上完全平衡地分布。

1. 计算Largest Empty Circle (LEC) 以设置障碍物几何形状，它最初包括多边形的边缘和初始点集。
2. 将生成的 LEC 的中心点添加到障碍物集中。
3. 为更新的障碍集重新计算 LEC。
4. 根据需要重复步骤 2-3 多次以获得所需的额外点数。

对于下图，我使用的是 JTS

LargestEmptyCircle

(Java) 实现。