如何得到一个不规则多边形内部的任意点？
我有一组描述不规则多边形区域边界的点：
int [] x = { /*...*/ };
int [] y = { /*...*/ };如何从这个多边形的内部均匀地选择一个随机点？
回答 2
Stack Overflow用户
发布于 2013-10-21 03:45:15
我将通过三个步骤完成此操作：
- 创建一个三角形列表，这些三角形覆盖与给定多边形相同的区域。如果您的多边形是凸的，这会更容易，因为您可以让所有三角形共享一个公共顶点。如果您的多边形不能保证是凸的，那么您必须找到更好的多边形三角剖分技术。下面是相关的Wikipedia article.
- Randomly，选择要使用的三角形，按面积加权。因此，如果三角形A占面积的75%，三角形B占面积的25%，则应在75%的时间内选择三角形A，在25%的时间内选择B。这意味着找到每个三角形所占总面积的一部分，并将其存储在列表中。然后从0到1生成一个随机的双精度数(Math.random()执行此操作)，并减去列表中的每个值，直到下一次减法使其为负数。这将使用面积权重considered.
- Randomly在所选三角形内选取一个点来随机选取一个三角形。您可以使用此公式：sample random point in triangle.
或者，您可以拾取一个覆盖整个多边形(如其边界框)的矩形，然后随机拾取该矩形内的一个点。然后检查该点是否在多边形内，如果不在，则生成一个新的随机点并重试，根据需要重复。从理论上讲，这可能永远需要时间，但在实践中，它最多需要四到五次尝试。
不过，您仍然需要一个算法来确定该点是否在多边形内部。如果你已经将它分解成三角形，这会更容易，只需检查它是否在其中任何一个中。
Stack Overflow用户
发布于 2013-10-21 05:13:04
如果你打算用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之前只进行一些尝试(从几十次到几千次)。
要从这些点生成shape对象，可以执行如下操作：
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<Point> 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()));
}https://stackoverflow.com/questions/19481514
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号