How can I find out if point is within a triangle i

Question

I need an algorithm (3D), which would determine if point belongs to a triangle. And also if it does I want to know the distance between some point in triangle and a another point. Triangles can be slightly rotated, but if point is outside triangles vertical reach then it should not be considered as inside the triangle.

Now I realize, my question probably doesn't make a lot of sense so here's the picture, which explains what I want.

Grey lines display, which way triangle is actually facing.

---

It's not actually that I want to check if a point is within a prism, but I after i find out if point lies within triangle (not exactly, might be on top of or below) then I need to find the distance between point and a triangle it belongs to. And depending on the distance function will finally return if that point is inside the triangle. A little inaccuracy is allowed. However, maybe I want to check if a point is within a prism, but do not know that. I am just horrible at math so I am not aware of correct terminology.

Answer 1

This can be split into 2 problems.

1. Test that the point inside the 3-planes defined by the triangle sides.
2. Find the distance to the plane defined by the triangle normal.
   (and use own logic to test if this distance is considered close or not).

Withe the example below, you can do a check, for eg:

if (isect_point_tri_prism_v3(p, v1, v2, v2) and
    (dist_signed_squared_point_tri_plane_v3(p, v1, v2, v2) < (eps * eps)):

    # do stuff

... where eps is the distance to consider points 'on the triangle'.

This code example uses functional Python so should be easy to move to other languages, it uses only simple arithmetic, no sqrt or complex functions.

# ----------------
# helper functions

def sub_v3v3(v0, v1):
    return (v0[0] - v1[0], v0[1] - v1[1], v0[2] - v1[2])


def dot_v3v3(v0, v1):
    return ((v0[0] * v1[0]) + (v0[1] * v1[1]) + (v0[2] * v1[2]))


def cross_v3v3(v0, v1):
    return ((v0[1] * v1[2]) - (v0[2] * v1[1]),
            (v0[2] * v1[0]) - (v0[0] * v1[2]),
            (v0[0] * v1[1]) - (v0[1] * v1[0]))


def closest_to_line_v3(p, l0, l1):
    """
    Return the closest point to p on the line defined by (l0, l1)
    """
    u = sub_v3v3(l1, l0)
    h = sub_v3v3(p, l0)
    l = dot_v3v3(u, h) / dot_v3v3(u, u)
    return (l0[0] + u[0] * l,
            l0[1] + u[1] * l,
            l0[2] + u[2] * l)


def point_in_slice_v3(p, v, l0, l1):
    cp = closest_to_line_v3(v, l0, l1)
    q = sub_v3v3(cp, v)
    rp = sub_v3v3(p, v)
    # For languages which allow divide-by-zero,
    # this is taken into account and returns false.
    h = dot_v3v3(q, rp) / dot_v3v3(q, q)
    return (h >= 0.0 and h <= 1.0)


# --------------
# main functions

def isect_point_tri_prism_v3(p, v0, v1, v2):
    """
    Return True when the point is inside the triangular prism.

    Zero area triangles always return false.
    """
    return (point_in_slice_v3(p, v0, v1, v2) and
            point_in_slice_v3(p, v1, v2, v0) and
            point_in_slice_v3(p, v2, v0, v1))


def dist_signed_squared_point_tri_plane_v3(p, v0, v1, v2):
    """
    Return the squared distance to the triangle,
    positive values are 'in-front' of the triangle, negative behind.
    (using CCW coordinate system - OpenGL).

    Remove the 'copysign' call for the non-signed version.
    (if you don't need to know which side of the triangle the point is on).
    """
    from math import copysign
    n = cross_v3v3(sub_v3v3(v2, v1), sub_v3v3(v0, v1))
    rp = sub_v3v3(p, v1)
    len_sq = dot_v3v3(n, n)
    side = dot_v3v3(rp, n)
    fac = side / len_sq
    return copysign(len_sq * (fac * fac), side)

Answer 2

This seems like the 3D equivalent of Data structure to query points which lie inside a triangle. You could use the same method in 3D: in 3D, a plane cuts the space in two halves: a point is either at one side of the plane or at the other side. The wedge-shape is a collection of planes: just combine the which_side_of_the_plane information for a given point with all the planes that build up the wedge.

Answer 3

You can use a cylindrical version of barycentric coordinates. I've only checked this for prisms that rise perpendicular from the triangular base -- another way to put this is that we are orthogonally projecting the point into the plane defined by the triangle, and checking if it is inside or not.

If you want more details on the math ask (or better yet, try to figure it out yourself since it's a neat little exercise).

If our triangle is ABC (non-degenerate), then N = (B-A)x(C-A) (cross product) is a normal to the (unique) plane defined by the triangle. Call the point we want to test P.

Now calculate the value a' = N . ((P-B) x (P-C)) (where . is dot product). a' is the usual barycentric coordinate multiplied by N.N (which is positive).

Similarly, we find b' = N . ((P-C) x (P-A)) and c' = N . ((P-A) x (P-B)). If all three of 'a'', 'b'', and 'c'' are non-negative, then the projection of P is inside the triangle (if you want to exclude the triangle itself, then all three must be strictly positive).