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 _get_cell_id_from_latlong(self, radius=1000):
        # type: (Optional[int]) -> List[str]
        position_lat, position_lng, _ = self.api_wrapper.get_position()

        cells = get_cell_ids(position_lat, position_lng, radius)

        if self.config['debug']:
            self._log('Cells:', color='yellow')
            self._log('Origin: {},{}'.format(position_lat, position_lng), color='yellow')
            for cell in cells:
                cell_id = CellId(cell)
                lat_lng = cell_id.to_lat_lng()
                self._log('Cell  : {},{}'.format(lat_lng.lat().degrees, lat_lng.lng().degrees), color='yellow')

        return cells

 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 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 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 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 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 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 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 _get_cellid(self, lat, long, radius=10):
        origin = CellId.from_lat_lng(LatLng.from_degrees(lat, long)).parent(15)
        walk = [origin.id()]

        # 10 before and 10 after
        next = origin.next()
        prev = origin.prev()
        for i in range(radius):
            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)

def get_cellid(lat, long):
    origin = CellId.from_lat_lng(LatLng.from_degrees(lat, long)).parent(15)
    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 ''.join(map(encode, sorted(walk)))

def get_neighbors(lat, lng):
    origin = CellId.from_lat_lng(LatLng.from_degrees(lat, lng)).parent(15)
    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 walk

def get_cell_ids(lat, long, radius = 10):
	origin = CellId.from_lat_lng(LatLng.from_degrees(lat, long)).parent(15)
	walk = [origin.id()]
	right = origin.next()
	left = origin.prev()
	# Search around provided radius
	for i in range(radius):
		walk.append(right.id())
		walk.append(left.id())
		right = right.next()
		left = left.prev()

	# Return everything
	return sorted(walk)

    def _get_cell_id_from_latlong(self, radius=10):
        position_lat, position_lng, _ = self.api.get_position()
        origin = CellId.from_lat_lng(LatLng.from_degrees(i2f(position_lat), i2f(position_lng))).parent(15)
        walk = [origin.id()]

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

    def cover_cell(self, cid):
        lats = []
        lngs = []
        output = []
        s2_cell = Cell(cid)
        lvl = s2_cell.level()
        for i in [0, 1]:
            for j in [0, 1]:
                lats.append(s2_cell.get_latitude(i, j)/pi*180)
                lngs.append(s2_cell.get_longitude(i, j)/pi*180)
        locations = self.cover_region((min(lats),min(lngs)),(max(lats),max(lngs)))
        for location in locations:
            testid = CellId.from_lat_lng(LatLng.from_degrees(location[0],location[1])).parent(lvl)
            if testid == cid:
                output.append(location)

        return output

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 get_area_cell(location,unfilled=False):
    border = []
    locs = []

    cid_large = CellId.from_lat_lng(LatLng.from_degrees(location[0], location[1])).parent(lvl_big)
    border.append(get_border_cell(cid_large))

    if unfilled:
        return [], border, cid_large

    corner = neighbor_s2_circle(LatLng.from_degrees(border[-1][0][0], border[-1][0][1]), safety_border*0.5, safety_border/3.0)
    j_maxpoint = LatLng.from_point(neighbor_s2_circle(LatLng.from_degrees(border[-1][1][0], border[-1][1][1]), safety_border*0.5, (1-safety_border)/3.0))
    i_maxpoint = LatLng.from_point(neighbor_s2_circle(LatLng.from_degrees(border[-1][3][0], border[-1][3][1]), (1-safety_border)*0.5, safety_border/3.0))

    base = corner
    p_start = base

    dist_j = j_maxpoint.get_distance(LatLng.from_point(p_start))
    last_dist_j = None
    j = 0
    while last_dist_j is None or dist_j < last_dist_j:
        dist_i = i_maxpoint.get_distance(LatLng.from_point(p_start))
        last_dist_i = None
        while last_dist_i is None or dist_i < last_dist_i:
            locs.append(LatLng.from_point(p_start))
            p_start = neighbor_s2_circle(p_start, 1.0, 0.0)
            last_dist_i = dist_i
            dist_i = i_maxpoint.get_distance(LatLng.from_point(p_start))
        base = neighbor_s2_circle(base, 0.0, 1.0)
        last_dist_j = dist_j
        dist_j = j_maxpoint.get_distance(LatLng.from_point(base))
        if j % 2 == 1:
            p_start = base
        else:
            p_start = neighbor_s2_circle(base, -0.5, 0.0)
        j += 1

    all_loc = []
    for loc in locs:
        all_loc.append([loc.lat().degrees, loc.lng().degrees])

    return all_loc, border,cid_large