Spring 2019
We'll first spend quite a bit of time setting up Python graphics algorithms to figure out which region we are in. We'll start by writing a bounding-box algorithm, then a point-in-polygon algorithm, and finally we'll use point-in-polygon and our GPS coordinates to figure out which region of campus we're in. To finish it all up, you'll then generate a Python script using these functions that will live on the class server an allow web-based conversion of GPS coordinates to campus locations using GET requests. We'll expand this latter functionality significantly next week.
Run Python's IDLE. Edit the code in the IDLE editor, use Run Module (F5) to run the code. The upside is that almost all installs of Python have IDLE, and that once you run your code you have access to the variables in memory, which you can access in the interactive shell, thus making debugging a bit easier. The downside is that IDLE is not a very powerful IDE, and the Python shell is itself a bit cumbersome.
Edit your code in a better text editor, like Sublime Text, Atom, vim, emacs, or whatever you want. Save the file with the extension .py, and then in the command line, type python -i myfile.py
where myfile is replaced by your filename. This is super simple, and you can use a great IDE.
Edit your code in a better text editor. Save the file with the extension .py, and then at the command line run python
to go into python interactive mode. Then type import myfile.py
, which will try to import all the variables, functions, and classes defined in myfile.py.
Choose one and use it for today.
Geofencing is an arguably popular application of interconnected embedded systems. For example, your Nest thermostat can start warming up your house when your cell phone's GPS sensor reports that you are nearing the house. Or a bakery sends you an ad on Facebook if you wander within 1 mile of their store. For this 6.08 application, our geofencing app will use the labkit (a wearable) to report where you're at and discretize that into MIT campus locations.
A number of interesting computer graphics algorithms arise in geofencing. One is to determine if we are in a certain region of campus. As a first step, imagine we want to know if we are on-campus or off-campus, and we consider campus to be a rectangle. We represent the rectangle as a Python list of four vertices.
How do we know whether this point is within this rectangle? One simple (and quick) way is to see if our point's x-coordinate is less than the maximum x-coordinate and greater than the minimum x-coordinate of all the vertices, and similarly for the y-coordinate(s) of the point and the rectangle. This is a bounding-box test.
Our first task is to write a function known as bounding_box
that implements this algorithm. The function should take in a tuple point_coord
representing the x-y coordinates of the point of interest and a list box
that contains the coordinates (also tuples) of the four corners of the box. The function should return True
if point_coord
is in the box, and False
otherwise.
Does the order of the coordinates for the rectangle matter?
Write your code and make up some test cases (create a simple rectangle and try different point locations). For this code block, do not make any assumptions about the order of the corners in the box
list!!
sign
shown below might be helpful for you to use, if you wish. def sign(x): if x > 0: return 1 elif x == 0: return 0 else: return -1
The bounding box test is fast and simple, and one can show that if the point is not in the bounding box it is also not within any polygon inscribed within the bounding box. When checking for whether a point is in one of many arbitrary polygons, it is advantageous to first do a bounding-box test to quickly remove irrelevant polygons. This is common in the graphics community. For example, if someone wanted to see if a bunch of bouncing balls were colliding, this would be a good test to start with.
However, representing MIT's campus as a rectangle is quite limited, so we move on to allowing for more complex shapes.
We can make things a bit more sophisticated by allow the campus regions to be represented as a set of polygons. A convex polygon is a polygon where all interior angles are less than 180 degrees, while a non-convex polygon allows for interior angles > 180 degrees. Here are examples of convex and non-convex polygons
This allows for a more accurate representation of campus, shown below:
To determine if we are in a polygon, we use a different algorithm, known as the crossings test or the Jordan Curve Theorem. From our starting point, we construct a line going to x = +\infty. We count how many edges we cross. If we cross an odd number of edges, we are inside the polygon. If we cross an even number, we are outside the polygon.
Here is the outline of our algorithm:
First, translate the point (and polygon vertices) so that the point is at the origin (shown in Figure 5 above). This will make the math easier and more generalized.
Go through each edge (two adjacent vertices), and check if the two y-coordinates differ in sign. For the polygon above, edges e1 and e4 cross the x-axis. All other edges are ignored. We can assume that the polygon vertices are provided in an ordered fashion, i.e., two adjacent vertices constitute an edge. In particular, in the function below, the vertices will be provided as a list of tuples.
For edges that crosses the x-axis:
See if the x-coordinates of the edge vertices are both positive. This is the case for e1, for which v1_x = 3 and v2_x = 7. If so, then the edge and our ray intersect. Incremenent the number of crossed edges by 1.
If both x-coordinates are negative (as for e4), then we don't intersect, go to the next edge.
If the x-coordinates differ in sign, then we might intersect. Here we need to compute the actual x-axis intersection point and, if it is positive, increment the number of crossed edges by 1. Below is an example of such a situation, where e6 intersects the ray and e7 does not:
Else go on to the next edge.
Determine whether we have an even or odd number of crossings. The point is inside if there is an odd number of crossings.
An important part of the algorithm is computing the intersection point between the following ray and edge, the formula for which is given by:
Develop the function for within_area
. Think of some good test cases and test your code locally. (Do not use Python 2. 2008 was eleven years ago, you can use Python 3 now.) For example, create a convex and a concave polygon and test various points. Make sure to include a point that will test the situation where you have to explicitly compute the intersection point. When you're done, copy-paste the function into the checker.
With your point in polygon function working, we next need to figure out, given a location, which campus region we're in. We are going to hold the campus regions in a dictionary:
locations={ "Student Center":[(-71.095863,42.357307),(-71.097730,42.359075),(-71.095102,42.360295),(-71.093900,42.359340),(-71.093289,42.358306)], "Dorm Row":[(-71.093117,42.358147),(-71.092559,42.357069),(-71.102987,42.353866),(-71.106292,42.353517)], "Simmons/Briggs":[(-71.097859,42.359035),(-71.095928,42.357243),(-71.106356,42.353580),(-71.108159,42.354468)], "Boston FSILG (West)":[(-71.124664,42.353342),(-71.125737,42.344906),(-71.092478,42.348014),(-71.092607,42.350266)], "Boston FSILG (East)":[(-71.092409,42.351392),(-71.090842,42.343589),(-71.080478,42.350900),(-71.081766,42.353771)], "Stata/North Court":[(-71.091636,42.361802),(-71.090950,42.360811),(-71.088353,42.361112),(-71.088267,42.362476),(-71.089769,42.362618)], "East Campus":[(-71.089426,42.358306),(-71.090885,42.360716),(-71.088310,42.361017),(-71.087130,42.359162)], "Vassar Academic Buildings":[(-71.094973,42.360359),(-71.091776,42.361770),(-71.090928,42.360636),(-71.094040,42.359574)], "Infinite Corridor/Killian":[(-71.093932,42.359542),(-71.092259,42.357180),(-71.089619,42.358274),(-71.090928,42.360541)], "Kendall Square":[(-71.088117,42.364188),(-71.088225,42.361112),(-71.082774,42.362032)], "Sloan/Media Lab":[(-71.088203,42.361017),(-71.087044,42.359178),(-71.080071,42.361619),(-71.082796,42.361905)], "North Campus":[(-71.11022,42.355325),(-71.101280,42.363934),(-71.089950,42.362666),(-71.108361,42.354484)], "Technology Square":[(-71.093610,42.363157),(-71.092130,42.365837),(-71.088182,42.364188),(-71.088267,42.362650)] }
Here are those polygons rendered onto maps of the MIT area.
You see that right now we have a bunch of polygons defining regions on campus. Write a function get_area
that, given a point defined by point_coord
(which is a tuple of the form (lon
, lat
)), determines whether you are in any of the regions in our dictionary. If you are in one of the regions, return the name of the region (e.g. "Kendall Square") and if not, return "Outside MIT". Try to develop get_area
on your machine. Think of some good test cases and test your code locally.
For the checker below, you can assume that a functioning within_area
already exists.
As a final part in today's lab, bring all of the code that you wrote together and place it in a location on 608dev.net so that when a user provides the query arguments lat
and lon
in Decimal Degree Format the system will return the region within MIT's campus it refers to (or outside if that's the case).
In case you'd like to spread your functionality over multiple python files when on the server, there's a bit of extra syntax you need to use in order to make it work happily in our sandboxed environment.
Well let's say we have two folders in our home directory on the server: joe1
and joe2
. joe1
will hold a file called hey.py
which will have a request_handler
function definition and is therefore meant to be visited through the browser. The second folder, joe2
will hold a second function in a file called funstuff.py
that we'll want to use in our request_handler
function in hey.py
. To be more specific, let's say funstuff.py
contains the following:
def cool(): return "HI THERE. Learning is unironically fun!!"
We can get access to the function above in hey.py
by writing it like the following:
import sys sys.path.append('__HOME__/joe2') from funstuff import cool def request_handler(request): return cool()
We import sys
, and then append to our Python path the location of our other directory of interest, using the __HOME__
tag that will be interpretted by ther server. So there fore when you go and visit the http://608dev.net/sandbox/sc/your_kerberos/joe1/hey.py
you'll get HI THERE. Learning is unironically fun!!
as a response. Imagine what you could do with code that actually contributes to society rather than just this toy example we've provided! The possibilities are endless.
If you get done early, consider working on Exercise 04 since that exists and is a thing. Also consider doing a design exercise.
944c002
).\ / /\__/\ \__=( o_O )= (__________) |_ |_ |_ |_Course Site powered by CAT-SOOP 14.0.4.dev5.