Take the 2-minute tour ×

1) How can I generate a random number in a union of intervals in Python?

I'm aware of the existence of the random package and I know how to use this functions.

2) How can I generalize this problem to the one of finding a circle (x,y,radius) outside the union of a set of non overlapping circles given a vector containing the radius of this circles in a descending order?

This is what I did so far:

import random as rand
import numpy as np
from numpy import *

r = #some irrelevant function or defined vector

[x,y]=[array([],dtype=float) for dummy in range(2)]

for j in xrange(0,len(r)):
    while (q<j-1):
        if ((x[j]-x[q])**2+(y[j]-y[q])**2<=(r[j]+r[q])**2):

But this too slow! I need this to be freakin fast!

share|improve this question
Do you mean inside the union of circles, rather than outside? The latter doesn't seem to have much in common with the interval problem you're asking about in the first part. –  Blckknght Jan 29 '14 at 23:14

2 Answers 2

If you can easily compute the total size of your union of intervals, it's not to hard to then pick a random value from the union. Here's some not very optimized code:

def random_from_intervals(intervals): # intervals is a sequence of start,end tuples
    total_size = sum(end-start for start,end in intevals)
    n = random.uniform(total_size)
    for start, end in intervals:
        if n < end-start:
            return start + n
        n -= end-start

You can do something equivalent to pick a point inside the union of a set of circles. Just weigh each circle by its area (or just radius squared, since units don't matter). Picking a specific point once you've narrowed things down a given circle is a bit tougher, but not insoluble. Here's some code where I cheat a little and generate an extra random number to help select from the points at a given radius from the center:

def random_from_circles(circles): # circles is a sequence of x,y,r tuples
    total_weight = sum(r**2 for x,y,r in circles)
    n = random.uniform(total_weight)
    for x, y, r in circles:
        if n < r**2:
            d = n**0.5
            theta = random.uniform(math.pi*2)
            return x + d * math.cos(theta), y + d * math.sin(theta)
        n -= r**2
share|improve this answer

Generate a random number between 0 and the sum of your intervals, binary search a list of (cumulative sum, interval) pairs. So with the intervals [0, 1), [2, 5), [8, 10) I have a list:

[(1, [0, 1)), (4, [2, 5)), (6, [8, 10))]

6 is the sum of the total space covered, so generate a random number in [0, 6). If the number is, say, 3.5, binary search for 3.5 in our list. It falls immediately to the left of the interval it belongs in.

[(1, [0, 1)), <3.5>, (4, [2, 5)), (6, [8, 10))]

For circles, can you describe what distribution the circles must be drawn from? Otherwise just generate a random circle, the odds that it overlaps with a circle you have are vanishingly small. If you have a distribution, but still very few circles in the total space, then this may be a collision detection problem. Look up quadtrees.

share|improve this answer
Thanks for your answer. This could be a solution for (1) and it might be what I'm looking for. I have a gamma distribution of the radii. And depending on the fraction of space I want to cover with circles I have a certain number of radii. The piece of code I wrote works sufficiently fast for 50% of the space but not for 80 -95%. –  David Jan 30 '14 at 0:26

Your Answer


