6 pts roughly coplanar
Wihem Kherrati
Does anyone know a simple and Quick test to determine if 6 points are roughly
coplanar ?
thanks.
w.
Dave Lorenz
A very simple test would be a linear regression using the x-, y-, and z-coordinates.
Say, model z = mx + ny + b. Use the standard error of the estimate to determine the if
the points are roughly coplanar.
--
Dave Lorenz (lor...@nwq1dmnspl.cr.usgs.gov)
U.S. Geological Survey
2280 Woodale Drive
Mounds View, MN 55112
Joseph O'Rourke
Dave Lorenz <lor...@srvrdmnspl.cr.usgs.GOV> wrote:
>In article <30ghbe$l...@sophia.inria.fr>, wkh...@fafner.inria.fr (Wihem Kherrati) writes:
>>
>> Does anyone know a simple and Quick test to determine if 6 points are roughly
>> coplanar ?
>
Another method would be to compute the volume of the tetrahedra determined
by four of your six points. This volume is zero if the points are
coplanar. You could compute all 6-choose-4 volumes.
Here is code for the volume, taken from p.140 of my text cited below.
/*-------------------------------------------------------------------------
Volume6 returns six times the volume of the tetrahedron determined by f
and p. Volume6 is positive iff p is on the negative side of f,
where the positive side is determined by the rh-rule. So the volume
is positive if the ccw normal to f points outside the tetrahedron.
--------------------------------------------------------------------------*/
int Volume6( tFace f, tVertex p )
{
int vol;
int ax, ay, az, bx, by, bz, cx, cy, cz, dx, dy, dz;
ax = f->vertex[0]->v[X];
ay = f->vertex[0]->v[Y];
az = f->vertex[0]->v[Z];
bx = f->vertex[1]->v[X];
by = f->vertex[1]->v[Y];
bz = f->vertex[1]->v[Z];
cx = f->vertex[2]->v[X];
cy = f->vertex[2]->v[Y];
cz = f->vertex[2]->v[Z];
dx = p->v[X];
dy = p->v[Y];
dz = p->v[Z];
vol = -az * by * cx + ay * bz * cx + az * bx * cy - ax * bz * cy
- ay * bx * cz + ax * by * cz + az * by * dx - ay * bz * dx
- az * cy * dx + bz * cy * dx + ay * cz * dx - by * cz * dx
- az * bx * dy + ax * bz * dy + az * cx * dy - bz * cx * dy
- ax * cz * dy + bx * cz * dy + ay * bx * dz - ax * by * dz
- ay * cx * dz + by * cx * dz + ax * cy * dz - bx * cy * dz;
return vol;
}
@book{o-cgc-94
, author = "Joseph O'Rourke"
, title = "Computational Geometry in {C}"
, publisher = "Cambridge University Press"
, year = 1994
, note = "ISBN 0-521-44592-2/Pb \$24.95,
ISBN 0-521-44034-3/Hc \$49.95.
Cambridge University Press,
40 West 20th Street,
New York, NY 10011-4211.
1-800-872-7423."
, note = "346+xi pages, 228 exercises, 200 figures, 219 references"
}
Kenneth Sloan
compute eigenvectors/values and look at the smallest eigenvalue?
--
Kenneth Sloan Computer and Information Sciences
sl...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
David Eberly
> In article <1994Jul19.1...@rsg1.er.usgs.gov>,
> Dave Lorenz <lor...@srvrdmnspl.cr.usgs.GOV> wrote:
> >In article <30ghbe$l...@sophia.inria.fr>, wkh...@fafner.inria.fr (Wihem Kherrati) writes:
> >>
> >> Does anyone know a simple and Quick test to determine if 6 points are roughly
> >> coplanar ?
> >
> >A very simple test would be a linear regression using the x-, y-, and z-coordinates.
>
> Another method would be to compute the volume of the tetrahedra determined
> by four of your six points. This volume is zero if the points are
> coplanar. You could compute all 6-choose-4 volumes.
Sounds computationally expensive. Let P0 through P5 be the 6 points and
define Q1 = P1-P0, Q2 = P2-P0, ..., Q5 = P5-P0. Let these be the rows
of a 5x3 matrix and row-reduce it. The points are co-planar if and only
if the matrix has rank 2.
Dave Eberly
ebe...@cs.unc.edu
David Eberly
> In article <30ghbe$l...@sophia.inria.fr> wkh...@fafner.inria.fr (Wihem Kherrati) writes:
> >
> > Does anyone know a simple and Quick test to determine if 6 points are roughly
> >coplanar ?
> >
> >thanks.
> >w.
>
> compute eigenvectors/values and look at the smallest eigenvalue?
For which matrix?
Dave Eberly
ebe...@cs.unc.edu
Chris Mok
This could be one quick way but I'm not sure if it handles all cases:
(1) Randomly group points into two triangles
(2) Calculate normal vectors and compare, if they differs, then FALSE
(3) Swap one point of each triange and form two new triangles, repeat (1)-(2)
Just an idea. No proof. No nothing. :-)
--
Chris Mok cm...@io.org
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
Steve Seitz
|> >
|> > Does anyone know a simple and Quick test to determine if 6 points are roughly
|> >coplanar ?
|> >
|> >thanks.
|> >w.
|>
|> compute eigenvectors/values and look at the smallest eigenvalue?
The idea is that the points should span a subspace of dimension two if and only
if they are coplanar. Form a 3x6 matrix, M, where each column is a point.
M has rank 2 if and only if the points are coplanar.
To deal with `rough' coplanarity you have to use an approximate notion of rank.
A good way to do this is to compute the 3rd singular value of M, s3
(the singular values of M are the eigenvalues of M*(Mtranspose)--a 3x3 matrix).
s3 = 0 exactly when the points are coplanar and s is very small when the points
are close to planar. In fact, s3 gives you the error in a very direct sense:
s3/sqrt(6*3) is the average amount that you have to perturb each coordinate to
make the points coplanar.
This may sound tricky but all that is required is a matrix multiplication and
finding the smallest eigenvalue of a 3x3 matrix (i.e., solve a cubic poly eqn).
-Steve Seitz
P.S. Surprisingly, the same procedure can be used with 2 (projected) views of
the points (no 3D info) under orthographic projection.
Steve Seitz
left out one minor point (no pun intended!). If you do it the way I suggested
by putting all 6 points in a matrix it will count the origin as an implicit
7th point. The way to get around this is to use one of the 6 points as the
origin of world coordinates and put the 5 remaining points (with coordinates
with respect to the new origin) in the matrix. Then the 3rd singular value,
s3/sqrt(5*3) is the avg dist from planarity.
-Steve Seitz