You*_*sef 4 c# math point polygon
我正在寻找一种算法来生成多边形内均匀分布的点.
这是场景:
我有一个由每个点的角(x,y)处的点坐标指定的多边形.我有多边形内生成的点数.
例如,假设我有一个包含5个点的多边形:(1,1); (1,2); (2,3); (3,2); 和(3,1)
我需要在该多边形内生成20个相等的距离点.
注意:某些多边形可能不支持均匀分布的点,但我希望以尽可能多的一致性覆盖多边形的所有区域的方式分布点.(我的意思是我不希望分数比另一分数多得多)
有算法吗？或者是图书馆
我正在开发一个C#应用程序,但是任何语言都可以,因为我只需要算法,我可以翻译它.
非常感谢您的帮助
小智 10
我使用的简单方法是:
三角形多边形.耳朵剪裁是完全足够的,因为你需要的是将多边形解剖成一组非重叠的三角形.
计算每个三角形的面积.每个三角形的样本与该三角形相对于整体的面积成比例.每个样本只需要一个统一的随机数.
一旦确定一个点来自给定的三角形,则在三角形上均匀地采样.这本身比你想象的要容易.
所以这一切都取决于你如何在三角形内进行采样.这很容易做到.三角形由3个顶点定义.我叫他们P1,P2,P3.
选择三角形的任何边缘.生成沿该边缘均匀分布的点(P4).因此,如果P1和P2是相应端点的坐标,那么如果r在区间[0,1]上具有均匀分布,则P将是沿该边缘的均匀采样点.
P4 =(1-r)*P1 + r*P2
接下来,沿P3和P4之间的线段进行采样,但不均匀地进行采样.如果s是区间[0,1]上的均匀随机数,那么
P5 =(1-sqrt(s))*P3 + sqrt(s)*P4
r和s当然是独立的伪随机数.然后P5将被随机采样,在三角形上均匀.
好处是它不需要实施拒绝方案,所以长而薄的多边形不是问题.对于每个样本,成本仅需要为每个事件生成三个随机数.由于耳朵剪辑相当简单并且是一项有效的任务,因此即使对于看起来很难看的多边形或非凸多边形,采样也是有效的.