Created 2007-01-19 Modified 2007-01-21
Chelton Evans
Convex Shape Intersection
This is a linear time algorithm to determine if two convex shapes intersect. If shape A has M points and shape B has N points this is O(M+N) in time.
The convex shapes are ordered in the sense that given a point on the convex shape its neighboring points can be found. For 2D this is trivial but higher dimensions require surface transversal which is 1 dimension less than the space that the convex object is in.
Choose a point p in B. Iterate over half spaces in A until either a half space that sees p is found or no half spaces in A see the point p. O(M) in time.
Case no half space hi sees p. Either B is inside A or A and B intersect. Repeat the algorithm swapping A and B. O(N) in time. If again no point p in B is found in A then A and B intersect and the algorithm terminates (without saying where the intersection occurred). With total time O(M+N).
General case where the point p is seen. Then either A is inside B or A and B intersect.
Iterate around the half spaces in A following the points in B. The half spaces must be neighbors or very near each other. The point in B is also a state and saved, when the next half space is iterated to one of B's neighboring points will see it if it is visible, else and intersection occurs.
This operation is O(M+N) in time because finding the next point from a neighboring half space is constant in time.
Case A is inside B.
Case A and B intersect. Then not all the points in B are visible to A.
