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

  • 2
    Is the contour made up of the **line segments** between your points, or is it something else?2012-04-10
  • 0
    Actually not, until now is just a set of 3-D points2012-04-10
  • 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.2012-04-10
  • 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.2012-04-10
  • 0
    @High Performance Mark No, I'm not interested in the intersection with the convex hull.2012-04-10
  • 0
    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.2012-04-10
  • 0
    The problem is that the set has a total of 72 points, so there would be a total of 71 line segments to test for intersection. Since the plane is going to be translated, and for each translation the intersection has to be computed, I think it would be computationally expensive.2012-04-10
  • 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