CEGE0096: Point-in-Polygon Test
1st Assignment (50%)
In this assignment you will apply your programming knowledge to the practical
problem of determining whether a point lies inside or outside a polygon, which
is a fundamental operation of a Geographic Information System (GIS). The
point-in-polygon (PiP) problem is illustrated in Fig. 1. In this figure, the grey
area represents a polygon. The red points lie outside the polygon, the green
points lie inside, and the blue points like on the boundary. Visually, this is easy
to see, however, it is not so straightforward to determine computationally.
Figure 1: Example of PiP problem.
The procedure for PiP that you will use involves two steps:
1. Test if the point is inside the minimum bounding rectangle (MBR) of the
2. If it is, use PiP algorithm to test whether the point is inside the polygon.
These steps are introduced in turn in the following sections.
2 The Minimum Bounding Rectangle Algorithm
PiP is a computationally intensive operation. Therefore, it is common to first
get the MBR of a polygon and test whether the point lies inside this rectangle.
For the purposes of this assignment, the MBR can be found by simply taking
the minimum and maximum of both coordinates of the the polygon. If a given
point lies outside this rectangle, then it is definitely outside the polygon and
there is no need to proceed to the full PiP algorithm. This is shown graphically
in Fig. 2.
Figure 2: Example of MBR.
In Fig. 2, we can see that the MBR correctly categorises the top-left point
as outside the polygon, but incorrectly categorises some of the other points.
Therefore, it is necessary to use a more sophisticated algorithm to determine
whether the other points lie inside or on the boundary of the polygon.
3 The Point-in-Polygon Algorithm
There are two commonly used PiP algorithms; the ray casting algorithm (RCA)
and the winding number algorithm (WNA). In this assignment you are asked
to implement the RCA.
The Ray Casting Algorithm. The RCA involves drawing a straight line
(in any direction) from the test point, and counting how many times it crosses
the boundary of the polygon. If the line crosses the boundary an odd number of
times then the point lies inside the polygon. If the line crosses the boundary an
even number of times then the point lies outside the polygon. This is depicted
graphically in Fig.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:itcsdx