面の交差点上のサンプルランダム点

Question

複雑なサーフェスの交差点からランダムな2次元数値を一様にサンプリングする最も効率的な方法は何でしょうか？

たとえば、多くのディスクの交差や多数のディスクの結合の補完を考えてみましょう。

2次元の関心領域を含むボックスからポイントを描き、希望の条件が満たされているかどうかを確認することができますが、ランダムなポイントを直接均一に描画する効率のよいソリューションがあるかどうかは疑問です区切られた表面から！

おかげ

Answer 1

任意の円がある場合は、チェックを回避する方法はありませんで、またはアウト

各ノードが固定されていますQuadtreeを、構築されるだろう、このようなチェックをスピードアップするための良い方法（1つか0がベストかもしれない）チェックするための円へのポインタ。

ツリー検索（線形変換）は、1つの循環チェック（およびここでは受け入れまたは拒否）または循環チェックなし（無条件で受け入れる）でノードに移動します。

更新

いくつかの簡単な実装。しかし、空間データ検索（QuadTreeページの下部にあるリンクを参照）の については、QuadTrees、R-treesなどのツリーの詳細についてはこちらをご覧ください。

いくつかのサンプルコードUNTESTEDでは、指定されたディスクのリストを再帰的に構築し、ポイント到着時に再帰的にツリーを歩き、ポイントを分類します。 ツリーウォーキングは、ここではいくつかの暗黙の前提がありますO（LOG2（N））の複雑さ、そして最後に、最大1枚のディスクチェック

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)