在曲面的交叉点上采样随机点 [英] Sample random points over intersection of surfaces
问题描述
在 python 中，从复杂的曲面交集均匀采样随机二维数的最有效方法是什么?
What would be the most efficient way, in python, to uniformly sample random two-dimensional numbers from a complicated intersection of surfaces ?
例如，考虑多个磁盘的交集或多个磁盘的并集.
For instance, consider the intersection of many disks or the complementary of the union of many disks.
我知道我可以简单地从包含感兴趣的二维区域的框中绘制点，然后检查是否满足所需的条件，但我想知道是否有更有效的解决方案来直接从划界的表面！
I know I could simply draw points from a box containing the two-dimensional zone of interest and then check if the desired conditions are satisfied, but I'm wondering if there is a much efficient solution to draw uniformly random points directly from the delimited surface !
谢谢
推荐答案
如果有任意圆，没有办法避免检入检出
If there are arbitrary circles, there is no way to avoid checking in-or-out
加速此类检查的好方法是构建 四叉树，其中每个节点都将有固定的(最好是 1 或 0)指向圆的指针来检查.
The good way to speed up such check would be building Quadtree, where each node will have fixed (one or zero would be the best) pointers to circle to check against.
树搜索(线性变换)将使您通过一次循环检查(在这里您接受或拒绝)或不进行循环检查(无条件接受)到达节点.
Tree search (linear transformation) will get you to the node with one circular check (and here you accept or reject) or no circular check (accept unconditionally).
更新
一些简单的实现.但是您可能会阅读更多有关用于空间数据搜索的四叉树、R 树和类似树的信息(请参阅四叉树页面底部的链接)，因为这个想法的变体可能会帮助你构建更好的算法
Some simple implementation. But you might read more about QuadTrees, R-trees and similar trees for spatial data search (see links at the bottom of QuadTree page), because variations of this idea might help you build better algorithms
一些示例代码，输入 UNTESTED，递归地构建给定磁盘列表的四叉树，然后在到达点递归地遍历树并分类点.树遍历是 O(log2(N)) 复杂度，最后最多一次磁盘检查
Some sample code, typed UNTESTED, recursively builds quadtree given list of disks, then at point arrival recursively walks the tree and classify point. Tree walking is O(log2(N)) complexity, and at the end maximum one disk check
def squared(x):
return x*x
class Disk(object):
def __init__(self, x, y, r):
self._x = x
self._y = y
self._r = r
def check(self, x, y):
return squared(x-self._x) + squared(y-self._y) <= squared(self._r)
class Node(object):
def __init__(self, llx, lly, urx, ury):
# nodes, in CCW
self._NE = None
self._NW = None
self._SW = None
self._SE = None
# corners
self._llx = llx
self._lly = lly
self._urx = urx
self._ury = ury
# dividers
self._dx = 0.5*(llx + urx)
self._dy = 0.5*(lly + ury)
# disk to check
self._disk = None
def is_leaf_node(self):
"""
True if node has no children
"""
if self._NE is None:
if self._NW is None:
if self._SW is None:
if self._SE is None:
return True
return False
def check_point(self, x, y):
"""
True if not covered by circle
"""
if self._disk is None:
return True
return not self._disk.check(x, y)
def check_node(node, disks):
"""
return sublist of disks which affects the node
"""
rc = []
for disk in disks:
if disk.check(node._llx, node._lly):
rc.append(disk)
elif disk.check(node._llx, node._ury):
rc.append(disk)
elif disk.check(node._urx, node._lly):
rc.append(disk)
elif disk.check(node._urx, node._ury):
rc.append(disk)
if len(rc) == 0:
return None
return rc
def build(node, disks):
subdisks = check_node(node, disks)
if subdisks is None: # empty type of leaf node
node._disk = None
return node
if len(subdisks) == 1: # simple circle leaf node
node._disk = subdisks
return node
node._NE = build(Node(self._dx, self._dy, self._urx, self._ury), disks)
node._NW = build(Node(self._llx, self._dy, self._dx, self._ury), disks)
node._SW = build(Node(self._llx, self._lly, self._dx, self._dy), disks)
node._SE = build(Node(self._dx, self._lly, self._urx, self._dy), disks)
return node
def check_point(node, x, y):
if node.is_leaf_node():
return node.check_point(x, y)
if x > node._dx: # SE of NE nodes
y > node._dy: # NE
return check_point(node._NE, x, y)
return check_point(node._SE, x, y)
# SW or NW
y > node._dy: # NW
return check_point(node._NW, x, y)
return check_point(node._SW, x, y)
# main
# in the (0,0):(1,1) square
root = build( Node(0.0, 0.0, 1.0, 1.0), disks )
rc = check_point(root, x, y)
这篇关于在曲面的交叉点上采样随机点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
