3

I have the (x,y)-coordinates of all three corners of a 2D-triangle. Now I want to check if a point with (xp,yp) is inside this triangle: I know two methods (only theoretically, not yet implemented) to check:

  • with vectors:

    vec_0A + vec_AB*lambda + vec_AC*my = vec_0P

lambda + my =< 1

  • with equations of lines:

calculate the three linear equations of AB, AC, BC and check for each equation if P is left/right of it.

Problem 1: It must be accurate, because typical (x,y)-values of my corners and points look like this: (-0.049721957725789148, 0.024809768773549616) -> 18 positions after decimal point

Problem 2: It should has a good performance, because I want to check if P is inside triangle(ABC) OR inside triangle(DEF) OR inside triangle(GHI) OR inside triangle(JKL) OR outside of all of them. And I have to do it with ~ 10,000 points.

I read somewhere that the vector-way isn't that accurate. True? Do you know some other ways of checking? Which way of checking do you recommend?

zhangyangyu
  • 8,520
  • 2
  • 33
  • 43
Munchkin
  • 4,528
  • 7
  • 45
  • 93
  • Don't see any problem with the vector approach. Accuracy will depend on your hardware. This [post](http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-triangle) has some more info. – dwxw Jul 12 '13 at 14:44
  • This looks like it could be useful: http://www.blackpawn.com/texts/pointinpoly/ – user2357112 Jul 12 '13 at 14:47
  • Both ways are valid and there is nothing inherently inaccurate about them. The first way _should_ be a bit faster, imho. I don't know how often you have to check these 10k points, but it shouldn't take too long either way. Regarding precision: Python's `float`s are double precision, which gives you a precision of ~16 decimal digits. If you need more, there's always [`decimal`](http://docs.python.org/2/library/decimal.html) (though that'll be way slower). – Carsten Jul 12 '13 at 14:51
  • Another reasonable approach would be to calculate the centroid of the triangle, then see if the line segment between the centroid and your test point intersects any of the three sides. I don't know that that's easier/harder/better/worse than the other approaches... – twalberg Jul 12 '13 at 14:56

1 Answers1

3

With problems like this always look for libraries... it is a mathematical problem and probably has a solution in a library. One quick answer:

import matplotlib
matplotlib.path.Path.contains_points   # is the function you are looking for

check the docstring for usage instructions.

Joop
  • 7,840
  • 9
  • 43
  • 58