Previous Topics:
- Convex Hull (Introduction)
- Convex Hull( Geometric Primitives)
- Convex Hull ( Geomatric Primitives-I)
- Convex Hull ( Geomatric Primitives-II)
Determining Whether a Point Is Inside a Complex Convex 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 even numbers 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.
Straight forward Rules:
(1)
In figure 1, we see that if we draw a line from +infinite to -infinite through point C, which intersect the line AB. You check just .In figure 2, we see that if we draw a line from +infinite to -infinite through point C, which does not intersect the line AB
(2) Now check, the position of point C with respect to line AB. (discuss it previous above paragraph).
(3) If there are an odd number of intersect points on each side of the test point C, then it is inside the polygon; if there are even numbers of intersect points on each side of the test point C, then it is outside the polygon.
Implementations:
Code in C++:
Graphical Implementation:
The question whether a point is contained within a polygon is a straight-forward one for us to answer visually. However, devising an algorithm that answers this question efficiently and covers most practical cases might still be a little difficult. A short and efficient algorithm named PNPoly has been described by W. Randolph Franklin.
Reference: Read More
Code in C++
Graphical Implementation:
Next Topics:
No comments:
Post a Comment