Subject: Re: General flat-flat intersection
On Sat, 22 Apr 2006 23:49:09 +0300, Kaba
>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
>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
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.
View All Messages in comp.graphics.algorithms
General flat-flat intersection =>
Re: General flat-flat intersection
Copyright © 2006 WatermarkFactory.com. All Rights Reserved.