Question: Given points on a surface, how can well check whether another test point falls inside the surface?

I don't have equation defining the surface. All I have, are sample points lying on the surface. It is no exaggeration to say that the sample points I have on the surface define the surface itself. And because of the nature of my application, I always know that those points will come to define an ellipsoid like surface such as this:

enter image description here

For a similar question, you can refer to here. The reason why I asked that question was because I thought that answering that question, I could have answered this question as well. My initial approach was to write out the equations of the surface, I can then check whether a test point is inside the surface or outside of it. More explicitly, if I found that

$$\sum_{i=0}^n \sum_{j=0}^{n-i} \sum_{k=0}^{n-i-j} a_{ijk}\,x^iy^jz^k > 0$$

Then I can be sure that the test point lies outside the surface.

If I found that $$\sum_{i=0}^n \sum_{j=0}^{n-i} \sum_{k=0}^{n-i-j} a_{ijk}\,x^iy^jz^k = 0$$

Then I can be sure that the test points lies exactly on the surface. And so on.

But upon further thought, I am unable to convince myself of the merit of this approach. That's why I ask a more direct question here.

Any idea?


Triangulate the points to make a closed tesselated volume (ask again if you don't know how). Then fire a "ray" from your test point, and count its intersections with the set of triangles. If the number of intersections is odd, the test point is inside the volume.

  • $\begingroup$ bubba, how should I define the ray? For a ray to be formed, you will need two points. I know one of the points must be the test point, what about another point? $\endgroup$ – Graviton Aug 16 '13 at 10:49
  • 1
    $\begingroup$ It doesn't matter. The ray starts at your test point, and goes to infinity in any direction you want. Based on your knowledge of your problem, you may be able to decide some preferred direction. If not, just shoot parallel to one of the coordinate axes to make the triangle intersection calculations easier. $\endgroup$ – bubba Aug 16 '13 at 10:56
  • $\begingroup$ I should have mentioned -- the ray doesn't really require two points; it is defined by one point (your test point) and a "shooting" direction vector. $\endgroup$ – bubba Aug 17 '13 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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