均匀地在矩形区域内生成一个随机点(一些矩形可能重叠)
均匀地在矩形区域内生成一个随机点(一些矩形可能重叠)
提问于 2018-04-04 07:46:49
假设它被赋予了一组不同区域的矩形，并且一些矩形可能重叠。目标是在矩形区域之间生成一个均匀的随机点。
矩形被定义为一对两点：
- (x1，y1) -左下角；
- (x2，y2) --右上角。
我关于不重叠矩形中随机点均匀分布的策略是，-基于区域(existing solution)随机选择一个矩形：
for(int i = 0; i < rectangles.length; i++) {
int area = (rectangles[i].x2 - rectangles[i].x1) *
(rectangles[i].y1 - rectangles[i].y2);
if(rand.nextInt(total + area) >= total) {
selected = i;
break;
}
total += area;
}然后在矩形内生成任意点：
- x1 +(1/(x2-x1))*rand(0，(x2-x1-1))
- y1 +(1/(y2-y1))*rand(0，(y2-y1-1))。
但是，如果一些矩形可以重叠的话，该怎么办呢？
回答 2
Stack Overflow用户
发布于 2018-04-04 20:50:36
如果第一个预处理步骤足够快的话，这里有一个简单且非常快速的解决方案(假设矩形是整数坐标，小于……)( 1000)：
squares = set()
for rect in rects:
for oneByOneSquare in rect:
squares.add(oneByOneSquare)
squares = list(squares)
while True:
randomSquare = random.choice(squares)
randomPoint = randomPointInsideSquare(randomSquare)这样做的目的是将矩形分割成正方形。然后随机选择正方形，然后随机生成该方格内的一个点。
Stack Overflow用户
发布于 2018-04-05 04:32:37
一个工业级的解决方案是
- 将所有矩形合并成正交多边形。这些多边形不重叠。
- 将第一步得到的多边形分解成不重叠的矩形。
- 在这些不重叠的矩形中均匀选择你的点。
这种方法适用于任何可能重叠多边形的输入，如果您用任何类型的三角剖分(比如梯形分解，然后是三角剖分)替换第二步，然后从最后一组三角形中选择点。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/49655323
复制相关文章
相似问题
腾讯云开发者
