一种简单的方法是：
我正在寻找一种算法来在多边形内部生成均匀分布的点。
这里是场景：
我有一个多边形，该多边形由每个点在角（x，y）处的点的坐标指定。而且我有在多边形内部生成的点数。
例如，假设我有一个包含5个点的多边形：（1，1）; （1，2）; （2，3）; （3，2）;和（3，1）
而且我需要在该多边形内生成20个等距点。
注意：某些多边形可能不支持均匀分布的点，但是我希望以一种尽可能覆盖所有区域的方式来分布点。 （我的意思是我不希望一个零件的零件比另一个零件多得多）]
是否有算法可以做到这一点？或图书馆
我正在使用C＃应用程序，但是任何语言都可以，因为我只需要算法并且可以翻译它。
非常感谢您的帮助
我使用的简单方法是：
对多边形进行三角剖分。修剪耳朵就足够了，因为您所需要的只是将多边形分解成一组不重叠的三角形。
计算每个三角形的面积。从每个三角形采样，并与该三角形相对于整个区域的面积成比例。每个样本仅花费一个统一的随机数。
一旦确定一个点来自给定的三角形，则在该三角形上均匀采样。这本身比您想象的要容易。
所以实际上，一切都取决于您如何在三角形内进行采样。这很容易做到。一个三角形由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）* P3 + sqrt（P ** 4）>
r和s当然是独立的伪随机数。然后将随机采样P5，均匀地分布在三角形上。
很好的是，它不需要任何拒绝方案即可实施，因此，长而细的多边形不是问题。对于每个样本，代价只是每个事件需要生成三个随机数。由于修剪耳朵很简单并且是一项高效的任务，因此即使对于看起来讨厌的多边形或非凸多边形，采样也将非常有效。
一种简单的方法是：
此方法会产生一定数量的浪费点。对于三角形，它永远不会超过50％。对于任意多边形，它可以任意高，因此您需要查看它是否适合您。
对于任意多边形，您可以先将多边形分解为三角形，以使您可以保证浪费点的上限：50％。
对于等距的点，从空间填充曲线生成点（并丢弃不在多边形中的所有点）。>>
简单的答案来自一个更简单的问题：如何从均匀分布中生成一定数量的随机分布点，这些点都将适合给定多边形？
简单的答案是这样的：找到多边形的边界框（假设它是[a，b] x [c，d]），然后继续生成实数对，其中一个对是U（a，b），另一个是从U（b，c）开始，直到您拥有适合多边形内部的n个坐标对。这很容易编程，但是，如果您的多边形非常锯齿，或者又细又歪，则非常浪费且缓慢。
为了得到更好的答案，找到最小的旋转矩形边界框，并在变换后的坐标中进行上述操作。
您可以为此使用力向图...看http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)它绝对会给你扔骨头。
我从没尝试过，但我谨记可以在图中为某些顶点设置一个修复]
您的算法最终会像
将图形缩放到]的有界框>
尽管不是绝对的，因为某些凸形可能会产生更奇怪的结果（以星号表示）
最后：没看过，但标题和摘要似乎很相关看看Consistent Graph Layout for Weighted Graphs
希望这有帮助...
更好的答案来自更好的问题。假设您要放置一组n个watch望塔以覆盖一个多边形。您可能会认为这是一个优化问题：找到n个点的2n坐标，这将最小化适合您目标的成本函数（或最大化值函数）。一个可能的成本函数可以为每个点计算到其最近邻点或多边形边界的距离，以较小者为准，并计算此序列的方差作为“非均匀性”的度量。您可以使用如上所述获得的n个点的随机集合作为初始解决方案。
我在某些书中看到过这样的“ watch望塔问题”。算法，演算或优化。
@@ Youssef：对延迟表示抱歉；一位朋友来了，网络中断了。
@@其他人：有耐心，别那么高兴。
一种简单的方法是：
简单的答案来自一个更简单的问题：如何从均匀分布中生成一定数量的随机分布点，这些点都将适合给定多边形？
简单的答案是这样的：找到多边形的边界框（假设它是[a，b] x [c，d]），然后继续生成实数对，其中一个对是U（a，b），另一个是从U（b，c）开始，直到您拥有适合多边形内部的n个坐标对。这很容易编程，但是，如果您的多边形非常锯齿，或者又细又歪，则非常浪费且缓慢。
更好的答案来自更好的问题。假设您要放置一组n个watch望塔以覆盖一个多边形。您可能会认为这是一个优化问题：找到n个点的2n坐标，这将最小化适合您目标的成本函数（或最大化值函数）。一个可能的成本函数可以为每个点计算到其最近邻点或多边形边界的距离，以较小者为准，并计算此序列的方差作为“非均匀性”的度量。您可以使用如上所述获得的n个点的随机集合作为初始解决方案。
我在某些书中看到过这样的“ watch望塔问题”。算法，演算或优化。
@@ Youssef：对延迟表示抱歉；一位朋友来了，网络中断了。