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