Lab 04a: Geofencer

Spring 2019

The questions below are due on Tuesday February 26, 2019; 10:00: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. On Thursday we'll finish the job.

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 latter functionality significantly next week.

1.1) 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, nor does the universe just give you test cases which you can ask on Piazza about, so if you want to improve your programming chiops, 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 use it for today.

1.2) Geofencing Overview

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.

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.

Check Yourself:

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

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

Convex and Non-Convex Polygons.

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

Our humble campus represented as a polygon.

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

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

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 03B 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 lab on Thursday, 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 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).

Checkoff 2:
Show your working server-side script (via the browser) to a staff member. Be prepared to explain your algorithms in detail and test it using a location (pluck one from the query values which appear when you move around on a Google map.

4.1) Multiple Files on the Server (OPTIONAL)

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

Note that when importing files into other files, they must live within a subdirectory of your home directory, not in directly in the home directory. So don't try to just append the path "HOME".

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.



This page was last updated on Tuesday February 26, 2019 at 03:05:41 PM (revision 944c002).
 
Course Site powered by CAT-SOOP 14.0.4.dev5.
CAT-SOOP is free/libre software, available under the terms
of the GNU Affero General Public License, version 3.
(Download Source Code)
CSS/stryling from the Outboxcraft library Beauter, licensed under MIT
Copyright 2017