Speeding up selecting sets of 3 nodes that form triangles with given min and max side length
Question: I've got a list of about 60 points, from which I'm generating all possible
combinations of size 3. I'm trying to determine whether any of the 3 points
are within certain distance parameters - that is, not too close to each other,
and not too far from each other (say, no point can be less than 10 units to
the next nearest point, and no point can be more than 100 units from the
furthest point).

I've got code to do so here:

    
    
    def setPalmCombinations(self):
        # Testing confirms that the range of distances is about 5 - 10 for
        # minimum distance between points, and anywhere from 150 - 200 for max
        # distance between points. 10 and 100 should be reasonable cutoffs.
        minDistance = 10
        maxDistance = 100
        startTime = time.time()
        iter = itertools.combinations(self.handContour, 3)
        def distanceCheck(points):
            A = points[0][0]
            B = points[1][0]
            C = points[2][0]
            AB = np.linalg.norm(A - B)
            if not(minDistance < AB < maxDistance): return None
            BC = np.linalg.norm(B - C)
            if not(minDistance < BC < maxDistance): return None
            CA = np.linalg.norm(C - A)
            if not(minDistance < CA < maxDistance): return None
            return np.array([A, B, C])
        a = [distanceCheck(i) for i in iter]
        print time.time() - startTime
    

However, just generating this list of possible combinations takes roughly .4
to .5 seconds, which is far too slow. Is there a way I can optimize this
calculation (or fundamentally redo the algorithm so that it's not simply a
brute force search) so that I can get the time down to about a realtime
calculation (that is, 30ish times a second).

I was thinking about possibly generating a list of the distances between every
point, sorting it, and looking for the points with distances toward the center
of the cutoff range, but I think that may actually be slower than what I'm
doing now.

I'm also trying to figure out some more intelligent algorithm given the fact
that the points are originally stored in order of how they define the contour
- I should be able to eliminate some points before and after each point in the
list when making the combinations ... however, when I tried to generate the
combinations using this fact with Python's default for loops, it ended up
being slower than simply using itertools and generating everything.

Any advice is appreciated.

Thanks!


Answer: You can speedup using numpy. Assuming `comb` is your already calculated
possible combinations, you can easily vectorize distance calculations:

    
    
    >>> import numpy as np
    >>> comb = np.array(list(comb))
    >>> dists = comb - np.roll(comb, -1)
    # L2 norm
    >>> dists = dists**2
    

dists will be a `Nx3` array containing `AB` `BC` and `CA` distances
respectively.

Mask it with your conditions:

    
    
    >>> mask = (dists > minDist) & (dists < maxDist)
    

Find rows where all distances satisfy the conditon:

    
    
    >>> rows = np.all(mask, axis=1)
    

return combinations that satisfy conditions:

    
    
    >>> comb[rows]
    

UPDATE: Just noticed that this is still quite slow for large N. Here it is the
function that contains all the above steps:

    
    
    >>> def palm_combinations(points, min_dist=10, max_dist=100): 
            combs = np.array(list(itertools.combinations(points, 3)))
            dists = (combs - np.roll(combs, -1))**2
            mask = (dists > min_dist) & (dists < max_dist)
            return combs[np.all(mask, axis=1)]
    

For a sample data of 100 points:

    
    
    >>> a = np.random.rand(100) * 500
    >>> %timeit palm_combinations(a)
    10 loops, best of 3: 79.5 ms per loop
    

The bottleneck of the function is the generation of all the combinations:

    
    
    >>> %timeit combs = np.array(list(itertools.combinations(a, 3)))
    10 loops, best of 3: 69.2 ms per loop
    

UPDATE 2: It can be speeded-up with a bit more complicated approach. Using
`np.fromiter`:

    
    
    # Define combinations data type (3 float each combination)
    >>> dt = np.dtype('f,f,f')
    # Fast numpy array conversion
    >>> combs = np.fromiter(itertools.combinations(points, 3), dt)
    

The function would be something like:

    
    
    >>> def palm_combinations(points, min_dist=10, max_dist=100): 
            dt = np.dtype('f,f,f')
            combs = np.fromiter(itertools.combinations(points, 3), dt)
            combs = combs.view('f').reshape(-1,3)
            dists = (combs - np.roll(combs, -1))**2
            mask = (dists > min_dist) & (dists < max_dist)
            return combs[np.all(mask, axis=1)]
    

And the speed test:

    
    
    >>> %timeit palm_combinations(a)
    10 loops, best of 3: 29.8 ms per loop
    

For N=100

