Как создать радиус в любое расстояние м/км расположенного вокруг координаты и получить список этих координат?

Question

[agent_2203]

Суть вопроса в том, что есть yandex map, в ней берем любую координату по широте и долготе, допустим 55.880707, 37.55513.

Мне нужно найти все координаты в пределах радиуса, расположенные с периодичностью каждый, допустим, метр.
Не знаете как это сделать на python ?

Answer 1

[Wataru]

Пусть координаты x0,y0. Расстояние можно считать по этой формуле (вики).

Вам придется или скопировать код по ссылке и переписать на питоне, или использовать этот пакет.

Дальше, вам надо начиться отступать от заданной точки на север или восток на 1 метр. Это можно или медетировать над формулой выше а можно просто запустить бинарный поиск, который будет искать изменение широты или долготы. Пусть d - сколько вам надо отложить в метрах, R - радиус земли в метрах. Тогда ищите изменение на отрезке (0, 4*r*180/(2*Pi*R)). Пробуйте откладывать текущее значение по широте или долготе, считайте расстояние по формуле и, если оно больше d, заменяйте верхнюю границу отрезка на середину, иначе заменяйте нижнюю границу. Остановите бин.поиск, когда отрезок станет достаточно мелким (например <1e-10).

Используя бинпоиск выше вы можете найти, сколько надо отложить по широте или долготе в градусах, чтобы точка сдвинулась на 1м. Теперь можно сделать основной цикл.

Сначала сгенерируйте точки на одной вертикале с начальной. Для этого повторно откладывайте 1м на север и юг от нее, пока расстояние до (x0,y0) не превысит ваш радиус. Бинпоиск достаточно запустить ровно один раз в самом начале и дальше именно это приращение откладывайте вверх и вниз.

Потом аналогичным образом откладывайте от каждой сгенеренной точки новые точки на запад и восток. Сначала для каждой точки бинпоиском найдите нужное приращение по долготе. Потом откладывайте его влево и вправо, пока не выйдите за радиус от (x0,y0).

Comments

[agent_2203]

не подскажите что имеется ввиду r в формуле ?
(0, 4*r*180/(2*Pi*R))

[Wataru]

agent_2203, расстояние между точками. 1 метр.

Но на самом деле там фигня у меня написана... лучше тупо до 180 по долготе и до 90 по широте гнать и не доумать.

[agent_2203]

Илья Николаевский, как это реализовать ? Я больше силен в программирование чем в алгоритмизации

[Wataru]

agent_2203,

// x,y - точка от которой ищем +1м вверх
// -180 <=x<=180, -90<=y<=90.
l = 0
// required_dist - нужное приращение
r = min(180, 90-y);
while r-l < 1e-10:
  m=(r+l)/2;
  dist = haversine((x,y),(x,y+m)); // Формула для расстояния между точками.
  if dist > required_dist: r = m
  else l = m
step = l; // шаг по широте, чтобы сдвинутся на required_dist.

[agent_2203]

Илья Николаевский, а как в данном случае изменять required_dist и чему оно равняется в начале ?

[Wataru]

agent_2203, required_dist - это ваш 1м, заданный в условии задачи.

[agent_2203]

from haversine import haversine

x = 55.880707
y = 37.55513
l = 0
r = min(180, 90-y)
required_dist = 1

while r-l < 1e-10:
    m=(r+l)/2
    dist = haversine((x,y),(x,y+m))
    if dist > required_dist:
        r = m
    else:
        l = m

step = l

Тут даже цикл он не проходит и ничего не происходит, может я что-то не понял ?

[Wataru]

agent_2203, Потому что опечатка, надо в условии цикла поменять знак на >.

[Wataru]

agent_2203, Еще смотрите, что расстояние возвращенное haversine в тех же единицах, что и required_dist. Модуль по ссылке в ответе, вроде без дополнительных параметров возвращает в километрах.

[agent_2203]

Илья Николаевский, понял, я перевожу в метры, а дальше что делать ? У меня есть шаг, он с целыми числами, в данном случае 16,..., что с ним делать ? Если добавлять к y-ку, то это вообще не то что надо

from haversine import haversine

x = 55.880707
y = 37.55513 
l = 0
r = min(180, 90-y)
required_dist = 1 

while r-l > 1e-10:
    m=(r+l)/2
    dist = haversine((x,y),(x,y+m))/1000
    if dist > required_dist:   
        r = m
    else:
        l = m

step = l

[Wataru]

agent_2203, У вас есть шаг изменения широты, чтобы отступить на один метр.

Откладывайте его от x0, y0, пока расстояние от текущей точки до центра не станет больше вашего радиуса (исходные данные в вашей задаче).

Так вы получите столб точек прямо над центром с заданным шагом. Внитури этого цикла от каждой точки найдите таким же бинарным поиском (лучше его в отдельную функцию вынести) приращение по долготе. Отаклыдывайте это приращение влево и вправо, пока не выйдете за радиус.

Так вы получите все точки в сетке с расстоянием примерно в 1м в пределах заданного радиуса.

Answer 2

[agent_2203]

Фух, наконец-то доделал всю логику, благодарю за подсказку, вот готовый код:

from haversine import haversine
from re import match
from pprint import pprint

def num_decimal_places(number):
    return len(
        (str(number) if '.' in str(number) \
        else str(number) + '.').rstrip('0').split('.')[-1]
        )

def go_to_metr(x, y, name_coordinate):
    required_dist = 1
    l = 0
    r = min(180, 90-y)
    while r-l > 1e-10:
        m=(r+l)/2

        dist = (
            (haversine((x,y),(x,y+m))/1000)
                ) if name_coordinate == "y" else (
            (haversine((x,y),(x+m,y))/1000)
                )

        if dist > required_dist: 
            r = m
        else:
            l = m

    step = float(int(l))

    numb_digit = 1

    for _ in range(
        num_decimal_places(y if name_coordinate == "y" else x)
    ):
        numb_digit *= 10
        
    step = step/numb_digit
    finally_coordinate = x+step if name_coordinate == "x" else y+step
    return finally_coordinate


def go_to_radius(init_x, init_y, radius):
    array_coord_x = []
    array_coord_y = []
    for coordinate in ["x", "y"]:
        local_coord = init_x if coordinate == "x" else init_y
        init_coord = init_y if coordinate == "x" else init_x

        array_coord = array_coord_x if coordinate == "x" else array_coord_y

        for _ in range(radius):
            local_coord = go_to_metr(
                local_coord if coordinate == "x" else init_coord, 
                init_coord if coordinate == "x" else local_coord, coordinate)
            array_coord.append(
                    (
                        (local_coord, init_coord) 
                    ) if coordinate == "x" else (
                        (init_coord, local_coord)
                    )
            )
    array_coord_all = []
    
    for numb, _ in enumerate(range(len(array_coord_x))):  
        array_coord_all.append((array_coord_x[numb][0], array_coord_y[numb][1]))
    return {
        "coords_x": array_coord_x, "coords_y": array_coord_y,
        "coords_all": array_coord_all
    }
    
pprint(go_to_radius(55.880707, 37.55513, 5))

Вывод:

{'coords_all': [(55.880715, 37.55529),
                (55.880723, 37.55545),
                (55.880731000000004, 37.55561),
                (55.88073100000001, 37.55577),
                (55.88073100000009, 37.555930000000004)],
 'coords_x': [(55.880715, 37.55513),
              (55.880723, 37.55513),
              (55.880731000000004, 37.55513),
              (55.88073100000001, 37.55513),
              (55.88073100000009, 37.55513)],
 'coords_y': [(55.880707, 37.55529),
              (55.880707, 37.55545),
              (55.880707, 37.55561),
              (55.880707, 37.55577),
              (55.880707, 37.555930000000004)]}

Comments

[Developer]

Как будет работать вблизи полюсов?

[agent_2203]

Developer, можете проверить и скажете

[Developer]

agent_2203, браво!
То есть, ты не проверял крайние случаи чтобы проверить правильную работу алгоритма?
Я бы уволил такого манки-кодера.
Вместо тебя эту проверку сделают конкуренты, хакеры и взломщики, будь готов к неприятностям

[agent_2203]

Developer, не будьте таким серьезным, я и открыл этот вопрос чтобы обсудить данную задачу, никаких конкурентов в помине нет, а этот код я сделал такому же программисту, в личное его пользование, если ему нужно, то дополнит сам, а разводить данный цирк можете идти на реддит, там любят таких хейтеров как вы :)

В любом случае если есть какие-то конкуренты, то они уже давно взяли этот код, не беспокойтесь, если бы я делал для заказчика, то я бы проверил все случаи, и уж тем более не выставлял код на всеобщее обозрение.