0

I'm trying to write an algorithm to determine if point is located inside a triangle or on it's edge in 3D coordinate space. For example, I try to reach such results for different cases enter image description here

enter image description here

enter image description here

enter image description here

I've figured out how to check if point P inside the triangle, I calculated normal vectors for triangles ABP, BCP, CAP and checked if they are similar.

Can someone explain how to check if a point is on the edge of a triangle (but not outside of a triangle)? You can provide formulas or code as you wish.

Dark_Phoenix
  • 368
  • 3
  • 14
  • minor nit, triangle is 2d not 3d – pm100 Feb 16 '22 at 00:17
  • 1
    https://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle – pm100 Feb 16 '22 at 00:18
  • See https://en.wikipedia.org/wiki/Barycentric_coordinate_system#Barycentric_coordinates_on_triangles – lhf Feb 16 '22 at 00:18
  • @pm100, I have a triangulated mesh in 3d space, so the triangles themselves have 3d coordinates – Dark_Phoenix Feb 16 '22 at 00:19
  • Can a point be 'in the triangle' while not being on the same plane as the triangle? – Tyler Feb 16 '22 at 00:21
  • @Tyler, what do you mean? – Dark_Phoenix Feb 16 '22 at 00:23
  • 1
    I think @Tyler is asking if the point has to be on the triangle plane or if you are doing some projection into 2d and checking the projected point vs the projected triangle. – Fantastic Mr Fox Feb 16 '22 at 00:28
  • He's asking if the point can be above or below the triangle and still be true? – user4581301 Feb 16 '22 at 00:28
  • 1
    Side note, if you're looking for a formula you can turn into code, you might be better off asking at Mathematics. – user4581301 Feb 16 '22 at 00:29
  • The point lies on the same plane as the triangle. But I want to check if it is between two points or on the same line (like 4th picture) but outside the triangle – Dark_Phoenix Feb 16 '22 at 00:31
  • First pass: generate a bounding box of the triangle. You can quickly check to see if the point is inside-or-outside the bounding box. – Eljay Feb 16 '22 at 00:42
  • Does this answer your question? [How to determine if a point is in a 2D triangle?](https://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle) –  Feb 16 '22 at 00:44
  • 1
    https://stackoverflow.com/a/34093754/10091872 –  Feb 16 '22 at 00:45
  • A point lies on the edge if it is colinear with any two points of the triangle. Remember, this is CS, so there will be a small _epsilon_ you should account for. If the point computes as _in_ the triangle _and_ as reasonably colinear with AB, AC, or BC, then it is on the edge. – Dúthomhas Feb 16 '22 at 05:04

1 Answers1

0

Make vectors:

r = p - A (r.x = p.x - A.x, r.y = p.y - A.y, r.z = p.z - A.z)
s = B - A
q = C - A

Calculate normal to ABC plane:

n = s x q  (vector product)

Check if p lies in ABC plane using dot product:

dp = n.dot.r

If dp is zero (or has very small value like 1.0e-10 due to the floating point errors, then p is in the plane, and we can continue

Decompose vector p by base vectors s and q. At first check if z-component of normal (n.z) is non-zero. If so, use the next pair of equations (otherwise choose equations for x/z or y/z components):

px = a * sx + b * qx
py = a * sy + b * qy

Solve this system

a =  (sy * qx - sx * qy) / (py * qx - px * qy)  
b =  (px - a * sx) / qx

If resulting coefficients a and b fulfill limits:

a >= 0
b >= 0
a + b <= 1.0

then point p lies in triangle plane inside it.

MBo
  • 77,366
  • 5
  • 53
  • 86
  • Hi MBo. If you consider a rotation that brings the triangle in the plane XY, the resolution becomes crystal clear, most of it becoming a 2D discussion. And tolerancing (in terms of distances) becomes easy to deal with. –  Feb 16 '22 at 11:08
  • @Yves Daoust Here I use projection onto proper plane. It seems for me that rotation is a bit more complex. Concerning rotation approach - it is worth to transform vertices into (0,0,0), (1,0,0), (0,1,0) - affine matrix calulation should be simpler, final stage is elementary. – MBo Feb 16 '22 at 15:28
  • The projection on a plane is still 3D, and the rotation is simpler than you think. The affine transformation is tempting, but it does not preserve the Euclidean distance. But what matters most, the geometry is easier to think about. –  Feb 16 '22 at 15:32