Search code examples
matlabintersectionconvex-hull

How to check if two convex hulls have intersection in Matlab?

Say I have two convex hulls like this.

C=convhull(x1, y1); 
D=convhull(x2, y2);

where x1,y1,x2,y2 are vectors.

Now I can plot these two convex hulls, but how can I know if these two convex hulls have intersection? I want it in a program, not visually, since I plan to use this in another .m file.

Note: This is all in matlab.

Solution

  • Probably the simplest way, although not necessarily the most efficient, is to use inpolygon. 

    C=convhull(x1, y1); 
D=convhull(x2, y2);

xC = x1(C); yC = y1(C);
xD = x2(D); yD = y2(D);
CinD = inpolygon(xC, yC, xD, yD);
DinC = inpolygon(xD, yD, xC, yC);

    If you're just looking for a binary yes/no answer as to whether the two polygons intersect,

    CDintersect = any(CinD) || any(DinC);

    If you need the actual points, CinD contains the indices for xC,yC and DinC contains the indices for xD,yD.

    While this doesn't require any toolboxes, it does require checking all of the points on both convex hulls, although you can shortcut that if CinD contains any points and you're just looking for a yes/no answer.