**comp.graphics.algorithms**

## 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

>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.

Reply

View All Messages in

**comp.graphics.algorithms**

path:

General flat-flat intersection =>

Replies:

Re: General flat-flat intersection

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.