[comp.graphics] How to determine 4 points in a 3D plane??

) (10/24/90)

Hi Netters..

  I am looking for the algorithm (pseudocode is fine) to determine any 4 given
abitrary points p(x,y,z) that lie in the same plane...e.g. The algorithm should
work for the following points ..

	a)	p1=[1,1,0]
		p2=[0,2,1]
		p3=[1,0,2]
		p4=[3,-1,2]

	b)	p1=[4, 2, 1]
		p2=[0, -3, 4]
		p3=[2, 0, 3]
		p4=[1, 4, 1]

  Thanks in advance for you help..
							si

jroth@allvax.enet.dec.com (Jim Roth) (10/25/90)

In article <31644@netnews.upenn.edu>, sichen@grasp.cis.upenn.edu (the S T R A N G E R ???!!!) writes...

>  I am looking for the algorithm (pseudocode is fine) to determine any 4 given
>abitrary points p(x,y,z) that lie in the same plane...e.g. The algorithm should
>work for the following points ..

>	a)	p1=[1,1,0] p2=[0,2,1] p3=[1,0,2] p4=[3,-1,2]

>	b)	p1=[4, 2, 1] p2=[0, -3, 4] p3=[2, 0, 3] p4=[1, 4, 1]

It's unclear what you want - in both of your cases, the points aren't coplanar.

If you need a predicate that tests if points lie on a plane or not, try
evaluating the determinant

	| x1 y1 z1 1 |
	| x2 y2 z2 1 |
	| x3 y3 z3 1 |
	| x4 y4 z4 1 |

This is zero, or nearly so, if the points lie on the same plane.  In fact,
it is 6 times the volume of a tetrahedron with the given 4 vertices (in
homogenous coordinates.)

- Jim

levine@well.sf.ca.us (Ron Levine) (10/30/90)

In article <31644@netnews.upenn.edu>, sichen@grasp.cis.upenn.edu (the S T R A N G E R ???!!!) writes:
> 
>   I am looking for the algorithm (pseudocode is fine) to determine any 4 given
> abitrary points p(x,y,z) that lie in the same plane...e.g. The algorithm should
> work for the following points ..
> 
> 	a)	p1=[1,1,0]
> 		p2=[0,2,1]
> 		p3=[1,0,2]
> 		p4=[3,-1,2]
> 
> 	b)	p1=[4, 2, 1]
> 		p2=[0, -3, 4]
> 		p3=[2, 0, 3]
> 		p4=[1, 4, 1]


Form the 3 vectors v1 = p1 - p4, v2 = p2 - p4, and v3 = p3 - p4.

Then the four points are coplanar if and only if the "box 
product"  v1 dot ( v2 cross v3 ) = 0.

Another way of expressing the same formula is that the 
determinant
                | v1x v1y v1z |
                | v2x v2y v2z | = 0
                | v3x v3y v3z |

If you don't understand "dot", "cross", or "determinant", see any 
book on elementary vector algebra.  

Applying this test shows that neither of the point sets a) nor b) 
is coplanar.

        --Ron