Please help to design the algorithm and compute complexity

#1

Given some points of a Convex polygon, you need to design an algorithm to check weather a given
point lies inside the polygon or not.

Warning!!!

  1. NOT to waste unnecessary memory.
#2

hello @sch

extend the given point till infinity (ie convert point in line segment with one end at the given point and one at infinity) and then see how many times it intersect the polygon.
if its odd no of times then answer is inside otherwise outside

#3

how can I check if the line intersect the polygon or not

#4

iterate through all the edges of the polygon(in cyclic order i ,(i+1) ) and then see whether this line segment intersects with segement generated by point or not.

refer this for clarity-> link

#5

The algo given in gfg doesn’t work for polygon (2,3), (4,3), (4,2), (4,1), (2,1), (1,2) and point (3,2). Could you please review it?

#6

try giving input in anticlockwise fashion

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.