algorithmgeometrypolygonpointconvex-polygon

How to check point is present inside a polygon if points are not aligned correctly?


I was working on a question In which we have to find the convex hull of given N points and check whether another P point is present in a polygon or not. So I implemented the Jarvis march gift wrapping algorithm. So, It returned output with correctly aligned points for a polygon if none of the endpoints of the convex hull is collinear. But in case of collinear These collinear points don't come in an aligned manner. So, If such a polygon comes without aligned endpoints how can we check Whether Point P is inside or outside? Mainly all algorithms I know or think of works on side fr which we should know exactly which point comes first and which comes second. Is there any approach for this special case???

example: If points of polygon are {0,0},{1,1},{4,4},{2,2},{3,3},{2,0} and Point is {2,1}. It should take it as polygon {0,0},{1,1},{2,2},{3,3},{4,4},{2,0} and It should return {2,1} is in polygon.


Solution

  • You could start by transforming the polygon to ensure there are no colinear points. Clearly only the endpoints of any colinear segment need to be retained.