如何获得不规则多边形内部的随机点？

Question

我有一组描述不规则多边形区域边界的点：

int [] x = { /*...*/ };
int [] y = { /*...*/ };

如何从多边形内部均匀选择一个随机点？

Answer 1

我将分三个步骤进行操作：

1. 创建一个三角形列表，这些列表覆盖与给定的多边形相同的区域。如果多边形是凸面的，则比较容易，因为您可以让所有三角形共享一个共同的顶点。如果不能保证多边形是凸的，则必须找到更好的多边形三角剖分技术。这是相关的维基百科文章。

2. 随机选择要使用的三角形，并按其面积加权。因此，如果三角形A是面积的75％，而三角形B是面积的25％，则应该选择75％的时间选择三角形A，25％的时间选择B。这意味着找到每个三角形占总面积的比例，并将其存储在列表中。然后从0到1生成一个随机双数（Math.random（）这样做），并减去列表中的每个值，直到下一个减法将其变为负数为止。这将随机选择一个考虑了面积权重的三角形。

3. 在所选三角形内随机选择一个点。您可以使用以下公式：对三角形中的随机点进行采样。

或者，您可以选择一个覆盖整个多边形的矩形（例如其边界框），然后随机选择该矩形内的一个点。然后检查该点是否在多边形内，如果不是，则生成一个新的随机点，然后重试，并根据需要重复。从理论上讲，这可能要花很长时间，但实际上最多只能进行四到五次尝试。

但是，您仍然需要一种算法来确定该点是否在多边形内。如果您已经将其分解为三角形，则更容易，只需检查它是否在其中任何一个中即可。