Shafaet's blog

Need help to find "Point Inside a Polygon"
By Shafaet, 14 years ago, In English
Given all the points of a n-sided polygon in anti-clockwise order i need to find if a specific point P lies inside the polygon or not.

I searched in google and found 2 good algorithms. Ray Casting algorithm and Winding Number algorithm. I think the second one is simpler and less likely to result in floating point error.

I am not very good at geometry and i am facing difficulty in finding the angles in Winding algo. Wikipedia says "If the winding number is non-zero, the point lies inside the polygon. One way to compute the winding number is to sum up the angles subtended by each side of the polygon." So if the angle is exactly zero, than the point is outside.

Can anyone help me to measure the angles? I am not sure when an angle should be negative.

Thanks in advance :).
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Are we given convex polygon? If yes, we need just to check that given point lies on one side of the line.Otherwise count the sum of all the triangles' square wich are composed by given point and 2 neighbor points of polygon. If sum=square of polygon then the point lies inside the polygon, otherwise no. 
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    The polygon can be both convex or concave. So i need a more generalized algorithm.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      So follow the second method that i've described:)
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        Does the second method works for all polygon? What about a polygon like this one:

        In this case some triangle area may fall outside the polygon even if the specific point is inside the polygon, depended on position of the specific point. Am i wrong?
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          yeah, you are right....and I'm wrong(
          → Reply
        • 14 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          You can calculate the signed square of triangle using cross product.

          After calculating sum of squares of all triangles don't forget to wright  SumOfSquares=abs(SumOfSquares) or something like this.

          → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think a safe way to calculate the angle is using atan2...
Iterating over the N vectors (v[i] = point_in_poly[i] - point_to_test) and sum all adjacent angles.

for(i : [0 ... N - 1])
sum += atan2( cross_product(v[i], v[(i+1)%N]), inner_product(v[i], v[(i+1)%N]) )

then check sum
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
If you just want to use it as a subroutine, there should be a lot of ready-to-use libraries to do that task.

If you want to understand the algorithms, I recommend you to read a good textbook in computational geometry.  Although Wikipedia gives a brief overview of these algorithms, it is no comparison to a good textbook.  In general, Computational Geometry: Algorithms and Applications by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars is an excellent textbook in this field.  Although I do not have the book right now within my reach and I cannot guarantee anything, I am reasonably sure that it explains both algorithms.

Note that if all the numbers in the input are integers, we do not need floating-point arithmetic at all to implement either of the two algorithms.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks for the referring the book,i will try to collect it. Bth how can i measure the angles without floating point? The angles wont be integer all the time,isnt it? Or did i misunderstand the algo :(?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      It is true that a straightforward implementation of the winding number algorithm would require trigonometric functions.  The Wikipedia article explains a little about how to compute the winding number by using only integer arithmetic, but as I said, it is better to read a textbook to understand the algorithm.  And hopefully it is fun to study these two algorithm.

      However, I realized that I cannot find the explanation of either algorithm in the textbook by de Berg et al., at least through Google Books.  A quick search with Google Books showed that Section 20.3 of the book Introduction to Geometric Computing by Sherif Ghali explains the algorithm based on ray casting.
      → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
The following algorithm works on any polygons:

Generate random point A with big coordinates. So big that it definitely lies outside the polygon.
No count the number of intersections between sides of the polygon and segment (A, P).
If it is odd - the point lies inside the polygon, otherwise it is outside.

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    ++
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    There are some problems when one or more of vertex of the polygon lies on the (A, P). When we go from A to P and intersect one of such point, the next part of the segment AP may lie inside or outside of the polygon equiprobably.

    What we can do if AP contains one of sides of the polugon?

    It may be fixed if we try your test more times (for example, 100) and at end choose a version, which happen more times than another version. It is some probabilistic algorithm :D.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is the probability that polygon vertex lies on the segment?

      Especially if the random point is something like (14134*PI, 32324*sqrt(2)) ;)

      I've never had problems with this method, and of course I ran the test only once, not several times.


      Even if we want to work only with integers - magic point such as (1287332,43143445) - and it's unbelievable that there is counter-example in the testset.

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I agree that probablity of wrong answer is vanishingly small. But I think that it must be declared that this probability is nonzero.

        If you use the magic constant in a competition like ACM - it is ok (in WA case you can just change magic constant). In case of competition like TopCoder/Codeforces you may be challenged/hacked. Also you may be hacked if you use rand() without srand() and run test only once.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Ah, really, the method with integer numbers may lead to hacks. When the constants are real - I still think it's almost impossible to hack them, because problem inputs are usually integers or real numbers with low precision.
          → Reply
          • 14 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it
            I agree.

            UPD. A beautiful idea came into my head. For integer numbers we can put A = P + (Z, 1) (Z is large). Because gcd(Z, 1)=1 there are no integer points inside AP. So aglorithm will be always correct.
            → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks. This is called Ray Casting algorithm,i haven't implement it yet,i am trying to implement Winding Number algorithm first.
    → Reply