comp.graphics.algorithms

Subject: Re: General flat-flat intersection

On Sat, 22 Apr 2006 23:49:09 +0300, Kaba wrote:
>Given is an n-flat and an m-flat. A k-flat is represented by a point and
>k linearly independent tangent vectors. The intersection of a n-flat and
>a m-flat is at most a min(n, m)-flat. Give an algorithm to compute the
>intersection flat in the point-tangent form.
>
>Here are some special cases in 3D:
>0-flat and 2-flat: point-plane intersection
>1-flat and 1-flat: ray-ray intersection
>1-flat and 2-flat: ray-plane intersection
>2-flat and 2-flat: plane-plane intersection
>etc..
>
>This is pure curiosity, no practical need involved.

You might want to approach this is through Grassmann coordinates, not
point-vector form. If you're familiar with Pluecker coordinates for
lines, these just extend the same idea.

Use homogeneous coordinates for points and hyperplanes in dimension d.

(x0: x1: ...: xd)
[c0: c1: ...: cd]

These are already Grassmann coordinates (for the point) and dual
Grassmann coordinates (for the hyperplane). The intended meaning for
hyperplane is a d-1 flat.

We can select a k flat with k+1 independent points, or equivalently
(in homogeneous form), with one point and k vectors. Assemble their
coordinates in columns to form a (d+1)x(k+1) matrix. Compute all the
independent (k+1)x(k+1) subdeterminants. That is, choose k+1 rows and
form their determinant. These are the Grassmann coordinates.

For the duals, select a (d-n) flat with n independent hyperplanes. In
similar fashion, assemble a nx(d+1) matrix and compute independent nxn
subdeterminants. Noting n=d-k, either way combinatorics tells us we
have a collection of

(d+1)?(k+1) = (d+1)?(d-k) = (d+1)!/(k+1)!(d-k)!

numbers for the coordinates. In higher dimensions there is increasing
redundancy, but (at least for theory) it may be worth it.

It's a bit messy to notate, but suppose we have a k flat and wish to
extend it with an independent point. Already having a collection of
subdeterminants around makes it relatively easy to express a new,
extended, collection including the new column. This gives us the join
approach.

Likewise, if we have a (d-n) flat and wish to restrict it with an
independent hyperplane, the same idea gives the meet.

This is not quite the same as computing arbitrary intersections, but
is a good step along the way. For more, try Stolfi's dissertation or
Hodge and Pedoe's multivolume book.