代写Graphics相关算法，判断二维平面上的点，是否属于某个Polygon中。
Python Coursework: Point in Polygon
In this coursework 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 GISystem. Your work will build upon the point,
polygon and geometry examples that were introduced in the practical sessions
and assignments. The point in polygon (PIP) problem is illustrated in figure
- In the picture, the green area represents a polygon. The red points lie
outside the polygon and the blue points lie inside. Visually, this is easy to
see, however, it is not so straightforward to determine this computationally.
The procedure for PIP that you will use involves two steps: - Test if the point is inside the minimum bounding rectangle of the polygon.
- If it is, use a PIP algorithm to test whether the point is inside the polygon.
These steps are introduced in turn in the following sections.
Minimum bounding rectangle
PIP is a computationally intensive operation. Therefore, it is common to first
get the minimum bounding rectangle (MBR, alternatively minimum bounding box)
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 x and y coordinates of a polygon (a smaller rectangle may be found
by rotating the coordinate system). 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 figure 2,
where the red box is the MBR.
It can be seen that the MBR correctly identifies the red point as outside the
polygon, but incorrectly identifies one of the blue points as inside.
Therefore, it is necessary to use a more sophisticated algorithm to determine
whether the blue points do indeed lie inside the polygon.
The point in polygon algorithm
There are two commonly used PIP algorithms; the ray casting algorithm and the
winding number algorithm. The ray casting algorithm is introduced here as it
is conceptually simpler, but you are free to use the winding number algorithm
in your submission if you wish.
The ray casting algorithm
The ray casting algorithm 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 figure 3.
Special case
There is a situation where the ray casting algorithm may produce inconsistent
results. If the ray passes through a vertex (point) on the polygon boundary,
it will count as crossing the boundary twice. The problem with this is shown
graphically in figure 4.
The top ray passes through the vertex and two crosses are counted. However,
the ray continues inside the polygon, and when it passes out again, the
algorithm wrongly identifies the point as inside. The bottom ray, again,
passes through the vertex and two crosses are counted, however, it continues
outside the polygon and the point is correctly identified as outside.
Instructions
To complete this coursework, you will build on the point, polygon and geometry
classes that you created in the fourth Python tutorial. Your task is to create
a Python script that does the following:
- Reads in a list of x, y coordinates from a .csv file and creates a polygon object from them.
- Creates a point object for testing.
- Tests whether the point is inside the polygon and returns “Inside” or “Outside”.
- Plots the point and polygon in a plot window.
Your control flow for step three may be something like this (note that this is
pseudocode and is not intended to be run in Python):
if point is not in MBR: # Test if the point is inside the MBR
print “Outside” # Print outside if True
elif point is in polygon: # Test if point is inside polygon using the ray casting algorithm
print “Inside” # Print inside if true
else
print “Outside” # Print outside if false
—|—
You will get additional marks if you make your code object oriented. As an
example, you may notice from the pseudocode above that the PIP operation
involves checking the MBR and then running the ray casting algorithm in
separate steps. Although the MBR is used in the PIP operation, it may have
other uses outside PIP, and therefore should be accessible without running the
PIP operation directly. Similarly, there may be other uses for the ray casting
algorithm other than PIP. You should try and implement this kind of thinking
throughout your code as much as possible.
There is a wealth of information on how to implement the PIP algorithm online.
You are free to adapt code from online sources to work with your data and
classes. If you do, any code you use should be referenced in the comments of
your code with a URL and author and date (if available). Do not simply copy
and paste code verbatim.
The mark scheme is as follows (total of 100)
Core marks
- Successfully implement the minimum bounding rectangle - 15 marks
- Successfully implement either the ray casting or winding number algorithm (or any other PIP algorithm you may find) - 15 marks
Additional marks
- Make your code object oriented - Max 25 marks
- Comment your code clearly so that it can be easily understood and used by others and use a clear and consistent naming scheme. You should clearly explain what each line of code in the algorithm is doing - Max 10 marks
- Plotting of points and polygons with appropriate axis labels and annotations - Max 5 marks
- Successfully deal with special cases in your PIP algorithm - Max 10 marks
- Incorporate some simple error handling functionality - Max 10 marks
- Creativiy: 10 additional marks are available for adding features that are not specified.
Evaluation
To help you build your program, you will be supplied with a .csv file
containing the coordinates of a polygon, and several test points. You can use
these to test whether your PIP algorithm works. Your work will be assessed
using a separate, unseen polygon and set of points. The polygon will be in the
same format.
Submission
Completed scripts should be submitted as Python (.py) files to the course
Moodle page using a facility under the materials for week 10.
NOTE: An element of collaborative work is allowed but PLEASE DO NOT SUBMIT
SCRIPTS THAT ARE IDENTICAL TO ONE ANOTHER. For example, in the past we have
had submissions with students referring to a directory on their friend’s
computer. This is unacceptable!
