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 :).
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 :).
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?
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.
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
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.
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.
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.
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.
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.
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.