Little tool to map gps coordintates to states

gps2state.py

from __future__ import division

import json


def is_counterclockwise(a, b, c):
    """Check if three points are sorted counterclockwise.

    See http://jeffe.cs.illinois.edu/teaching/373/notes/x05-convexhull.pdf
    for more info."""

    # this is the determinant of the following matrix
    # | 1  a[0]  a[1] |
    # | 1  b[0]  b[1] |
    # | 1  c[0]  c[1] |
    det = (c[1] - a[1]) * (b[0] - a[0]) - (b[1] - a[1]) * (c[0] - a[0])
    return det


def is_intersection((a, b), (c, d)):
    """Check if there is an intersection between segment of points (a, b)
    and segments of points (c, d).

    See http://jeffe.cs.illinois.edu/teaching/373/notes/x06-sweepline.pdf
    for more info."""
    acd = is_counterclockwise(a, c, d)
    bcd = is_counterclockwise(b, c, d)
    abc = is_counterclockwise(a, b, c)
    abd = is_counterclockwise(a, b, d)

    # print (acd, bcd, abc, abd)

    if acd == bcd == abc == abd == 0:
        # overlapping lines
        return True
    if (acd > 0) == (bcd > 0):
        return False
    if (abc > 0) == (abd > 0):
        return False
    else:
        return True


class State(object):
    def __init__(self, name, coords):
        self.name = name
        self.sides = zip(coords, coords[1:] + coords[:1])

    def in_state(self, (x, y)):
        """Calculate if point (x, y) is in state)"""
        test_line_a, test_line_b = ((-180.0, y), (x, y)), ((x, y), (180.0, y))
        inter_a = inter_b = 0
        for side in self.sides:
            int_a = is_intersection(test_line_a, side)
            int_b = is_intersection(test_line_b, side)
            inter_a += 1 if int_a else 0
            inter_b += 1 if int_b else 0

        return (inter_b % 2) or (inter_a % 2)


def get_states(path):
    with file(path) as f:
        states_coord = json.load(f)

    states = {
        name: State(name, coord) for name, coord in states_coord.iteritems()}
    return states