Lab 04b: Geofencer

The questions below are due on Tuesday February 27, 2018; 08:25:00 PM.


Partners: You have not yet been assigned a partner for this lab.
You are not logged in.

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.

Don't Fence Me In

 

Goals:

In the next few labs we will use our GPS unit and server-side 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 server-side script necessary for most of the functionality. Next week we'll complete the rest.

1) Big-Picture 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 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 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 on-campus or off-campus, and we consider campus to be a rectangle. We represent the rectangle as a Python list of four vertices.

Think inside the box.

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.

What if the point is on an edge? While this issue could arise in a coarsely discretzed system (like your screen), it is highly unlikely to arise in the real world of GPS coordinates, which have 8 digits of precision. Your code could either assume that such points are inside or are outside, depending on the inequality you create.

Try Now:

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:

  1. 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.

  2. 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.

  3. 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.

Note that a function like 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

def bounding_box(point_coord,box): pass # Your code here

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 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

Convex and Non-Convex Polygons.

This allows for a more accurate representation of campus, shown below:

Our humble campus subdivided into polygons.

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.

Odd = Inside, Even = Outside. If you ignore the "side", each pair has the same number of vowels!

Here is the outline of our algorithm:

Translate the point (and potential surrounding shape) to the origin.

  • 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 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.

    • 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:

p = \frac{x_1 y_2 - y_1 x_2}{y_2 - y_1}

An illustration of the intersection of a ray and edge.

As for the bounding box, we have some edge cases here, literally. What if the ray intersects a vertex, or is coincident with an edge (and thus with two vertices)? Again, for our applications these isues are highly unlikely to occur, but for cases where they can occur there are accepted ways of setting up the algorithm to accomodate those possibilities. You can find a nice discussion of these issues and point-in-polygon algorithms in general here and here.

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, copy-paste the function into the checker.

def within_area(point_coord,poly): pass #Your code here

Checkoff 1:
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)]
}

In Lab 04A we used the degree decimal minutes (DDM) representation of location. Now that we are going to do math, we want to use the decimal degree (DD) representation of location. So locations will look like "42.359163, -71.091826" rather than "42 21.54978, -71 5.50956". For next week, don't worry. We'll use a library to fix that issue on our embedded system.

Here are those polygons rendered onto maps of the MIT area.

MIT as polygons! MIT as polygons!

The polygons zoomed out.

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.

def get_area(point_coord,locations): pass #Your code here

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 iesc-s1.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).

Checkoff 2:
Show your working server-side 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.