Sample Random Points Over Intersection Of Surfaces

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 interse

Solution 1:

If there are arbitrary circles, there is no way to avoid checking in-or-out

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).

UPDATE

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

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

defsquared(x):
    return x*x

classDisk(object):
    def__init__(self, x, y, r):
        self._x = x
        self._y = y
        self._r = r

    defcheck(self, x, y):
        return squared(x-self._x) + squared(y-self._y) <= squared(self._r)

classNode(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 = Nonedefis_leaf_node(self):
        """
        True if node  has no children
        """if self._NE isNone:
            if self._NW isNone:
                if self._SW isNone:
                    if self._SE isNone:
                        returnTruereturnFalsedefcheck_point(self, x, y):
        """
        True if not covered by circle
        """if self._disk isNone: 
            returnTruereturnnot self._disk.check(x, y)

defcheck_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)

    iflen(rc) == 0:
        returnNonereturn rc

defbuild(node, disks):
     subdisks = check_node(node, disks)
     if subdisks isNone: # empty type of leaf node
         node._disk = Nonereturn node
     iflen(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

defcheck_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: # NEreturn check_point(node._NE, x, y)

        return check_point(node._SE, x, y)

    # SW or NW
    y > node._dy: # NWreturn 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)