Find if Point P is in Triangle ABC - Algorithm & Details

  • Thread starter Thread starter robert
  • Start date Start date
  • Tags Tags
    Point Triangle
AI Thread Summary
To determine if point P is inside triangle ABC in 2D space, use a method involving dot products and perpendicular vectors. For each triangle side, calculate a perpendicular vector and perform a dot product with the vector from the triangle vertex to point P. If the dot product is consistently positive or negative for all three sides, point P is inside the triangle. Reference the sign of the dot product between the perpendicular vector and the vector from vertex A to vertex C to ensure accuracy. This approach helps manage practical issues like border inclusion and numerical stability.
robert
Messages
23
Reaction score
0
I have a triangle in 2d space with points A(x,y), B(x,y), and C(x,y). I also have the point P(x,y). How do I find if the point P is in the triangle? If it involves anything like a cross product or dot product then please include details on how to do that. It's for a computer program and I have the variables ax,ay,bx,by,cx,cy,px,py so if someone could provide an algorithm that would be great. Thanks in advance.
 
Mathematics news on Phys.org
Here is another method, maybe a bit more simple, where practical issues like inclusion of the border or numerical stability are perhaps easier to control.

The following procedure is repeated 3 times, once for each side of the triangle. In the attached picture, representing one of the three iterations using side AB, the idea is to determine if the given point is in the "green area", on the same side of the line as the triangle itself. (If this is true for the three sides, then the point is inside.) I use a vector perpendicular to the line, as drawn in the picture. If the vector from vertex A to vertex B is (p,q) = (Bx-Ax, By-Ay), then a perpendicular vector could be (-q,p). Now, a dot product between this perpendicular vector and any other vector (in particular, the vector from A to our given point P) will be positive on one side of the line, and negative on the other; we can use this sign to discern at which side any point lies. But there is a caveat: we don't really know towards which side (green or red) the perpendicular vector will point to (due to the simplistic way in which it was calculated; forcing it to the actual green side would require a good number of extra tests). In the picture it is on the green side, but it could have been just as perpendicular but on the red side. What I do is to use, as a reference, the sign of the dot product between the perpendicular vector and the vector from A to C (since C is always on the green side, on the side that contains the triangle).

The dot product of two vectors, Ux,Uy and Vx,Vy, is of course UxVx + UyVy.
 

Attachments

  • triang.png
    triang.png
    640 bytes · Views: 555
Last edited:
Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Thread 'Imaginary Pythagorus'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
Back
Top