Có các vấn đề mình cần lưu ý khi cài đặt thuật toán:
- Điểm đó nằm trên cạnh.
- Điểm đó trùng với một điểm của đa giác.
Nguồn :
http:// alienryderflex .com/ polygon/
Point-In-Polygon Algorithm
Figure 1
Figure 1 demonstrates a typical case of a severely concave polygon with 14 sides. The red dot is a point which needs to be tested, to determine if it lies inside the polygon.
The solution is to compare each side of the polygon to the Y (vertical) coordinate of the test point, and compile a list of
nodes, where each node is a point where one side crosses the Y threshold of the test point. In this example, eight sides of the polygon cross the Y threshold, while the other six sides do not. Then, if there are an
odd number of nodes on each side of the test point, then it is inside the polygon; if there are an
even number of nodes on each side of the test point, then it is outside the polygon. In our example, there are five nodes to the left of the test point, and three nodes to the right. Since five and three are odd numbers, our test point is inside the polygon.
(Note: This algorithm does not care whether the polygon is traced in clockwise or counterclockwise fashion.)
Figure 2
Figure 2 shows what happens if the polygon crosses itself. In this example, a ten-sided polygon has lines which cross each other. The effect is much like “exclusive or,” or XOR as it is known to assembly-language programmers. The portions of the polygon which overlap cancel each other out. So, the test point is outside the polygon, as indicated by the even number of nodes (two and two) on either side of it.
Figure 3
In Figure 3, the six-sided polygon does not overlap itself, but it does have lines that cross. This is not a problem; the algorithm still works fine.
Figure 4
Figure 4 demonstrates the problem that results when a vertex of the polygon falls directly on the Y threshold. Since sides
a and
b both touch the threshold, should they both generate a node? No, because then there would be two nodes on each side of the test point and so the test would say it was outside of the polygon, when it clearly is not!
The solution to this situation is simple. Points which are exactly on the Y threshold must be considered to belong to one side of the threshold. Let’s say we arbitrarily decide that points on the Y threshold will belong to the “above” side of the threshold. Then, side
a generates a node, since it has one endpoint below the threshold and its other endpoint on-or-above the threshold. Side
b does not generate a node, because both of its endpoints are on-or-above the threshold, so it is not considered to be a threshold-crossing side.
Figure 5
Figure 5 shows the case of a polygon in which one of its sides lies entirely on the threshold. Simply follow the rule as described concerning Figure 4. Side
c generates a node, because it has one endpoint below the threshold, and its other endpoint on-or-above the threshold. Side
d does not generate a node, because it has both endpoints on-or-above the threshold. And side
e also does not generate a node, because it has both endpoints on-or-above the threshold.
Figure 6
Figure 6 illustrates a special case brought to my attention by John David Munch of Cal Poly. One interior angle of the polygon just touches the Y-threshold of the test point. This is OK. In the upper picture, only one side (hilited in red) generates a node to the left of the test point, and in the bottom example, three sides do. Either way, the number is odd, and the test point will be deemed inside the polygon.
Polygon Edge
If the test point is on the border of the polygon, this algorithm will deliver unpredictable results; i.e. the result may be “inside” or “outside” depending on arbitrary factors such as how the polygon is oriented with respect to the coordinate system. (That is not generally a problem, since the edge of the polygon is infinitely thin anyway, and points that fall right on the edge can go either way without hurting the look of the polygon.)