def cover_region_s2(location1,location2):
    rc = RegionCoverer()
    rc.max_level = lvl_big
    rc.min_level = lvl_big
    rc.max_cells = 1000
    locations = []

    if location1[0] > location2[0]:
        lat1,lat2 = location2[0],location1[0]
    else:
        lat1, lat2 = location1[0], location2[0]


    if location1[1] > location2[1]:
        lng1, lng2 = location2[1], location1[1]
    else:
        lng1, lng2 = location1[1], location2[1]

    lng1 = (lng1 + 180) % 360 - 180
    lng2 = (lng2 + 180) % 360 - 180

    lngs = []
    if lng2 > lng1:
        lngs.append((lng1,lng2))
    elif lng2 < lng1:
        lngs.append((-180.0,lng2))
        lngs.append((lng1,180.0))

    for lng1,lng2 in lngs:
        cids = rc.get_covering(LatLngRect(LatLng.from_degrees(lat1,lng1),LatLng.from_degrees(lat2,lng2)))

        for cid in cids:
            ll_cid = cid.to_lat_lng()
            locations.append((ll_cid.lat().degrees,ll_cid.lng().degrees))
    return locations

def main():
    origin_lat_i, origin_lng_i = f2i(origin_lat), f2i(origin_lng)
    api_endpoint, access_token, profile_response = login(origin_lat_i, origin_lng_i)

    with sqlite3.connect('database.db') as db:
        create_tables(db)

    while True:
        pos = 1
        x = 0
        y = 0
        dx = 0
        dy = -1
        steplimit2 = steplimit**2
        for step in range(steplimit2):
            #print('looping: step {} of {}'.format(step + 1, steplimit**2))
            # Scan location math
            if -steplimit2 / 2 < x <= steplimit2 / 2 and -steplimit2 / 2 < y <= steplimit2 / 2:
                step_lat = x * 0.0025 + origin_lat
                step_lng = y * 0.0025 + origin_lng
                step_lat_i = f2i(step_lat)
                step_lng_i = f2i(step_lng)
            if x == y or x < 0 and x == -y or x > 0 and x == 1 - y:
                (dx, dy) = (-dy, dx)

            (x, y) = (x + dx, y + dy)

            #print('[+] Searching for Pokemon at location {} {}'.format(step_lat, step_lng))
            origin = LatLng.from_degrees(step_lat, step_lng)
            parent = CellId.from_lat_lng(origin).parent(15)
            h = get_heartbeat(api_endpoint, access_token, profile_response, step_lat, step_lng, step_lat_i, step_lng_i)
            hs = [h]

            for child in parent.children():
                latlng = LatLng.from_point(Cell(child).get_center())
                child_lat, child_lng = latlng.lat().degrees, latlng.lng().degrees
                child_lat_i, child_lng_i = f2i(child_lat), f2i(child_lng)
                hs.append(get_heartbeat(api_endpoint, access_token, profile_response, child_lat, child_lng, child_lat_i, child_lng_i))
            visible = []

            data = []
            for hh in hs:
                for cell in hh.cells:
                    for poke in cell.WildPokemon:
                        disappear_ms = cell.AsOfTimeMs + poke.TimeTillHiddenMs
                        data.append((
                            poke.SpawnPointId,
                            poke.pokemon.PokemonId,
                            poke.Latitude,
                            poke.Longitude,
                            disappear_ms,
                        ))
            if data:
                print('Upserting {} pokemon'.format(len(data)))
                with sqlite3.connect('database.db') as db:
                    insert_data(db, data)

def bounds(cell_id):
    cell = Cell(cell_id)

    url_string = 'http://maps.googleapis.com/maps/api/staticmap?size=400x400&path='

    coords = []
    for i in range(4) + [0]:
        point = cell.get_vertex(i)
        coords.append("{},{}".format(LatLng.latitude(point).degrees, LatLng.longitude(point).degrees))

    url_string += "|".join(coords)
    print url_string

def get_dir(lat, lng):
	origin_point = config.get("LOCATION")
	if origin_point is None:
		return "NoLocationSet" #No location set
	origin_point = LatLng.from_degrees(origin_point[0], origin_point[1])
	latLon = LatLng.from_degrees(lat, lng)
	diff = latLon - origin_point
	diff_lat = diff.lat().degrees
	diff_lng = diff.lng().degrees
	direction = (('N' if diff_lat >= 0 else 'S') if abs(diff_lat) > 1e-4 else '') + \
		(('E' if diff_lng >= 0 else 'W') if abs(diff_lng) > 1e-4 else '')
	return direction

def cover_square(lat, lng, width, level=15):
    offset = int(width / 2)
    g = Geodesic.WGS84  # @UndefinedVariable
    r = RegionCoverer()
    r.min_level, r.min_level = level, level
    g1 = g.Direct(lat, lng, 360, offset)
    g1 = g.Direct(g1['lat2'],g1['lon2'],270,offset)
    p1 = LatLng.from_degrees(g1['lat2'],g1['lon2'])
    g2 = g.Direct(lat, lng, 180, offset)
    g2 = g.Direct(g2['lat2'],g2['lon2'], 90,offset)
    p2 = LatLng.from_degrees(g2['lat2'],g2['lon2'])
    cells = r.get_covering(LatLngRect.from_point_pair(p1, p2))
    return cells

    def get_pokemons(self):
        pokemon_list = []
        origin_point = LatLng.from_degrees(self.location.latitude, self.location.longitude)
        for pokemon in Pokemon.get_active():
            pokemon_point = LatLng.from_degrees(pokemon['latitude'], pokemon['longitude'])

            pokemon_list.append({
                'id': pokemon['pokemon_id'],
                'name': pokemon['pokemon_name'],
                'time': '%02d:%02d' % (divmod((pokemon['disappear_time'] - datetime.utcnow()).seconds, 60)),
                'latitude': pokemon['latitude'],
                'longitude': pokemon['longitude']
            })

        return pokemon_list

def getNeighbors(location):
    level = 15
    origin = CellId.from_lat_lng(LatLng.from_degrees(location[0], location[1])).parent(level)

    max_size = 1 << 30
    size = origin.get_size_ij(level)

    face, i, j = origin.to_face_ij_orientation()[0:3]

    walk = [origin.id(),
            origin.from_face_ij_same(face, i, j - size, j - size >= 0).parent(level).id(),
            origin.from_face_ij_same(face, i, j + size, j + size < max_size).parent(level).id(),
            origin.from_face_ij_same(face, i - size, j, i - size >= 0).parent(level).id(),
            origin.from_face_ij_same(face, i + size, j, i + size < max_size).parent(level).id(),
            origin.from_face_ij_same(face, i - size, j - size, j - size >= 0 and i - size >= 0).parent(level).id(),
            origin.from_face_ij_same(face, i + size, j - size, j - size >= 0 and i + size < max_size).parent(level).id(),
            origin.from_face_ij_same(face, i - size, j + size, j + size < max_size and i - size >= 0).parent(level).id(),
            origin.from_face_ij_same(face, i + size, j + size, j + size < max_size and i + size < max_size).parent(level).id()]
            #origin.from_face_ij_same(face, i, j - 2*size, j - 2*size >= 0).parent(level).id(),
            #origin.from_face_ij_same(face, i - size, j - 2*size, j - 2*size >= 0 and i - size >=0).parent(level).id(),
            #origin.from_face_ij_same(face, i + size, j - 2*size, j - 2*size >= 0 and i + size < max_size).parent(level).id(),
            #origin.from_face_ij_same(face, i, j + 2*size, j + 2*size < max_size).parent(level).id(),
            #origin.from_face_ij_same(face, i - size, j + 2*size, j + 2*size < max_size and i - size >=0).parent(level).id(),
            #origin.from_face_ij_same(face, i + size, j + 2*size, j + 2*size < max_size and i + size < max_size).parent(level).id(),
            #origin.from_face_ij_same(face, i + 2*size, j, i + 2*size < max_size).parent(level).id(),
            #origin.from_face_ij_same(face, i + 2*size, j - size, j - size >= 0 and i + 2*size < max_size).parent(level).id(),
            #origin.from_face_ij_same(face, i + 2*size, j + size, j + size < max_size and i + 2*size < max_size).parent(level).id(),
            #origin.from_face_ij_same(face, i - 2*size, j, i - 2*size >= 0).parent(level).id(),
            #origin.from_face_ij_same(face, i - 2*size, j - size, j - size >= 0 and i - 2*size >=0).parent(level).id(),
            #origin.from_face_ij_same(face, i - 2*size, j + size, j + size < max_size and i - 2*size >=0).parent(level).id()]
    return walk

    def getCells(self, radius=10, bothDirections=True):
        origin = CellId.from_lat_lng(
            LatLng.from_degrees(
                self.latitude,
                self.longitude
            )
        ).parent(15)

        # Create walk around area
        walk = [origin.id()]
        right = origin.next()
        left = origin.prev()

        # Double the radius if we're only walking one way
        if not bothDirections:
            radius *= 2

        # Search around provided radius
        for _ in range(radius):
            walk.append(right.id())
            right = right.next()
            if bothDirections:
                walk.append(left.id())
                left = left.prev()

        # Return everything
        return sorted(walk)

 def getCellId(self):
     return CellId.from_lat_lng(
         LatLng.from_degrees(
             self.latitude,
             self.longitude
         )
     ).parent(15)

 def getLatLongIndex(latitude, longitude):
     return CellId.from_lat_lng(
         LatLng.from_degrees(
             latitude,
             longitude
         )
     ).id()

def neighbor_s2_circle(location, i_dir=0.0, j_dir=0.0):  # input location can be list, tuple or Point
    if type(location) in (list, tuple):
        ll_location = LatLng.from_degrees(location[0], location[1])
    elif type(location) is Point:
        ll_location = LatLng.from_point(location)
    elif type(location) is LatLng:
        ll_location = location
    else:
        return None

    cid_large = CellId.from_lat_lng(ll_location).parent(lvl_big)

    cid_small = cid_large.child_begin(lvl_small)
    vec_to_j = (Cell(ij_offs(cid_small, 0, 1)).get_center() - Cell(cid_small).get_center()).normalize()
    vec_to_i = (Cell(ij_offs(cid_small, 1, 0)).get_center() - Cell(cid_small).get_center()).normalize()

    vec_newlocation = ll_location.to_point() + safety * HEX_R / earth_Rrect * (i_dir * 3 ** 0.5 * vec_to_i + j_dir * 1.5 * vec_to_j)

    return vec_newlocation  # output is Point

def sub_cell(cell,i=0,dist=25):
    
    g = Geodesic.WGS84  # @UndefinedVariable
    olat = CellId.to_lat_lng(cell).lat().degrees
    olng = CellId.to_lat_lng(cell).lng().degrees

    p = g.Direct(olat, olng,(45+(90*i)),dist)
    c = CellId.from_lat_lng(LatLng.from_degrees(p['lat2'],p['lon2']))
    
    return c.parent(cell.level()+1)

    def remove_plan():
        location = (request.args.get('lat', type=float), request.args.get('lng', type=float))
        cid = CellId.from_lat_lng(LatLng.from_degrees(location[0],location[1])).parent(mapl.lvl_big)
        token = cid.to_token()

        lock_plans.acquire()
        if token in list_plans:
            list_plans.pop(list_plans.index(token))
        lock_plans.release()
        return jsonify("")

def cover_circle(lat, lng, radius, level=15):
    EARTH = 6371000
    region = Cap.from_axis_angle(\
             LatLng.from_degrees(lat, lng).to_point(), \
             Angle.from_degrees(360*radius/(2*math.pi*EARTH)))
    coverer = RegionCoverer()
    coverer.min_level = level
    coverer.max_level = level
    cells = coverer.get_covering(region)
    return cells

def get_cell_walk(lat, lng, radius, level=15):
    origin = CellId.from_lat_lng(LatLng.from_degrees(lat, lng)).parent(level)
    walk = [origin]
    right = origin.next()
    left = origin.prev()
    for dummy in range(radius):
        walk.append(right)
        walk.append(left)
        right = right.next()
        left = left.prev()
    return sorted(walk)

 def add_plan():
     location = (request.args.get('lat', type=float),request.args.get('lng', type=float))
     all_loc,border,cid = mapl.get_area_cell(location,True)
     # grid = mapl.Hexgrid()
     # all_loc = grid.cover_cell(cid)
     center = LatLng.from_point(Cell(cid).get_center())
     center = (center.lat().degrees, center.lng().degrees)
     token = cid.to_token()
     lock_plans.acquire()
     list_plans.append(token)
     lock_plans.release()
     return jsonify((all_loc, border,[center,token],[]))

def get_cell_ids(lat, long, radius=1000):
    # Max values allowed by server according to this comment:
    # https://github.com/AeonLucid/POGOProtos/issues/83#issuecomment-235612285
    if radius > 1500:
        radius = 1500  # radius = 1500 is max allowed by the server
    region = Cap.from_axis_angle(LatLng.from_degrees(lat, long).to_point(), Angle.from_degrees(360*radius/(2*math.pi*EARTH_RADIUS)))
    coverer = RegionCoverer()
    coverer.min_level = 15
    coverer.max_level = 15
    cells = coverer.get_covering(region)
    cells = cells[:100]  # len(cells) = 100 is max allowed by the server
    return sorted([x.id() for x in cells])

def get_cellid(lat, long):
    origin = CellId.from_lat_lng(LatLng.from_degrees(lat, long)).parent(15)
    walk = [origin.id()]

    next = origin.next()
    prev = origin.prev()
    for i in range(10):
        walk.append(prev.id())
        walk.append(next.id())
        next = next.next()
        prev = prev.prev()
    return sorted(walk)

def cell_spiral(lat, lng, dist, level=15, step=100, res=3.6):
    cells = []

    g = Geodesic.WGS84  # @UndefinedVariable
    
    for i in xrange(0,dist,step):
        for rad in xrange(int(360/res)):
            p = g.Direct(lat, lng, rad*res, i)
            c = CellId.from_lat_lng(LatLng.from_degrees(p['lat2'],p['lon2']))
            c = c.parent(level)
            if c not in cells: cells.append(c)
    
    return cells

def get_cellid(lat, lng, level=15):
    origin = CellId.from_lat_lng(LatLng.from_degrees(lat, lng)).parent(level)
    walk = [origin.id()]

    # 10 before and 10 after
    next = origin.next()
    prev = origin.prev()
    for i in range(10):
        walk.append(prev.id())
        walk.append(next.id())
        next = next.next()
        prev = prev.prev()
    return sorted(walk)