Usu's blog

Point inside a polygon
By Usu, history, 6 years ago, In English

Hey guys! I need your help. Lately I tried to make a program which check if a point is inside o polygon, I did it in N^2 for convex, I didn't find a brute force for concave. So if you can help me, I would be grateful for an implementation or a link for concave (brute force) and an implementation for faster running time, I know the idea behind it, but my implementation have some bugs and I want to see a corect one. That from geeksforgeeks is not correct if you think about it. Thanks in advance!

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If you have a ray from the inside point in the polygon to any side it will cross the polygon odd number of times, and if it is in the outside it will cross it even number of times.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I know, but I have problems with implementation :)

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

http://codeforces.com/blog/entry/48868

→ Reply