Jump to content
• Advertisement

# Coplanar points

This topic is 2808 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 have a series of 3d points in space that define a co-planar polygon. How can I check that the points are co-planar? One way is the define a plane using three of them, and then measuring distance between the plane and the remaining points. Is there any other efficient way of doing it? Thanks!

#### Share this post

##### Share on other sites
Advertisement
Solving the Plane equation ax+by+cz = d is the only method I know of

#### Share this post

##### Share on other sites
Quote:
 Original post by kaarigarI have a series of 3d points in space that define a co-planar polygon. How can I check that the points are co-planar? One way is the define a plane using three of them, and then measuring distance between the plane and the remaining points. Is there any other efficient way of doing it? Thanks!

This clearly takes only O(n) time, which must also be a lower bound, since every point needs to be involved. Three multiplications, two additions and one compare seems very little work for a single step, so I think this method should be pretty close to optimal:).

#### Share this post

##### Share on other sites
You can check if four points are coplanar by making a 4x4 matrix where the rows are your points extended with a 1 as a fourth coordinate. The points are coplanar if and only if the determinant of that matrix is 0.

#### Share this post

##### Share on other sites
If you compute the singular values of the 3xN matrix of points, then the third component will be zero (or close to it) for a coplanar set of points.

Demonstrating this with python:

>>> import random, scipy.linalg>>> p = [ (random.gauss(0,1),random.gauss(0,1), random.gauss(0,.1))  for i in xrange(100) ]>>> scipy.linalg.svdvals(p)[2]0.8806>>> p = [ (random.gauss(0,1),random.gauss(0,1), random.gauss(0,0))  for i in xrange(100) ]>>> scipy.linalg.svdvals(p)[2]0.0

The second and third components will be close to zero for a colinear set of points.

#### Share this post

##### Share on other sites
Quote:
 Original post by tobiasjsIf you compute the singular values of the 3xN matrix of points, then the third component will be zero (or close to it) for a coplanar set of points.Demonstrating this with python:>>> import random, scipy.linalg>>> p = [ (random.gauss(0,1),random.gauss(0,1), random.gauss(0,.1)) for i in xrange(100) ]>>> scipy.linalg.svdvals(p)[2]0.8806>>> p = [ (random.gauss(0,1),random.gauss(0,1), random.gauss(0,0)) for i in xrange(100) ]>>> scipy.linalg.svdvals(p)[2]0.0The second and third components will be close to zero for a colinear set of points.

I believe that only works for planes that pass through the origin. In general you need to add a fourth column of ones. Then you can do the same trick, but checking the fourth component of the singular values.

#### Share this post

##### Share on other sites
Quote:
 Original post by alvaroI believe that only works for planes that pass through the origin. In general you need to add a fourth column of ones. Then you can do the same trick, but checking the fourth component of the singular values.

You're completely right. Apologies, and thanks for the correction. The other alternative would be to subtract the centroid of the points, which is possibly quicker (given the SVD is slow) and likely more numerically robust.

#### Share this post

##### Share on other sites
Thank you, guys. I have enough knowledge from you to go about it now. Thanks!

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
Rutin
24
3. 3
4. 4
JoeJ
18
5. 5
• Advertisement

• 14
• 22
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631766
• Total Posts
3002219
×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!