🔒 Locked

general formula for hyperplane

Started by AlphaCoder Jul 18, 2009 at 2:43 AM 7 replies 4k views

Original Post

Jul 18, 2009 at 2:43 AM

I'm working on a game in which the amount of spatial dimensions will vary from level to level and in some cases within the level. What is the general formula for the hyper plane described by n-points? I can generate a line based on two points and a plane based on three points and a hyperplane based on four points and a hyper hyper plane based on five points and a hyper hyper hyper plane based on six points and a hyper hyper hyper hyper plane based on seven points and a hyper hyper hyper hyper hyper plane based on eight points and a hyper hyper hyper hyper hyper hyper plane based on nine points. I could easily generate a hyper hyper hyper hyper hyper hyper hyper plane based on ten points. If I wanted to (and this case could certainly arise on the harder levels of my game) I could probably generate a hyper hyper hyper hyper hyper hyper hyper hyper hyper plane based on eleven points. On harder levels I could potentially generate a hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper plane based on twelve points. Also a hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper plane based on thirteen points would be feasible. It's when you get to hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper planes and beyond that I start having trouble. I wouldn't even know where to begin for generating a hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper plane or a hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper plane based on twenty points or forty points. Is there a general formula for generating a hyper * x - plane based on the necessary amount of points in a given dimension? I'm more than a little stumped as to how to go about generating a hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper hyper plane based on eighty seven points. I can visualize the higher dimensions easily. (in fact I'm one of the few people alive who can. only edward witten for sure can as well) My problem is my elementary school geometry teacher only took us up to twelve dimensions when we were working on higher dimensional geometry. Most of the kids cried when we reached thirteen. And that is because thirteen is a horribly unlucky number. As they say, thirteen is unlucky for some.

luca-deltodesco

Jul 18, 2009 at 3:09 AM

This is just an idea, but I see no reason why it wouldn't work.

By expressing the cross product as the matrix determinent

           |i  j  k |a x b = det|ax ay az|           |bx by bz|

You can expand the cross product to higher dimensions like:

              |i  j  k  l |x(a,b,c) = det|ax ay az aw|              |bx by bz bw|              |cx cy cz cw|

which will still give you the same property of the the resultant vector being perpendicular to each of the inputs.

So I would imagine that you could for any number of points in n-dimensions, form a hyperplane by evaluating:

n = x(p1-p0,p2-p0,p3-p0,p4-p0...pn-p0)
d = -n.p0

for the hyperplane n.p + d = 0

apatriarca

Jul 18, 2009 at 8:38 AM

What about a linear interpolation of the points? A line is described by
(1 - t)P + tQ
A plane by
uA + vB + (1 - u - v)C
and so on...

EDIT: Just a little note on terms. hyperplane is a general term and it's used in every dimension. So you say a 6-dimensional hyperplane and not an hyper hyper hyper plane.

[Edited by - apatriarca on July 18, 2009 9:38:42 AM]

swiftcoder

Jul 18, 2009 at 8:48 AM

Quote:
Original post by AlphaCoder
I can visualize the higher dimensions easily. (in fact I'm one of the few people alive who can. only edward witten for sure can as well)

Purely out of curiosity, if no one else can visualise these hyper-planes, then who is going to play your game?

Maze Master

Jul 18, 2009 at 10:08 PM

Along the lines of what apatriarca was saying, the linear subspace spanned by a set of points p1, p2, ... pn is given by the set of all linear combinations of those points. Ie: c1*p1+c2*p2+...+cn*pn for all combinations of numbers c1,...,cn. This is the line/plane/hyperplane/whatever that contains all your points, plus the origin.

For an affine space spanned by your points (line, plane, whatever containing your points but not the origin), you simply translate all your points so that one is at the origin, construct the linear subspace with the remaining ones, and then translate back. Ie: c1*(p2-p1)+c2*(p3-p1)+...+cn*(pn-p1)+p1

But why stop at n dimensions? Everyone knows that if you wanna be a true pimp baller, you have to include hyper-planes in infinite dimensional space in your game. It's all right though, these are the null spaces of continuous linear functionals.

luca-deltodesco

Jul 19, 2009 at 2:17 AM

Not to bash your answers, but isn't a plane defined in a such a way, ultimately useless unless you are only needing to generate points in the plane? Whereas a solution like mine is more akin to standard application, being able to for one; find which side of the plane a point resides, or if it is on the plane, and being able to use it in intersection calculations etc etc.

apatriarca

Jul 19, 2009 at 10:57 AM

Quote:
Original post by Maze Master
Along the lines of what apatriarca was saying, the linear subspace spanned by a set of points p1, p2, ... pn is given by the set of all linear combinations of those points. Ie: c1*p1+c2*p2+...+cn*pn for all combinations of numbers c1,...,cn. This is the line/plane/hyperplane/whatever that contains all your points, plus the origin.

For an affine space spanned by your points (line, plane, whatever containing your points but not the origin), you simply translate all your points so that one is at the origin, construct the linear subspace with the remaining ones, and then translate back. Ie: c1*(p2-p1)+c2*(p3-p1)+...+cn*(pn-p1)+p1

But why stop at n dimensions? Everyone knows that if you wanna be a true pimp baller, you have to include hyper-planes in infinite dimensional space in your game. It's all right though, these are the null spaces of continuous linear functionals.

I should probably clarify what I was saying. An n-dimensional affine sub-space is identified by (n+1) points {P_i}_i=0..n in general position (they shouldn't be part of an (n-1)-dimensional affine space). All the points in this subspace is a linear combination of the those points with the additional condition
c₀ + c₁ + ... + c_n = 1
where c_i is the coefficient of P_i. In fact
c₀P₀ + c₁P₁ + ... + c_nP_n =
= (1 - c₁ - ... - c_n)P₀ + c₁P₁ + ... + c_nP_n =
= P₀ + c₁(P₁ - P₀) + ... + c_n(P_n - P₀)
The locus of the points where the coefficients are all >= 0 is called the convex hull of those points.

@luca-deltodesco: My (and Maze Master) solution have the advantage that works in every ambient space.

[Edited by - apatriarca on July 19, 2009 11:57:22 AM]

Steve132

Jul 20, 2009 at 4:36 AM

I think this way is by far the easiest to code.

http://en.wikipedia.org/wiki/Plane_(geometry)

from wikipedia:

Let p be the vector representing the position of any known point in the plane, and let n be a nonzero normal vector. The desired plane is the set of all points r such that n dot (r-p)=0

to put this another way, a plane in N-d space consists of a set of N-d points r, such that each the line segment connecting p to r is perpendicular to the line segment connecting p to p+n.

so, if all the points in set R are in a plane, each point r will satisfy
n dot (r-p) = 0 for some value of p and n. That means to specify a particular plane from a bunch of r1,r2,r3,r4, you need to solve for p and n.

however, we can see from the formula...
n dot (r-p) == n dot r - n dot p = 0
n dot r = n dot p

n dot r will vary for each value of r, but n dot p will not, so it will be the same global value no matter what...let us arbitrarily assign:

d=-n dot p, t

and now we have the famous equation:

n dot r = -d

to define our plane. This equation holds in ALL dimensions of plane, so we can take advantage of it.

n dot r + d = 0

In 3d space, this looks familiar, its

Nx Rx + Ny Ry + Nz Rz + d = 0

and now, Nx,Ny,Nz,d are the 4 parameters you need to solve for, given multiple vectors R.

Well, it turns out, in 3D space, this is really easy:

Nx R1x + Ny R1y + Nz R1z + d = 0
Nx R2x + Ny R2y + Nz R2z + d = 0
Nx R3x + Ny R3y + Nz R3z + d = 0

which, since we see "hey, linear equations" we should automatically rewrite as a matrix:

| R1x  R1y  R1z  1 |  | Nx |   | 0 || R2x  R2y  R3z  1 |  | Ny | = | 0 || R3x  R3y  R3z  1 |  | Nz |   | 0 |                      |  d |   | 0 |

which is trivial to solve by a bunch of methods,

http://en.wikipedia.org/wiki/Kernel_(matrix)

This method trivially extends to any dimensionality...you just make your matrix of points on the left (you need at least N of them) make one more column filled with 1, then find the Null Space of that vector (also known as solving this Matrix equation for x)
Ax=0,

The best way by far that I am aware of to calculate this is by an svd-based method, which you can do using the Eigen C++ library in one line, or if you want faster there are a bunch of other ways, I leave it up to you.

Coding this up in Eigen:

#include<Eigen/Core>#include<Eigen/SVD>#include<vector>template<int N>Eigen::Matrix<double, N+1,1> solveHyperplane(const std::vector<Eigen::Matrix<double,1,N> >& points){    Eigen::Matrix<double, Eigen::Dynamic, N+1> R(points.size());    for(int i=0;i<points.size();i++)	//create a big matrix    {        R.block<1,N>(i,0)=points;        R.block<1,1>(i,N)=1.0;    }    return R.svd().matrixV().col(N);    //take the SVD, the null-vector is the last column of V }

AlphaCoder

Jul 22, 2009 at 12:40 PM

Quote:
Original post by swiftcoder
Quote:
Original post by AlphaCoder
I can visualize the higher dimensions easily. (in fact I'm one of the few people alive who can. only edward witten for sure can as well)
Purely out of curiosity, if no one else can visualise these hyper-planes, then who is going to play your game?

They should only need to worry about cross sections and a few.. details involved with the dimensions involved. There will be a lot of surprises for them if they aren't visualizing it in its entirety but I'm hoping to make that a core part of gameplay.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.