0

I'm looking for an algorithm to test if an N-dimensional object (defined by the convex hull of N+1 vertices) and an M-dimensional object (defined by the convex hull of M+1 vertices) intersect within L-dimensional space (where L is greater than or equal to both N and M). Ignore degenerate cases.

For example, it could test if a line segment and a triangle intersect in 3D space, and it could also test if two 4D objects intersect in 4D space.

I have been researching and thinking about this problem for a while, and have not found the answer yet, though it seems possible. So far my approach is to define the objects parametrically, and then check the system of equations for a solution.

Here is what I have so far: Object 1 has N dimensions, is defined by N+1 vertices, and exists in L dimensional space. Vertex 1 is the "origin" O1. N vectors V1 through Vn are defined by the difference of O1 and each of the other N vertices. N scalar parameters P1 through Pn are paired with the N vectors. So now every point in object 1 is defined by: O1 + sum(Pi*Vi, i = 1:N) such that "Pi >= 0" AND "sum(Pi, i = 1:N) <= 1". We have a similar definition for Object 2, with M+1 vertices also in L dimensional space, with vectors W1 through Wm, and scalars Q1 through Qm. This provides a system of L*(N+M) equations and L+N+M unknowns. Now my strategy is to reduce the system and test to see if there is a solution such that: "Pi >= 0" AND "sum(Pi, i = 1:N) <= 1" AND "Qi >= 0" AND "sum(Qi, i = 1:N) <= 1".

Any thoughts on how to proceed? I'm hoping that someone has done this already, and I won't have to re-invent the wheel.

Thomas Hamilton
  • 1
  • Do you really mean $L\geq max(M,N)$ or should it be $\leq$? – rschwieb Feb 20 '13 at 20:09
  • The space in which the objects are defined must have at least as many dimensions as the object with the highest number of dimensions.

    For instance, I'm not interested in a 3D object defined in 2D space (I don't think that's possible, is it?)

     – Thomas Hamilton Feb 21 '13 at 09:00
  • Ah, I guess maybe this notion of dimension is not the one I am thinking of. Most notions of dimension are monotonic in the sense that if $A\subseteq B$, the dimension of $A$ should be lower than that of $B$. However in this case, maybe the intersection of two shapes might have "more corners" than the intersecting objects. – rschwieb Feb 21 '13 at 14:40
  • Then, I think what I really mean is N⊆L AND M⊆L.

    I'm not really interested in the geometry of the intersecting region, just whether an intersection exists.

    Now, my thinking is to reduce the system of parametric equations to the smallest independent set and then find the dimensions of the intersecting region. I'm thinking that, if the dimensions of the intersecting region is equal to the dimensions of the lower-dimensional object, then the intersection exists (i'm also not interested in intersections with "edges")

     – Thomas Hamilton Feb 21 '13 at 18:17
  • Oh, OK I see you mean "intersect in L" to mean that L contains them both, rather than "L is the intersection". Thanks for clarifying. – rschwieb Feb 21 '13 at 18:57
  • What are your objects exactly? The convex hull of your set of vertices? – Tara B Feb 22 '13 at 19:09
  • They are always objects with the minimum number of points needed to span the dimensions that they have. For instance, in 3D space, any object defined with 4 points is always a tetrahedron, and any object with 3 points is always a triangle. I think that this implies that all objects are convex, but I could be wrong. So, in short, I think the answer to your question is yes, Tara B. Oh, and ignore degenerate cases. – Thomas Hamilton Feb 25 '13 at 09:29

1 Answers1

0

Ok, I have an answer, though I'm sure there is a simpler way. It turns out my intuition was correct, please read the original question for the details. I actually found the intersecting regions in general. When the region has a non-empty set of vertices, the objects intersect.

The solution:

Two geometric objects (S1 and S2) are given by two sets of vertices (S1 has N vertices, and S2 has M vertices) in L dimensional space (each vertex has L components). The objects are the convex hulls of their vertices, with N-1 and M-1 dimensions. For each, a point is chosen as an origin, and the remaining points are subtracted from this point in its respective set to create the basis vectors of two (in general) non-orthonormal frames, U and V.

We now have from two objects S1 and S2, with N and M vertices: origin O1 and N-1 basis vectors U to define a frame attached to S1, and origin O2 and M-1 basis vectors V to define a frame attached to S2. For each object, let there be a set of unknown scalars defined: X1 with N-1 scalars, and X2 with M-1 scalars. Then, a point in S1 can be defined by multiplying the scalars in X1 by their respective vectors in the basis U, and adding this to O1, with the constraints that all scalars in X1 are >=0, and their sum is <=1. Likewise for S2. S1 and S2 intersect if the system of L equations with M+N-2 unknown scalars in X1 and X2 has a solution.

A unique solution only exists if L = M+N-2 (as in the case of a line segment and a triangle that are not parallel), which is a single point defined in both bases. This is not generally true. We must also make sure the constraints on the unknown scalars are satisfied. Now I just plugged in the constraints as equations to fill the deficit in equations to solve the system. There are N+M constraints in total, but only L-(M+N-2) are needed to solve the system. Then the solution is iterated for every unique combination of N+M constraints taken L-(M+N-2) at a time.

This is equivalent to finding the set of vertices of the object formed by the intersection of S1 and S2 (with some possibly repeating). The set is empty if and only if S1 and S2 do not intersect. Note: There is another effect. Since S1 and S2 are convex, their intersection is convex. Then this algorithm has found the intersecting region in general, which is the convex hull of the output set of vertices.

I only wanted to know if they intersect, not solve for the intersecting region. I still wonder if there is a quicker way to find just the answer that I'm looking for.

Thomas Hamilton
  • 1