Lab 04b: Geofencer
If you are a current student, please Log In for full access to the web site.
Note that this link will take you to an external site (https://oidc.mit.edu) to authenticate, and then you will be redirected back to this page.
Goals:
In the next few labs we will use our GPS unit and serverside code to do geofencing and let you know how many classmates are in the same part of campus as you. Today we'll focus on developing the bulk of the serverside script necessary for most of the functionality. Next week we'll complete the rest.1) BigPicture and Today
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 boundingbox algorithm, then a pointinpolygon algorithm, and finally we'll use pointinpolygon 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 webbased conversion of GPS coordinates to campus locations using GET requests. We'll expand this lat functionality significantly next week.
1.1) Geofencing Overview
Geofencing is a 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.
2) Graphics algorithms
2.1) Are we in a box?
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 oncampus or offcampus, 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 xcoordinate is less than the maximum xcoordinate and greater than the minimum xcoordinate of all the vertices, and similarly for the ycoordinate(s) of the point and the rectangle. This is a boundingbox 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 xy 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?
2.2) Local debugging
It's good practice to learn how to debug your code locally rather than on the tutor. Why? Because in real life you won't have access to the online tutor, so if you want to learn to program you need to have a local system you can use. Here are three ways to go about it:
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 try it out for today. Write your code and make up some test cases (create a simple rectangle and try different point locations). Do not make any assumptions about the order of the corners in box
.
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
2.3) Are We in a Polygon?
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 polygons, it is advantageous to first do a boundingbox 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 nonconvex polygon allows for interior angles >180 degrees. Here are examples of convex and nonconvex 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.

Go through each edge (two adjacent vertices), and check if the two ycoordinates differ in sign. For the polygon above, edges e1 and e4 cross the xaxis. 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.

For edges that crosses the xaxis:

See if the xcoordinates 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 xcoordinates are negative (as for e4), then we don't intersect, go to the next edge.

If the xcoordinates differ in sign, then we might intersect. Here we need to compute the actual xaxis 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. 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, copypaste the function into the checker.
Show your working codes to a staff member. Be prepared to explain your algorithms in detail.
3) Are we in the Area?
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.
4) Put It On The Server
As a final part in today's lab, bring all of the code that you wrote together and place it in a location on iescs1.mit.edu 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).
Show your working serverside script (via the browser) to a staff member. Be prepared to explain your algorithms in detail.
If you get done early, consider working on Exercise 04 since that exists. Also consider doing a design exercise.