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.

There is a square lying on a plane in 3d space. I have:

  • N: normal of the square
  • S: vector normal to N determining the orientation of a pair of the square sides
  • C: coordinates of the center of the square
  • s: length of the side of the square
  • P: a point

How can I determine if the point is inside the square? Let's suppose that we already know that the point lies on the same plane of the square.

share|improve this question
    
What do you mean by a normal of the square (since it is in a plane)? –  copper.hat Dec 7 '12 at 22:22
    
the normal of the plane :) the plane is defined by a point (C, that is also the center of the square) and the normal N –  Giacomo Tagliabue Dec 7 '12 at 22:22
    
That doesn't answer my question. Is the plane in some larger space? How do you know the orientation of the square? –  copper.hat Dec 7 '12 at 22:23
    
it's in 3d space. the orientation of the square is not actually given, you are right. Let's say that we have another vector S normal to N that is the orientation of a pair of sides. Hope it's clear –  Giacomo Tagliabue Dec 7 '12 at 22:25
    
I don't follow the $S$ bit? –  copper.hat Dec 7 '12 at 22:26

3 Answers 3

up vote 3 down vote accepted

Given the $S$ you mentioned in the comments (without which the problem is ill-defined), you can take $S\times N$ to get a vector in the direction of the other pair of sides. Normalize both $S$ and $S\times N$ and express $P-C$ in the basis of those two vectors. If the components are both between $-s/2$ and $s/2$ then the point $P$ is inside the square.

share|improve this answer

Here is one way (not guaranteed to be the simplest, but easy enough for computers) to do this task in the plane.

Let $A$, $B$, $C$ and $D$ be the position vectors of the vertices of the square, written clockwise. Imagine for a moment that $P$ is a point near the center of the square. Connect $P$ to the vertices with line segments.

By taking the cross product of the vectors $(B-P)\times(A-B)$ you get an "upward" normal, reflecting the fact that the triangle $PBA$ (around the edges in that order) is oriented counterclockwise. The same thing can be done with $PCB$, $PDC$ and $PAD$. If you set up all four of these counterclockwise-oriented (upward) triangles, then no matter where your point $P$ appears in the interior, all of the cross products will come out pointing upward.

If someone accidentally gives you the vertices in counterclockwise order, nothing changes except that all the triangles are oriented clockwise (downward).

Now imagine you take $P$ and pull it over one of the sides: what happens to the triangles? If you pull it over a side, then one of the orientations reverses. If you pull it directly over a corner, two of the orientations reverse.

So: there is your test. After you have set up your equations to give you four upward oriented triangles for an interior point, plugging in any exterior point results in a mixture of orientations for the four triangles. If all four are up or all down, then the point is in the interior.

share|improve this answer
    
You should mention that you can check the orientation of a triangle, say $PBA$, via the sign of the dot product of $N$ with your $(B-P)\times(A-B)$. –  Rahul Dec 7 '12 at 23:02
    
neat solution, even if I have to compute the 4 vertices from the information that are given. Pretty fast though. –  Giacomo Tagliabue Dec 7 '12 at 23:11

Compute $\alpha = \langle N, P-C \rangle$. If $\alpha \neq 0$ then $P$ is not on the plane.

If $\alpha = 0$, compute $l_1 = \langle \frac{S}{\|S\|}, P-C \rangle$. If $|l_1| > \frac{s}{2}$, then $P$ is not in the square.

If $|l_1| \leq \frac{s}{2}$, compute $l_2 = \|P-C-l_1 \frac{S}{\|S\|}\|$. If $|l_2| > \frac{s}{2}$, then $P$ is not in the square, otherwise it is inside the square.

Aside: $l_1 \frac{S}{\|S\|}$ is the component of $P-C$ along a unit vector in the $S$ direction, and $P-C-l_1 \frac{S}{\|S\|}$ is the vector in a direction perpendicular to $S$ that lies in the plane (since $P-C$ and $S$ are perpendicular to $N$).

share|improve this answer

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.