c# - 在多边形中生成均匀分布点的算法

Question

我正在寻找一种算法来在多边形内生成均匀分布的点。

场景如下:

我有一个多边形，由每个点的角点 (x, y) 的坐标指定。我有在多边形内生成的点数。

例如，假设我有一个包含 5 个点的多边形:(1, 1) ; (1, 2) ; (2, 3) ; (3, 2) ;和 (3, 1)

我需要在该多边形内生成 20 个等距点。

注意:有些多边形可能不支持均匀分布的点，但我希望以尽可能一致的方式分布点，以覆盖多边形的所有区域。 (我的意思是我不想要比另一个有更多分数的部分)

是否有算法可以做到这一点？或者图书馆

我正在开发 C# 应用程序，但任何语言都可以，因为我只需要算法并且我可以翻译它。

非常感谢您的帮助

Answer 1

我使用的简单方法是:

1. 对多边形进行三角测量。剪耳就足够了，因为您只需将多边形分解成一组不重叠的三角形。

2. 计算每个三角形的面积。从每个三角形中抽取与该三角形相对于整体的面积成比例的样本。每个样本只需要一个统一的随机数。

3. 一旦确定某个点来自给定的三角形，就在该三角形上均匀采样。这本身比您想象的要容易。

所以实际上这一切都归结为您如何在三角形内采样。这很容易完成。三角形由 3 个顶点定义。我将它们称为 P1、P2、P3。

1. 选取三角形的任意一条边。生成沿该边均匀分布的点 (P4)。因此，如果P1和P2是相应端点的坐标，则如果r在区间[0,1]上均匀分布，则P将是沿该边缘的均匀采样点。

   P4 = (1-r)*P1 + r*P2

2. 接下来，沿 P3 和 P4 之间的线段进行采样，但采样不均匀。若s是区间[0,1]上的均匀随机数，则

   P5 = (1-sqrt(s))*P3 + sqrt(s)*P4

r 和 s 当然是独立的伪随机数。然后P5将被随机采样，在三角形上均匀分布。

好处是它不需要实现拒绝方案，所以细长的多边形不是问题。而对于每个样本，成本仅在于每个事件需要生成三个随机数。由于耳朵剪裁非常简单并且是一项高效的任务，因此采样将是高效的，即使对于看起来令人讨厌的多边形或非凸多边形也是如此。