1

I've googled all over for algorithms that do this but I can't find a single one that does it the way I need it to. Right now I am basically summing the areas formed by the three internal triangles and seeing if it equals the whole area but somehow it's not working properly, nor do I know if that's rigorous enough and covers all cases.

def isInsideTriangle(P,p1,p2,p3): #is P inside triangle made by p1,p2,p3?
    x,x1,x2,x3 = P[0],p1[0],p2[0],p3[0]
    y,y1,y2,y3 = P[1],p1[1],p2[1],p3[1]
    full = abs (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))
    first = abs (x1 * (y2 - y) + x2 * (y - y1) + x * (y1 - y2))
    second = abs (x1 * (y - y3) + x * (y3 - y1) + x3 * (y1 - y))
    third = abs (x * (y2 - y3) + x2 * (y3 - y) + x3 * (y - y2))
    return abs(first + second + third - full) < .0000001

Example: print isInsideTriangle((-10,0),(-10,-10),(10,-10),(0,10)) should be true, returns false

but print isInsideTriangle((0,0),(-10,0),(10,0), (0,10)) returns true as it should

user111373
  • 125
  • 1
  • 3
  • 8
  • That algorithm doesn't work properly (PointInTriangle((0,0),(0,0),(-10,4), (5,10)) returns false) – user111373 Nov 27 '13 at 16:40
  • 1
    @user111373 might want to put what you've found that "doesn't work" properly (and explain why) as part of your question so other people don't waste their making suggestions that "don't work" for some reason... – Jon Clements Nov 27 '13 at 16:42
  • 1
    @user111373 so if you have a list of test cases and known results... that's another useful thing to [edit] into your question... :) Always useful to include in your question - what you've tried and why it didn't work as expected and the expected outcome... – Jon Clements Nov 27 '13 at 16:42
  • Why don't you try changing each of these 3: `b1 = sign(pt, v1, v2) < 0.0f;` to `b1 = sign(pt, v1, v2) <= 0.0f;` ? I.e. allow points on the line to qualify? – KobeJohn Nov 27 '13 at 16:46
  • 1
    Unless my brain is completely fried, (-10,0) _isn't_ inside (-10,-10), (10,-10), (0,10). Or on an edge. – Chowlett Nov 27 '13 at 16:51
  • @user111373 I tried that and it works for me. Krumelur posted it as an answer and I guess that works too. – KobeJohn Nov 27 '13 at 16:53

1 Answers1

3

From the comments to your question I think what you are asking for is that the point should be considered to be in the triangle if it is on the edge. In this case, the cross product (called "sign" in the other question) would be zero, in which case you could change the comparison to consider zero to be on the "right side", i.e.

def sign(p1, p2, p3):
  return (p1[0] - p3[0]) * (p2[1] - p3[1]) - (p2[0] - p3[0]) * (p1[1] - p3[1])


def PointInAABB(pt, c1, c2):
  return c2[0] <= pt[0] <= c1[0] and \
         c2[1] <= pt[1] <= c1[1]

def PointInTriangle(pt, v1, v2, v3):
  b1 = sign(pt, v1, v2) <= 0
  b2 = sign(pt, v2, v3) <= 0
  b3 = sign(pt, v3, v1) <= 0

  return ((b1 == b2) and (b2 == b3)) and \
         PointInAABB(pt, map(max, v1, v2, v3), map(min, v1, v2, v3))

Now, this is not very stable numerically (you should never compare floats for equality) unless the points are in fact identical rather than equal (i.e. come from the same source).

If you want something a little more stable, maybe you could change <= 0 with <= ε where ε is some small number. But it all depends on what your use case is.

EDIT: Updated to handle degenerate triangles.

Krumelur
  • 31,081
  • 7
  • 77
  • 119
  • This doesn't seem to handle the case of degenerate triangles as well as it could. It returns True for `PointInTriangle((3,0), (0,0), (1,0), (2,0))`, which ideally should return False. – DSM Nov 27 '13 at 17:04
  • Yes, that is of course true. Its use all depends on its application. I "stole" the algorithm from the other question, which in turn "stole" it from GameDev. I think degenerate triangles are generally not that interesting in games, so it all depends. – Krumelur Nov 27 '13 at 17:08
  • Then also check if it lies within the AABB spanned by the triangle, for example. – Krumelur Nov 27 '13 at 17:10
  • But this gives a different answer for points on an edge, depending on whether you specify points clockwise or counterclockwise (as noted in a comment on the answer from the duplicate question). For example, `PointInTriangle((0, 0), (-10, 0), (10, 0), (0, 10))` gives `False` and `PointInTriangle((0, 0), (-10, 0), (0, 10), (10, 0))` gives `True`, but they should both be `True`. – John Y Nov 27 '13 at 17:46