在曲面交集上隨機抽樣的點示例

Question

在python中，從複雜曲面交集中均勻抽樣隨機二維數字的最有效方法是什麼？

例如，考慮多個磁盤或多個磁盤結合的補充。

我知道我可以簡單地從包含二維感興趣區域的框中抽取點，然後檢查是否滿足所需的條件，但是我想知道是否有一個非常有效的方法來直接繪製均勻的隨機點從劃界的表面開始！

感謝

Answer 1

如果有任意的圈子裏，沒有辦法避免檢查或出局

的好辦法，以加快此類檢查將被建設Quadtree，其中每個節點都會有固定的（一個或零將是最好的）圈出來檢查的指針。

樹搜索（線性轉換）將使您通過一個循環檢查（在這裏接受或拒絕）或無循環檢查（無條件接受）將您帶到節點。

UPDATE

一些簡單的實現。但你可能會閱讀更多關於四叉樹，R樹和類似樹木的空間數據搜索（見四叉樹頁面底部的鏈接）， 因爲這種想法的變化可能會幫助您構建更好的算法

一些示例代碼，輸入UNTESTED，遞歸地建立四叉樹給定的磁盤列表，然後在點到達時遞歸地走樹和分類點。 樹走路是O（LOG 2（N））的複雜性，並在最後一個最大的磁盤檢查

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)