Below assignment is taken from here.


In this project, you will develop a geographic visualization of twitter data across the USA. You will need to use dictionaries, lists, and data abstraction techniques to create a modular program. Below assignment is phase 2 of this project. For reference, phase 1 of this project is available here.

Phase 2: The Geometry of Maps


We will use the position abstract data type to represent geographic latitude-longitude positions on the Earth. The data abstraction, defined at the top of geo.py, has the constructor make_position and the selectors latitude and longitude.

In this phase, you will write two functions that together determine the centers of U.S. states. The shape of a state is represented as a list of polygons. Some states (e.g. Hawaii) consist of multiple polygons, but most states (e.g. Colorado) consist of only one polygon (still represented as a length-one list).

Problem 6 (2 pt). Implement find_centroid, which takes a polygon and returns three values: the coordinates of its centroid and its area. The input polygon is represented as a list of position abstract data types, which are the consecutive vertices of its perimeter. The first vertex is always identical to the last.

The centroid of a two-dimensional shape is its center of balance, defined as the intersection of all straight lines that evenly divide the shape into equal-area halves. find_centroid returns the centroid and area of an individual polygon.

The formula for computing the centroid of a polygon appears on Wikipedia. The formula relies on vertices being consecutive (either clockwise or counterclockwise; both give the same answer), a property that you may assume always holds for the input.

When you complete this problem, the doctest for find_centroid should pass.

python3 trends.py -t find_centroid

Problem 7 (2 pt). Implement find_center, which takes a shape represented by a list of polygons and returns a position, its centroid.

The centroid of a collection of polygons can be computed by geometric decomposition. The centroid of a shape is the weighted average of the centroids of its component polygons, weighted by their area.

When you complete this problem, the doctest for find_center should pass.

python3 trends.py -t find_center

Once you are finished, draw_centered_map will draw the 10 states closest to a given state (including that state).

python3 trends.py -d CA

Below is the solution for phase 2:

from data import word_sentiments, load_tweets
from datetime import datetime
from doctest import run_docstring_examples
from geo import us_states, geo_distance, make_position, longitude, latitude
from maps import draw_state, draw_name, draw_dot, wait, message
from string import ascii_letters
from ucb import main, trace, interact, log_current_line
#Phase 2: The Geometry of Maps

def find_centroid(polygon):
    """Find the centroid of a polygon.


    polygon -- A list of positions, in which the first and last are the same

    Returns: 3 numbers; centroid latitude, centroid longitude, and polygon area

    Hint: If a polygon has 0 area, return its first position as its centroid

    >>> p1, p2, p3 = make_position(1, 2), make_position(3, 4), make_position(5, 0)
    >>> triangle = [p1, p2, p3, p1]  # First vertex is also the last vertex
    >>> find_centroid(triangle)
    (3.0, 2.0, 6.0)
    >>> find_centroid([p1, p3, p2, p1])
    (3.0, 2.0, 6.0)
    >>> find_centroid([p1, p2, p1])
    (1, 2, 0)
    total_value = 0
    for index in range(len(polygon) - 1):
        total_value += (latitude(polygon[index]) * longitude(polygon[index + 1])) - (latitude(polygon[index + 1]) * longitude(polygon[index]))
    area_of_polygon = total_value / 2
    if area_of_polygon == 0:
        return (latitude(polygon[0]), longitude(polygon[0]), 0) 
    total_value = 0
    for index in range(len(polygon) - 1):
        total_value += (latitude(polygon[index]) + latitude(polygon[index + 1])) * ((latitude(polygon[index])*longitude(polygon[index + 1])) - (latitude(polygon[index + 1])*longitude(polygon[index])))
    centroid_latitude = total_value / (6 * area_of_polygon)
    total_value = 0
    for index in range(len(polygon) - 1):
        total_value += (longitude(polygon[index]) + longitude(polygon[index + 1])) * ((latitude(polygon[index])*longitude(polygon[index + 1])) - (latitude(polygon[index + 1])*longitude(polygon[index])))
    centroid_longitude = total_value / (6 * area_of_polygon)
    if area_of_polygon < 0:
        return (centroid_latitude, centroid_longitude, -area_of_polygon)
        return (centroid_latitude, centroid_longitude, area_of_polygon)

def find_center(polygons):
    """Compute the geographic center of a state, averaged over its polygons.

    The center is the average position of centroids of the polygons in polygons,
    weighted by the area of those polygons.

    polygons -- a list of polygons

    >>> ca = find_center(us_states['CA'])  # California
    >>> round(latitude(ca), 5)
    >>> round(longitude(ca), 5)

    >>> hi = find_center(us_states['HI'])  # Hawaii
    >>> round(latitude(hi), 5)
    >>> round(longitude(hi), 5)
    centroid_and_area_of_all_polygons = []  
    for index in range(len(polygons)):
    sigma_Cix_Ai = 0    
    sigma_Ai = 0   
    sigma_Ciy_Ai = 0
    for index in range(len(centroid_and_area_of_all_polygons)):
        sigma_Cix_Ai += ((centroid_and_area_of_all_polygons[index])[0]) * ((centroid_and_area_of_all_polygons[index])[2])
        sigma_Ai     += (centroid_and_area_of_all_polygons[index])[2]  
        sigma_Ciy_Ai += ((centroid_and_area_of_all_polygons[index])[1]) * ((centroid_and_area_of_all_polygons[index])[2])
    return make_position(sigma_Cix_Ai/sigma_Ai, sigma_Ciy_Ai / sigma_Ai)

As per the instructions in the problem 6 & problem 7, the above solution is tested with this output:

enter image description here

Can I improve the solution? In particular, I was struggling with naming conventions.

  • 3
    \$\begingroup\$ Please be aware that the relevant word is "improve", not "improvise". They have entirely different meanings. Also, please do not use backticks for emphasis. They're specifically for code. \$\endgroup\$ – Jamal May 20 '15 at 14:12

A few notes about your code:

  • Whenever possible, try to use object-based loops instead of index-based loops. It makes the code cleaner and lowers the cognitive overhead. For example, turn this loop:

    centroid_and_area_of_all_polygons = [] 
    for index in range(len(polygons)):

    Into this one:

    centroid_and_area_of_all_polygons = [] 
    for polygon in polygons:

    You could even simplify this with the built-in function map:

    centroid_and_area_of_all_polygons = list(map(find_centroid, polygons))

    Or with a list comprehension:

    centroid_and_area_of_all_polygons = [find_centroid(polygon) for polygon in polygons]
  • The following piece of code:

    if area_of_polygon < 0:
        return (centroid_latitude, centroid_longitude, -area_of_polygon)
        return (centroid_latitude, centroid_longitude, area_of_polygon)

    ...would benefit from the built-in function abs:

    return (centroid_latitude, centroid_longitude, abs(area_of_polygon))
  • You are importing waaaayyyyy too many modules and features that you don't use. Please try to only include what you will use, it will make it simpler for you (and other people reading your code) to know what your code really relies on.


Riding on Morwenn's answer, here are a few things I'd change :

  • iterations are clearer, more efficient, more concise if you don't use the index.
  • use variable to store values that you are going to reuse multiple times
  • do not repeat yourself : the duplicated loop looks a bit suspicious.
  • use can use tuple unpacking to get the different elements composing a tuple (or any other iterable really)
  • use short yet meaningful variable names. For instance, centroid_and_area_of_all_polygons could become centroids, total_value does not convey much information, I'd rather see sum than sigma because 1) it is shorter, 2) it reminds of the sum builtin, 3) that's what the symbol sigma really means in a mathematical context
  • you do not need to create a list of centroids : you can simply iterate.

Taking these comments into account, here's how the code looks (not tested):

def find_centroid(polygon):
    """ Foobar """
    double_area, weighted_lat, weighted_long = 0, 0, 0
    for i in range(len(polygon) - 1): 
        p1, p2 = polygon[i], polygon[i+1]
        lat1, lat2, long1, long2 = latitude(p1), latitude(p2), longitude(p1), longitude(p2)
        weight = (lat1*long2) - (lat2*long1)
        double_area += weight
        weighted_lat += (lat1 + lat2) * weight
        weighted_long += (long1 + long2) * weight
    return (weighted_lat / (3 * double_area), weighted_long / (3 * double_area), abs(double_area / 2))
            if double_area else
            (latitude(polygon[0]), longitude(polygon[0]), 0)

def find_center(polygons):
    """ Foobar """
    sum_area, sum_lati_weight, sum_longi_weight = 0, 0, 0
    for p in polygons:
        lati, longi, area = find_centroid(p)
        sum_area += area
        sum_lati_weight += lati * area
        sum_longi_weight += longi * area
    return make_position(sum_lati_weight/sum_area, sum_longi_weight / sum_area)

Then, you could :

  • rewrite find_centroid to iterate over consecutive elements without using the index. You'll find various ways to do so.
  • use the sum builtin to compute sums but because you are computing many things in each iteration, it might be be worth it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.