Does anyone know of a generalized intersection test?

I'm looking for an algorithm to test if an N-dimensional object and an M-dimensional object both defined within L-dimensional space intersect.

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

[Thomas Hamilton]

No attempts yet. Is the question too hard?

[Thomas Hamilton]

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" O. N vectors V1 through Vn are defined from the "origin" 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: O + sum(Pi*Vi) with i = 1 to N, P1 through Pn are all >= 0, and sum(Pi) <= 1 with i = 1 to N.

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 P1 through Pn are all >= 0, sum(Pi) <= 1, Q1 through Qn are all >= 0, and sum(Qi) <= 1. Any thoughts on how to proceed?

[Sean de Wolski]

A meta FYI: a question asked on Saturday when many of us are not working will fall off the front page or two and will never be seen. I recommend posting a comment or an edit sometime on a Monday to ensure maximum visibility.

Answer 1

[Sean de Wolski]

There are lots of 2d/3d versions of this on the FEX:

FEX:query:intersect

However, there doesn't seem to be anything for this in n-d and I don't know if some these algorithms extend to n-dimensions or not. I do seem to remember John having a utility that did something like this, though it might just be the distance to curve one.