1
$\begingroup$

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).

  • 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.2012-04-11

1 Answers 1

0

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?

  • 0
    Thanks bgins, it was the approach I was looking for! I've just implemented it and works fine.2012-04-24