Saturday, August 13, 2011

Finding whether a point lies inside a polygon

Hi, it's been a really loong break. Well after getting into the corporate world, you hardly get time!
I recently came across a problem TETRAHED in SPOJ which asks us to find whether a point lies inside a tetrahedron or not.
It seems quiet an interesting problem as the solution can be extended to any polygon.
In this we need to find the barycenters of the required point and then check the signs of the barycenters. If they are same then we can say that the point lies inside the region.
The problem has its application in geometric modelling and in graphics.
2.triangle centers
3 tutorial