Python代写：CEGEG082 Point in Polygon

发表于   |   分类于

代写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 1. 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:

  1. Test if the point is inside the minimum bounding rectangle of the polygon.
  2. 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:

  1. Reads in a list of x, y coordinates from a .csv file and creates a polygon object from them.
  2. Creates a point object for testing.
  3. Tests whether the point is inside the polygon and returns “Inside” or “Outside”.
  4. 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):

1
2
3
4
5
6
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

  1. Successfully implement the minimum bounding rectangle - 15 marks
  2. Successfully implement either the ray casting or winding number algorithm (or any other PIP algorithm you may find) - 15 marks

Additional marks

  1. Make your code object oriented - Max 25 marks
  2. 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
  3. Plotting of points and polygons with appropriate axis labels and annotations - Max 5 marks
  4. Successfully deal with special cases in your PIP algorithm - Max 10 marks
  5. Incorporate some simple error handling functionality - Max 10 marks
  6. 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!