determining whether two convex hulls overlap

Question

I'm trying to find an efficient algorithm for determining whether two convex hulls intersect or not. The hulls consist of data points in N-dimensional space, where N is 3 up to 10 or so. One elegant algorithm was suggested here using linprog from scipy, but you have to loop over all points in one hull, and it turns out the algorithm is very slow for low dimensions (I tried it and so did one of the respondents). It seems to me the algorithm could be generalized to answer the question I am posting here, and I found what I think is a solution here. The authors say that the general linear programming problem takes the form Ax + tp >= 1, where the A matrix contains the points of both hulls, t is some constant >= 0, and p = [1,1,1,1...1] (it's equivalent to finding a solution to Ax > 0 for some x). As I am new to linprog() it isn't clear to me whether it can handle problems of this form. If A_ub is defined as on page 1 of the paper, then what is b_ub?

score 1 · Answer 1 · answered Feb 17 '20 at 19:16

There is a nice explanation of how to do this problem, with an algorithm in R, on this website. My original post referred to the scipy.optimize.linprog library, but this proved to be insufficiently robust. I found that the SCS algorithm in the cvxpy library worked very nicely, and based on this I came up with the following python code:

import numpy as np
import cvxpy as cvxpy

# Determine feasibility of Ax <= b
# cloud1 and cloud2 should be numpy.ndarrays
def clouds_overlap(cloud1, cloud2):
    # build the A matrix
    cloud12 = np.vstack((-cloud1, cloud2))
    vec_ones = np.r_[np.ones((len(cloud1),1)), -np.ones((len(cloud2),1))]
    A = np.r_['1', cloud12, vec_ones]

    # make b vector
    ntot = len(cloud1) + len(cloud2)
    b = -np.ones(ntot)

    # define the x variable and the equation to be solved
    x = cvxpy.Variable(A.shape[1])
    constraints = [A*x <= b]

    # since we're only determining feasibility there is no minimization
    # so just set the objective function to a constant
    obj = cvxpy.Minimize(0)

    # SCS was the most accurate/robust of the non-commercial solvers
    # for my application
    problem = cvxpy.Problem(obj, constraints)
    problem.solve(solver=cvxpy.SCS)

    # Any 'inaccurate' status indicates ambiguity, so you can
    # return True or False as you please
    if problem.status == 'infeasible' or problem.status.endswith('inaccurate'):
        return True
    else:
        return False

cube = np.array([[1,1,1],[1,1,-1],[1,-1,1],[1,-1,-1],[-1,1,1],[-1,1,-1],[-1,-1,1],[-1,-1,-1]])
inside = np.array([[0.49,0.0,0.0]])
outside = np.array([[1.01,0,0]])

print("Clouds overlap?", clouds_overlap(cube, inside))
print("Clouds overlap?", clouds_overlap(cube, outside))

# Clouds overlap? True
# Clouds overlap? False

The area of numerical instability is when the two clouds just touch, or are arbitrarily close to touching such that it isn't possible to definitively say whether they overlap or not. That is one of the cases where you will see this algorithm report an 'inaccurate' status. In my code I chose to consider such cases overlapping, but since it is ambiguous you can decide for yourself what to do.

determining whether two convex hulls overlap

1 Answers1