如何在不规则多边形的内部获得随机点？
我有一组描述不规则多边形区域边界的点：
int [] x = { /*...*/ }; int [] y = { /*...*/ }; 如何从该多边形的内部统一选择一个随机点？
我会分三步完成：
-
创建一个三角形列表，覆盖与给定多边形相同的区域。 如果您的多边形是凸的，则更容易，因为您可以让所有三角形共享一个公共顶点。 如果不保证多边形是凸的，那么你必须找到更好的多边形三角剖分技术。 这是维基百科的相关文章 。
-
随机选择要使用的三角形，按其面积加权。 因此，如果三角形A是面积的75％而三角形B是面积的25％，则应该在75％的时间选择三角形A，并且选择B 25％。 这意味着找到每个三角形占据的总面积的分数，并将其存储在列表中。 然后从0 – 1生成随机双数（Math.random（）执行此操作），并减去列表中的每个值，直到下一个减法使其为负。 这将随机选择一个三角形，并考虑面积权重。
-
随机选择所选三角形内的一个点。 您可以使用此公式： 三角形中的随机点样本 。
或者，您可以选择覆盖整个多边形的矩形（例如其边界框）并随机选择该矩形内的点。 然后检查该点是否在多边形内部，如果不是，则生成一个新的随机点并再次尝试，并根据需要重复。 从理论上讲，这可能需要永远，但实际上最多需要四到五次尝试。
您仍然需要一个算法来确定该点是否在多边形内部。 如果你已经将它分解为三角形，这更容易，只需检查它是否在任何一个中。
如果你打算用java做这个，你真的应该有一个点的类，而不是使用并行数组。 此外，虽然技术上允许使用下划线作为名称的首字母，但这不是最佳做法; 如果您使用它来表示它们仅供内部使用，则将它们声明为private或protected或您需要的任何内容。
import java.awt.Point; import java.awt.Shape; import java.awt.Rectangle; /** * This method uniformly selects a random point contained in the shape * supplied to it. * @param region The region to select from. * @returns A random point contained in the shape. */ Point generatePoint(Shape region){ Rectangle r = region.getBounds(); double x, y; do { x = r.getX() + r.getWidth() * Math.random(); y = r.getY() + r.getHeight() * Math.random(); } while(!region.contains(x,y)) return new Point.Double(x,y); }
这样做，弯曲边界的处理也很容易。 如果需要，您甚至可以将其传递到非连续区域。 从点生成形状也很容易; 我建议为此目的使用Path2D 。
如果不需要double精度，只需用float替换它（您还必须将Point.Double更改为Point.Float并将Math.random()转换为float ）。
对此的一个问题是，如果该区域非常稀疏，因为它只包含其边界框的很小一部分，那么性能可能会受到影响。 如果这成为一个问题，您将需要使用更高级的方法，包括网格化多边形和选择网格单元格。 此外，如果该区域完全为空，则该方法将永远不会返回。 如果需要保护这些问题，那么我建议更改它，以便在放弃和返回null之前只会进行一些数字（从几十到几千）的尝试。
要从点生成形状对象，您可以执行以下操作：
import java.awt.geom.Path2D; //[...] Path2D path = new Path2D.Double(); path.moveto(_x[0], _y[0]); for(int idx = 1; idx < _x.length; idx++) path.lineto(_x[idx], _y[idx]); path.closePath();
如果只需要积分点，那么就这样做随机生成：
import java.awt.Point; import java.awt.Shape; import java.awt.Rectangle; /** * This method uniformly selects a random integral point contained in the * shape supplied to it. * @param region The region to select from. * @returns A random point contained in the shape. */ Point generateIntegralPoint(Shape region){ Rectangle r = region.getBounds(); int x, y; Random rand = new Random(); do { x = r.getX() + rand.nextInt( (int) r.getWidth() ); y = r.getY() + rand.nextInt( (int) r.getHeight() ); } while(!region.contains(x,y)) return new Point(x,y); }
或者，如果您感兴趣的形状相当小，则可以遍历边界框中的所有积分点，将有效的形状添加到列表中，然后从列表中进行选择。
import java.awt.Point; import java.awt.Shape; import java.awt.Rectangle; /** * This method uniformly selects a random integral point contained in the * shape supplied to it. * @param region The region to select from. * @returns A random point contained in the shape, or {@code} null if the * shape does not contain any integral points. */ Point generateIntegralPoint(Shape region){ Rectangle r = region.getBounds(); Random rand = new Random(); ArrayList list = new ArrayList<>(); for(int x = (int) r.getX(); x <= (int) (r.getX() + r.getWidth()); x++) for(int y = (int) r.getY(); y <= (int) (r.getY() + r.getHeight()); y++) if(region.contains(x,y)) list.add(new Point.Float(x,y)); if(list.isEmpty()) return null; return list.get(rand.nextInt(list.size())); }