CODEWITHSUNDEEP
c#c++mathgeometry
Kirill Ludcev
Kirill Ludcev

Reputation: 83

Find a 4 points that form a tetrahedron around some point

There is an array of points in 3 dimentions. 1 = {x,y,z}; 2 = {x,y,z}; 3 = {x,y,z}, ... n = {x,y,z}. Also we have a point t = {x,y,z}. How to spot a 4 points that form a tetrahedron around point t?

Upvotes: 1

Views: 556

Answers (3)

Salix alba
Salix alba

Reputation: 7824

A slight variation on @MvG. Using the Hesse normal form for a surface n⋅r−d=0 where n is a unit normal r is a point on a surface and d is distance from the point to a surface. Given three points on a surface p1, p2, p3 a normal is

n = (p2-p1) ^ (p3-p1)

Where ^ is the cross product. This is not unit length but thats not important. We can test whether a target point q is on the surface by calculating 

n . q  - n . p1

If it is zero then q is on the surface, otherwise the sign determines which side of the surface you are on. Note n . q is just the Triple product (a ^ b) . q which is expressed as a determinant. So our test is

triple( p2 - p1, p3 - p1, q ) - triple( p2 - p1, p3 - p1, p1 ).

Do this for each triple of points, and compare signs of t and forth point in the tetrahedron, as in MvG's solution. In fact if you do work out the algebra it should be the same test.

An optimisation it might be worth calculating before hand is that the x-coordinate of t must not be smaller that the minimum x-coord of the other points. Similar of max and min of x, y, and z. This might save a lot of multiplications.

Upvotes: 1

Codor
Codor

Reputation: 17605

Just a rough idea - the four points in question must have the same distance from t and must be pairwise in the same angle of 109.5°; might be a bit fiddlish to do in code though.

Upvotes: 0

MvG
MvG

Reputation: 61077

Attach a 1 to all your coordinates, effectively turning them into homogeneous coordinates. Then the sign of the determinant of the matrix formed by four such coordinate verctors tells you the orientation of the resulting tetrahedron. Or in other words, if you fix three points and plug in various vectors as the fourth, the resulting signs will tell you whether the fourth point is above of below the plane spanned by the first three.

Now you can build an algorithm from this. Start by choosing a triple of points. Then a fourth point is a valid coordinate only if it lies on the same side of the plane spanned by the first three as t. Multiply the signs, and if the result is positive you can continue. Check the other three sides of the resulting tetrahedron, and if t is inside all four, you are done. You could code this e.g. like this:

for i1 from 1 to n:
  for i2 from i1 + 1 to n:
    for i3 from i2 + 1 to n:
      for i4 from i3 + 1 to n:
        o = orient(i1, i2, i3, i4)
        if (orient(i1, i2, i3, t)*o > 0 and orient(i1, i2, t, i4)*o > 0 and
            orient(i1, t, i3, i4)*o > 0 and orient(t, i2, i3, i4)*o > 0):
          solution(i1, i2, i3, i4)

The function orient here is the determinant computation outlined above.

Upvotes: 2

Related Questions