placerequest.py

import urllib, json
from kmeans import kmean

AUTH_KEY = 'AIzaSyAG0fCOK8Qh9iODUjcK2TexVWVEBcw3MO4'


def FindRestaurants(origin, destination, newDirection=None):
		jsonData = FindDir(origin, destination)
		if (jsonData == "No Walking Path Found"):
			print(jsonData)
			return

		distance = jsonData["routes"][0]["legs"][0]["distance"]["value"]
		decodedPoly = decode(jsonData["routes"][0]["overview_polyline"]["points"])
		midPoint = decodedPoly[(int)(len(decodedPoly)/2)]
		radius = distance*(3/2)
		lat = midPoint[1]
		lng = midPoint[0]

		# run Google Places
		open_restaurants = GoogPlac(lat, lng, radius)
		latlong = []

		for restaurant in open_restaurants["results"]:
			latlong.append(PlaceDetails(restaurant["place_id"]))

		# doing k means clustering
		waypoints_limit = 23
		k = min(int(len(latlong)/3), waypoints_limit)
		centroids, clusters = kmean(latlong, k)
                return centroids

		# centroidString = ""
		# for centroid in centroids:
			# centroidString += str(centroid)+"|"
		# self.newDirection = NewDir(self.origin, self.destination, centroidString)


# find the shortest path between two points
def FindDir(origin, destination):
		MyUrl = ('https://maps.googleapis.com/maps/api/directions/json'
	           '?origin=place_id:%s'
	           '&destination=place_id:%s'
	           '&mode=walking'
	           '&key=%s') % (origin, destination, AUTH_KEY)
		#grabbing the JSON result
	  	response = urllib.urlopen(MyUrl)
	  	jsonRaw = response.read()
	  	jsonData = json.loads(jsonRaw)
	  	status = str((jsonData["status"]))
	  	no_results = "ZERO_RESULTS"
	  	if (status == no_results):
	  		return ("No Walking Path Found")
	  	return jsonData

# decode polyline
def decode(point_str):
    '''Decodes a polyline that has been encoded using Google's algorithm
    http://code.google.com/apis/maps/documentation/polylinealgorithm.html

    This is a generic method that returns a list of (latitude, longitude)
    tuples.

    :param point_str: Encoded polyline string.
    :type point_str: string
    :returns: List of 2-tuples where each tuple is (latitude, longitude)
    :rtype: list

    '''

    # sone coordinate offset is represented by 4 to 5 binary chunks
    coord_chunks = [[]]
    for char in point_str:

        # convert each character to decimal from ascii
        value = ord(char) - 63

        # values that have a chunk following have an extra 1 on the left
        split_after = not (value & 0x20)
        value &= 0x1F

        coord_chunks[-1].append(value)

        if split_after:
                coord_chunks.append([])

    del coord_chunks[-1]

    coords = []

    for coord_chunk in coord_chunks:
        coord = 0

        for i, chunk in enumerate(coord_chunk):
            coord |= chunk << (i * 5)

        #there is a 1 on the right if the coord is negative
        if coord & 0x1:
            coord = ~coord #invert
        coord >>= 1
        coord /= 100000.0

        coords.append(coord)

    # convert the 1 dimensional list to a 2 dimensional list and offsets to
    # actual values
    points = []
    prev_x = 0
    prev_y = 0
    for i in xrange(0, len(coords) - 1, 2):
        if coords[i] == 0 and coords[i + 1] == 0:
            continue

        prev_x += coords[i + 1]
        prev_y += coords[i]
        # a round to 6 digits ensures that the floats are the same as when
        # they were encoded
        points.append((round(prev_x, 6), round(prev_y, 6)))

    return points

# Get all the restaurants currently open within specified radius
def GoogPlac(lat,lng,radius):
	  LOCATION = str(lat) + "," + str(lng)
	  RADIUS = radius
	  MyUrl = ('https://maps.googleapis.com/maps/api/place/nearbysearch/json'
	           '?location=%s'
	           '&radius=%s'
	           '&types=restaurant'

	           '&key=%s') % (LOCATION, RADIUS, AUTH_KEY)

	  #grabbing the JSON result
	  response = urllib.urlopen(MyUrl)
	  jsonRaw = response.read()
	  jsonData = json.loads(jsonRaw)
	  return jsonData

# get place details
def PlaceDetails(placeid):
		PLACEID = placeid
		MyUrl = ('https://maps.googleapis.com/maps/api/place/details/json'
				'?placeid=%s'
				'&key=%s') % (PLACEID, AUTH_KEY)
		#grabbing the JSON result
	  	response = urllib.urlopen(MyUrl)
	  	jsonRaw = response.read()
	  	jsonData = json.loads(jsonRaw)
	  	return jsonData["result"]["geometry"]["location"]["lat"], jsonData["result"]["geometry"]["location"]["lng"]

# calculate new directions with waypoints
def NewDir(origin, destination, centroidString):
	MyUrl = ('https://maps.googleapis.com/maps/api/directions/json'
	           '?origin=place_id:%s'
	           '&destination=place_id%s'
	           '&mode=walking'
	           '&waypoint=optimize:true|%s'
	           '&key=%s') % (origin, destination, centroidString, AUTH_KEY)
	#grabbing the JSON result
  	response = urllib.urlopen(MyUrl)
  	jsonRaw = response.read()
  	jsonData = json.loads(jsonRaw)
  	status = str((jsonData["status"]))
  	no_results = "ZERO_RESULTS"
  	if (status == no_results):
  		return ("No Walking Path Found")
  	return jsonData


# print type(FindRestaurants('ChIJKcBHSE7GxokR8DA8BOQt8w4', 'ChIJjUMwJ1fGxokREkNf5LXR_Ak').newDirection)

# print PlaceDetails('ChIJKcBHSE7GxokR8DA8BOQt8w4')

route.js

from collections import namedtuple
from geopy import Point, distance

API_KEY = 'AIzaSyCeo86HIGUtpWaPOpOA6pbNQhHDe3-26ko'
MAX_STEPS = 5

FROM = (40.728833, -74.000852)
TO = (40.735012, -73.979333)
MOCKED_WAYPOINTS = [((40.72223320000001, -73.9874291), 4),
                    ((40.7324849, -74.00259299999999), 7),
                    ((40.7356354, -74.006691), 9),
                    ((40.742975, -73.98927599999999), 3),
                    ((40.73139849999999, -74.0024617), 4),
                    ((40.73686, -73.991384), 2),
                    ((40.7290258, -73.98712069999999), 6),
                    ((40.7327507, -74.0029358), 5)]


class Waypoint(namedtuple('Waypoint', 'pt area')):
    def closest(self, graph):
        valid_nodes = self.closer_nodes(graph)
        best_dist = None
        best = None
        for other in valid_nodes:
            dist = distance.distance(self.pt, other.pt).meters
            if not best_dist or dist < best_dist:
                best_dist = dist
                best = other
        return best

    def closer_nodes(self, graph):
        lats = sorted([self.area[0].latitude, self.area[1].latitude])
        lngs = sorted([self.area[0].longitude, self.area[1].longitude])

        def within(pt):
            return ((lats[0] <= pt.latitude <= lats[1]) and
                    (lngs[0] <= pt.longitude <= lngs[1]))

        nodes = [node for node in graph if within(node.pt)]
        return nodes


def best_path(nodes, origin, dest):
    # I'll convert my own damn parameters.
    nodes = [Point(lat, lng) for lat, lng in nodes]
    origin = Point(origin)
    dest = Point(dest)

    waypoints = [Waypoint(origin, (origin, dest))]
    for node in nodes:
        waypoints.append(Waypoint(node, (origin, dest)))
    to = Waypoint(dest, (origin, dest))
    waypoints.append(to)

    start, remaining = waypoints[0], waypoints[1:]
    path = []
    for i in range(MAX_STEPS):
        closer = start.closest(remaining)
        if closer is None:
            break
        path.append(closer)
        remaining = [pt for pt in remaining if pt != closer]
        start = closer

    # check to see if destination is in path
    if to in path:
        path.remove(to)
    return '|'.join(["{},{}".format(pt.pt.latitude, pt.pt.longitude) for pt in path])


def main():
    lat_longs = [Point(pt[0]) for pt in MOCKED_WAYPOINTS]
    path = best_path(lat_longs, Point(FROM), Point(TO))
    print(path)

if __name__ == '__main__':
    main()

views.py

from flask import render_template, make_response, request, current_app, jsonify
from app import app
import route
from placerequest import *

@app.route('/')
def index():
	return render_template('index.html', title="PopMap")

@app.route('/_search1', methods=['GET'])
def search1():
	origin = request.args.get('origin', "", type=str)
	destination = request.args.get('destination', "", type=str)

	originGeo = PlaceDetails(origin)
	destinationGeo = PlaceDetails(destination)

        restaurants = FindRestaurants(origin, destination)
        waypoints = route.best_path(restaurants, originGeo, destinationGeo)
        print 'waypoints: ' + str(waypoints)
        directions = NewDir(origin, destination, waypoints)
        print 'directions: ' + str(directions)

	return jsonify(directions)

@app.route('/_search2', methods=['GET'])
def search2():
	origin = request.args.get('origin', "", type=str)
	destination = request.args.get('destination', "", type=str)
	direction = FindRestaurants(origin, destination)

	return jsonify(FindRestaurants(origin, destination).newDirection)