Point in Polygon

Hide text Hide pseudo-code

Use the point in polygon -algorithm to find out whether the given points, numbered 1-4, are inside or outside the given polygon. The algorithm examines the number of times a half line drawn from a given point intersects the polygon.

For points 1 and 2, draw the half lines, count and mark the number of intersections and finally answer whether the point is inside or outside the polygon. Mark your answer in the pull-down menu.

For points 3 and 4, the number of intersections are given. Therefore, only answer whether the points are inside the polygon or not.

POINT_IN_POLYGON(Polygon p, Point q)
1. count = 0
2. let line l be a ray starting from q and 
   parallel to the positive x-axis
3. for each edge e in p
4.   if l intersects e
5.       increment count
6. if count is odd
7.   return true
8. else
9.   return false

  Created Fri Oct 30 13:52:47 EET 2009 - Powered by SVG-hut