Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a set of N 3D points (x,y,z cartesian coordinates) defining a closed contour and a 3D plane defined by a point and a normal.

What I want to determine is the point(s) where the closed contour and the 3D plane intersect.

Up to this point I'm clueless and just simply don't know how to start. I'm thinking about using a parametric equation (splines maybe?) to define my closed contour from the set of N 3D points, and then somehow try to use plane's equation to obtain the x,y,z coordinates of the intersection(s).

share|improve this question
    
If by 'closed contour' you mean a closed contour and not, say, a surface patch defined by a closed contour, why wouldn't you start by checking the intersection of the plane with each of the line segments which form the contour ? There are probably some easy tests to make on each segment to determine whether or not it is a candidate for checking. If you mean a surface patch, edit your question to clarify matters. –  High Performance Mark Apr 10 '12 at 8:51
2  
Is the contour made up of the line segments between your points, or is it something else? –  AakashM Apr 10 '12 at 9:46
2  
@msotaquira Well, then it's not a contour, is it? So you're rather asking for a good way to define a contour using those points, which is entirely dependent on the context and your needs. But using a simple piecewise linear curve, as Mark suggests in his answer (and AakashM assumed in his comment) would be a good start. –  Christian Rau Apr 10 '12 at 11:03
2  
Perhaps OP wants to know if the plane intersects the 'convex hull' of the set of points ? If so, OP should edit question and title to state this. I get really fed up answering the wrong questions here on SO. –  High Performance Mark Apr 10 '12 at 11:11
1  
@msotaquira A line-plane intersection is an extremely trivial operation. Come back when your contour has thousands of points to talk about computational expense. –  Christian Rau Apr 11 '12 at 10:40
show 3 more comments

migrated from stackoverflow.com Apr 11 '12 at 20:41

This question came from our site for professional and enthusiast programmers.

1 Answer

up vote -1 down vote accepted

If you have $n=72$ points, then you have $n-1=71$ pairs going to any particular point and ${n\choose2}=2485$ total pairs to check. But it's probably easier to just decide which side of the plane each point is on, with an array, or map, $$ \eqalign{ \phi &: \{1,~\dots,~n\}\to\{\pm1\} \\\\ \phi &: i \mapsto \phi(i)= \operatorname{sign}(\overrightarrow{PP_i}\cdot\overrightarrow{N}) \\\\ \overrightarrow{PP_i} \cdot \overrightarrow{N} &= a(x_i-x_0)+b(y_i-y_0)+c(z_i-z_0) \\\\ P_i &= (x_i,y_i,z_i)\qquad 0\le i\le n \\\\ \overrightarrow{N} &= (a,b,c) } $$ where $P_0$ is the point in the plane, $P_i$ is the $i$th surface/object point, and the normal vector $\overrightarrow{N}$ to the plane defines the direction or side of the plane which $\phi$ maps to $+1$. Then, assuming no points lie in the plane, the line connecting a given pair of points (say $i$ and $j$) crosses the plane iff $\phi(P_i)\phi(P_j)<0$. This takes $3n$ multiplications and $3n+2n=5n$ additions ($3$ subtractions & $2$ additions for each point) to compute and requires $n$ bits (assuming no points lie directly in the plane) or tertiary ($+1,0$ or $-1$) quantities (if a point can lie in the plane) of storage. For "real world" applications, you might also want to perform $n$ comparisons of the absolute value of the dot products against some $\epsilon$ as a threshold for considering the point to be in the plane rather than naively mixing your machine's representation and rounding errors. Is this a helpful start, too obvious, or irrelevant?

share|improve this answer
    
Thanks bgins, it was the approach I was looking for! I've just implemented it and works fine. –  msotaquira Apr 24 '12 at 7:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.