We're dealing with country borders, that is the set of multiple disjoint domains that is made of polygons. The problem is to identify the country (http://en.wikipedia.org/wiki/List_of_sovereign_states) by a give point on the map. To accomplish this we've been told to implement the ray casting algorithm, but the country is far from being the simply-connected domain. For example, Italy consists of many disjoint domains.
In this case is the crossing number algorithm or the even-odd rule algorithm still a valid approach for validation if the point in question is within the country borders?
EDIT-1
In case it is interesting to someone I've open similar discussion at http://scicomp.stackexchange.com/questions/3587/ray-casting-algorithm-for-multiple-disjoint-polygons-is-still-valid
EDIT-2
I did NOT mentioned the Point in Polygon algorithm (http://en.wikipedia.org/wiki/Point_in_polygon) in the question since I don't feel myself to be an expert in the area and expected the open discussion and your thoughts about the problem we're encountered in the practical applications and second it seems that this algorithm have some drawbacks since it is based on the ray tracing (http://en.wikipedia.org/wiki/Ray_tracing_(graphics)#Disadvantages).
Correct me if I'm wrong but I think so. Given a point in the plane, if you trace an horizontal segment, say, to the right -growing X direction- and the number of intersections with the -unique- boundary is odd, the point is inside it.
Algorithm, which you interests, is applied basically only to simply-connected domain (polygon).
In your case, a problem to be reduced to a point-location problem on planar sub-division (map).
For the decision of this problem there are many efficient methods: slab method, chain method, triangulation refinement method and etc. These methods more efficient than ray casting algorithm. They in details described, for example, in the monograph: F. P. Preparata and M.Shamos «Computational geometry. An introduction». This book is published also in Russian.
The odd-even intersections algorithm works on one or several boundaries, even overlapping. Odd intersections is inside, even is outside. Finally, it resolves to finding intersections between segments and a line. Please click on the image below.
Efficiency and level of complexity are other considerations, though.
In principle, it is possible to use ray casting algorithm to map. But in order to get the right solution it is necessary to consider the following: the number of intersections, the number of intersecting areas (even or odd), how intersecting areas are connected among themselves (have the general edge or not) etc.
But efficiency of this method will be O(N). Exist, as I already mentioned, the best methods with complexity O(logN).
May be, I have not understood a question essence.
Igor, are you talking about point-in-polygon, that is, given a point and a polygon, determine whether the point is inside the polygon? If so, then ray-tracing implemented correctly can work for a complex polygon composed from a set of simple polygons. But I'm skeptical that it works when there is intersection of the individual polygons. I think they must be disjoint. I don't think the algorithm needs to be much different, but implementing it correctly requires a lot of thought about boundary cases.
The same algorithm should also work even when the polygons have holes in them, that is, there are polygons that define the holes. Such things are used in GIS to represent, for example, a lake with an island. But the boundaries of the polygons, holes or otherwise, should not intersect.
And one last tip, pay attention to defining the order in which the vertices of the polygons are given, for example, traveling through vertices in that order is the interior of the polygon on the right or the left? The answer should be same for all of the polygons including the holes (in which case the exterior of the hole is part of the interior of the polygon).
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms