Sign in to follow this  

Test for nonplanarity

This topic is 3241 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was wondering if there's a simple and quick test for determining if a polygon is nonplanar? I have some ideas, (like triangulate it and compare all the normals), but I thought I would get a second opinion.

Share this post


Link to post
Share on other sites
Let's suppose you have the pentagon A B C D E. You can calculate the cross product (B-A)x(B-C) (the normal of the plane). If the polygon is planar, then the dot product of (B-A)x(B-C) with any other edge (e.g. D-E) should be near zero, since all the other edges should be perpendicular to ((B-A)x(B-C)) in order to lie on the same plane. I hope I am not missing anything.

Share this post


Link to post
Share on other sites
Grab the first three points and calculate the coefficients for the plane equation (assuming they're non-collinear, otherwise chose the first three non-collinear points). Check to make sure that all other points satisfy that equation, within a certain amount of tolerance. If they do, the polygon is planar.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zipster
Grab the first three points and calculate the coefficients for the plane equation (assuming they're non-collinear, otherwise chose the first three non-collinear points). Check to make sure that all other points satisfy that equation, within a certain amount of tolerance. If they do, the polygon is planar.


that's a pretty good method but you introduce a bias by picking the first 3 points, which could be removed by starting with the least squares equation of a plane and then checking for error from the least squares plane.

Share this post


Link to post
Share on other sites
Thanks, I guess I could go either way, use the DotProduct or get the plane coefficients, as explained here:
http://local.wasp.uwa.edu.au/~pbourke/geometry/planeeq/

But what is this least squares equation of a plane you mentioned?
It sounds useful if I wanted to convert a nonplanar polygon into a planar polygon, but this is only a test for nonplanarity.

Share this post


Link to post
Share on other sites
Quote:
Original post by theequal
Thanks, I guess I could go either way, use the DotProduct or get the plane coefficients, as explained here:
http://local.wasp.uwa.edu.au/~pbourke/geometry/planeeq/

But what is this least squares equation of a plane you mentioned?
It sounds useful if I wanted to convert a nonplanar polygon into a planar polygon, but this is only a test for nonplanarity.


We both made some assumptions about your problem statement. Specifically, we assumed that you want some tolerance to roundoff error, and I additionally assumed that you might want some small tolerance on what is considered planar.

For example, let's say you have 10 points belonging exactly to a plane. Then one of the points is moved off the plane by 1 picometer. IS it still "planar"? How about a millimeter? An inch?

Note that, due to floating point precision issues, even if you intentionally calculate a set of points to be perfectly planar, they won't end up being 100% perfectly planar...so you should use an error tolerance.

You can visualize this question in 2 dimensions by asking if a set of points are colinear (part of the same line). By zipster's method you would choose the first 2 points, calculate the line between them (by y=mx+b) and then calculate the distance (assuming vertical distance) of each point to the line. Note that the vertical distance is biased by the basis vectors and a more robust method would be to use the point-to-line distance as an error tolerance.

Anyway, using that method, you could have a situation with for example 10 points, all of the last 9 are perfect, but the first 1 is not so good. By forming the line between the first two, it causes the last (good) point to exceed the error tolerance and the whole thing is considered not-colinear. But if you use the best fit line, and then measure the error from that, the largest error would be smaller than the largest error you got by using only the first 2 points, so this might cause it to be identified as colinear.

Because there is no special ordering of the points, the unbiased decision is more logical. You may not care about this level of precision so Zipster's method is a little bit simpler.

Depending on how accurate you wanted to be you could even improve this more. For example the typical least squares approach would only measure errors on one dimension, and you could instead use a least squares fit that minimizes the point-to-plane distance of each point, and then use the maximum point-to-plane distance for a threshold. Maybe you also want to consider the situation where the set of points is MOSTLY planar, but has a couple non-planar points mixed in. Then you should combine the method with RANSAC. It depends on the problem.

Share this post


Link to post
Share on other sites
Quote:
Original post by yahastu
Quote:
Original post by theequal
Thanks, I guess I could go either way, use the DotProduct or get the plane coefficients, as explained here:
http://local.wasp.uwa.edu.au/~pbourke/geometry/planeeq/

But what is this least squares equation of a plane you mentioned?
It sounds useful if I wanted to convert a nonplanar polygon into a planar polygon, but this is only a test for nonplanarity.


We both made some assumptions about your problem statement. Specifically, we assumed that you want some tolerance to roundoff error, and I additionally assumed that you might want some small tolerance on what is considered planar.

For example, let's say you have 10 points belonging exactly to a plane. Then one of the points is moved off the plane by 1 picometer. IS it still "planar"? How about a millimeter? An inch?

Note that, due to floating point precision issues, even if you intentionally calculate a set of points to be perfectly planar, they won't end up being 100% perfectly planar...so you should use an error tolerance.

You can visualize this question in 2 dimensions by asking if a set of points are colinear (part of the same line). By zipster's method you would choose the first 2 points, calculate the line between them (by y=mx+b) and then calculate the distance (assuming vertical distance) of each point to the line. Note that the vertical distance is biased by the basis vectors and a more robust method would be to use the point-to-line distance as an error tolerance.

Anyway, using that method, you could have a situation with for example 10 points, all of the last 9 are perfect, but the first 1 is not so good. By forming the line between the first two, it causes the last (good) point to exceed the error tolerance and the whole thing is considered not-colinear. But if you use the best fit line, and then measure the error from that, the largest error would be smaller than the largest error you got by using only the first 2 points, so this might cause it to be identified as colinear.

Because there is no special ordering of the points, the unbiased decision is more logical. You may not care about this level of precision so Zipster's method is a little bit simpler.

Depending on how accurate you wanted to be you could even improve this more. For example the typical least squares approach would only measure errors on one dimension, and you could instead use a least squares fit that minimizes the point-to-plane distance of each point, and then use the maximum point-to-plane distance for a threshold. Maybe you also want to consider the situation where the set of points is MOSTLY planar, but has a couple non-planar points mixed in. Then you should combine the method with RANSAC. It depends on the problem.


Let's say I don't know how to do that, but at the same time, I don't want to use one of my points as the initial plane point.
Do you have any objections against using the average of all points as the plane point?
So, use that as a reference to test all other points?

Share this post


Link to post
Share on other sites
Taking the barycenter as the representative point on the plane should be fine.

To find the perpendicular vector, you can probably study the covariance matrix of the three coordinates, and pick an eigenvector corresponding to the smallest eigenvalue. I would have to think a little more carefully about it, but I am sure something like that can be worked out.

Perhaps I'll post some code if I find the time to write it tonight.

Share this post


Link to post
Share on other sites
Quote:
Let's say I don't know how to do that, but at the same time, I don't want to use one of my points as the initial plane point.
Do you have any objections against using the average of all points as the plane point? So, use that as a reference to test all other points?


Given a set of data points, the average point is the least squares POINT. It takes 3 points to define a plane. The least squares plane is by definition the "average plane" passing through all of those points. Note that the average point also lies on the least squares plane. The most simple way to calculate the least squares plane is by assuming a plane of the form z = ax + by + c. Then you can simply find the least squares line in the x and y directions and use this to construct the plane. All this requires is looping over the data points and computing some sums of squares.

Alternate ways of computing the least squares plane would be to, as alvaro suggested, compute the variance-covariance matrix of your data set and then take the eigenvector corresponding to the largest eigenvalue. To get the dominant eigenvector the simplest method is to use the power iteration, which just involves multiply a matrix times a vector and normalizing it in a loop.

There are a whole host of other complicated methods that can be used for finding a least squares solution (to a plane, or to any other system of linear equations). The fastest method is Cholesky decomposition, but you could also use QR decomposition, Singular value decomposition (take the singular vector corresponding to the smallest singular value), Gaussian elimination, Gauss-Jordan elimination, Gauss-Seidel iterations. If the system is small (ie, a plane with 3 unknowns) then it can be solved with only a 3x3 matrix inverse which could be computed directly by the Laplace Expansion Theorem.

EDIT - anyway, without further description of your problem specifying exactly WHY you want to know if a set of points is coplanar, we are likely to lead you astray in our comments.

Share this post


Link to post
Share on other sites
You run into problems using a functional form of the plane equation. For instance with z = Ax + By + D, you assume the Z component of the least-squares plane normal is non-zero. If it's zero, then you'll end up with a divide-by-zero, an un-invertible matrix, or some other invalid operation during your calculations. It's best to use an approach that can handle the general form, Ax + By + Cz + D = 0, and doesn't make any assumptions about the plane itself.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zipster
You run into problems using a functional form of the plane equation. For instance with z = Ax + By + D, you assume the Z component of the least-squares plane normal is non-zero. If it's zero, then you'll end up with a divide-by-zero, an un-invertible matrix, or some other invalid operation during your calculations. It's best to use an approach that can handle the general form, Ax + By + Cz + D = 0, and doesn't make any assumptions about the plane itself.


What Zipster says is true, which is why I listed several robust methods for estimating the plane. However all of these methods require using more complicated math than the basic form of z = Ax + By + D, which can be computed with just basic math skills and without the need for any math library.

In some cases this basic form is in fact preferable. For example, if your points are coming from a depth buffer where you know you can't have 2 points with the same x and y values having different z-values, then it is impossible to have a plane where the Z component of the normal is zero, and you want to avoid all of those planes when considering the least squares plane.

Share this post


Link to post
Share on other sites
Quote:
Original post by theequal
I was wondering if there's a simple and quick test for determining if a polygon is nonplanar?

I have some ideas, (like triangulate it and compare all the normals), but I thought I would get a second opinion.



Here is a third, or maybe fourth or fifth opinion:

We may assume the polygon has at least four vertices, say A, B, C, D etc.

The quadrilateral ABCD is planar if and only if the volume of the tetrahedron with vertices A, B, C, D is zero.
Formulas for the volume of a tetrahedron are easily retrieved. The fastest formulas use the Cartesian coordinates of the vertices. They involve four order-3 determinants, altogether 24 products of three factors each.
Beware however of loss of significant decimal places; the best one can do in this respect is to refer all calculations to the centre of gravity of the tetrahedron.

A general N-gon with vertices A, B, C, D, E, F etc. is planar if and only if the volumes of the N-3 tetrahedrons with consecutive vertices of the N-gon (ABCD, BCDE, CDEF etc.) as their vertices are all zero.

Good luck: Joher

Share this post


Link to post
Share on other sites

This topic is 3241 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this