useful_faq | (no subject)

Приветы! У меня задача по геодезии и вычислительной геометрии. В гугле искал, но все вокруг да около, ответа так и не нашел - надеюсь на вашу помощь.

На планете Земля имеется множество точек, заданных геодезическими координатам - широтой Lat и долготой Long. Требуется выбрать все точки, находящиеся в пределах круга радиуса R от наблюдателя, который задан широтой MyLat и долготой MyLong. Пример практического применения: найти все ларьки с пивом не далее 500 метров от дома.

Я пытался включать мозг и освежать знания в геометрии.
1. Первое решение - на поверхности: считать расстояния от меня до всех ларьков с пивом, выбирать те, которые ближе R=500.
Формула: S = 111.2 * arccos(sin(MyLat)*sin(Lat) + cos(MyLat)*cos(Lat)*cos(Long-MyLong)))
Но ларьков с пивом по всей планете чуть более, чем дофига, и перебирать стопицот их ради поиска нескольких - нерационально. Кроме того, приведенная формула содержит сложные (для процессора) операции, и это будет жрать время, когда искателей пива в один момент станет слишком много.

2. Второе решение: угловые расстояния. Измеряются углы к окружности и к искомой точке относительно прямой, проведенной к наблюдателю:

Решениями являются все точки, для которых угол b меньше или равен углу a.
Формула угла между 2 точками, выраженных в геокоординатах:
b = arccos(sin(MyLat)*sin(Lat) + cos(MyLat)*cos(Lat)*cos(Long-MyLong)))
Этот b должен быть не более a, которая является угловым расстоянием от наблюдателя к окружности:
arccos(sin(MyLat)*sin(Lat) + cos(MyLat)*cos(Lat)*cos(Long-MyLong))) < a
или (берем cos() от обеих частей неравенства)
sin(MyLat)*sin(Lat) + cos(MyLat)*cos(Lat)*cos(Long-MyLong)) > cos(a) (тут область определения, потом посчитаю)
Учитывая, что sin(MyLat), cos(MyLat) и cos(a) можно посчитать сразу один раз, а sin(Lat) и cos(Lat) можно посчитать и сохранить при задании координат ларька с пивом, единственным серьезным вычислением при переборе ларьков остается cos(Long-MyLong), но это уже не так страшно.
Направление выглядит заманчивым.

3. Можно еще так: разбить сферу на множество равноудаленных точек, и в будущем, при вводе координат ларьков, сразу определять и записывать принадлежность ларька к определенной базовой точке, что впредь сильно поможет при поиске. Но, кажется, для сферы существует лишь несколько вариантов размещения равноудаленных точек: вписанный икосаэдр и несколько других правильных многогранников. А в моем случае, таких точек надо не 12 и не 20, а тысячи.
4. Как-то решить задачу в полярной (сферической?) системе коориднат. Как - не представляю, но нутром чую: можно.

Короче, вот. Куда копать, не подскажете? Также интересуют мысли по оптимизации первого варианта. Например, на плоскости я бы сразу ограничил область поиска квадратом, и отсеял кучу хлама, у которых координаты Х и Y лежат за пределами квадрата. А тут... хер его знает, как %)

Спасибо!

зы: кстати, не нашел формулу окружности, проведенной на сфере ни в декартовых, ни в полярных координатах :(

Flat | Top-Level Comments Only

(deleted comment)

From:

skvoznik.livejournal.com

Спасибо, Жека - любопытно. Надо б посмотреть максимальные погрешности...

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

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

Совершенно прикладной. Вернусь из Крыма - буду приставать :)

Охты еееепть! Джон, это будет круто :) и на опен заходи.

стукни мне в скайп плз. Чота ты в оффе.

alex-djk1.livejournal.com

Точки по поверхности можно не равномерно разбрасывать, а свободно. У каждой указывать радиус, который попадают "ларьки". Причем это можно делать иерархически. Типо первые 10-20 окружностей покрывают всю землю, следущие уровни покрывают вышестоящие окружности. Как-то так.

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

Само собой, что точка может принадлежать нескольким окружностям (это не квадраты все-таки). Но за счет иерархичности, можно тащить много (миллионы к примеру) окружностей без ущерба к скорости. Пробежаться по иерархии, проверив на каждой по 5-10-20 окружностей по любому быстрее, чем перебрать весь миллион.
Как вариант расположения: первый шаг - на шар кладется 6 окружностей (как на куб). Следующие - делят эту окружность на 4 части. И так далее.

migorec.livejournal.com

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

Ага, я тоже так думал. За предельную широту не спорю, а вот по долготе разговор отдельный :)
Круги одинакового радиуса, расположенные на разных широтах, будут иметь разные предельные долготы.
Оки, даже если мы их сможем посчитать. Для поиска в районе экватора все красиво: там органиченная нами зона почти квадратная, оптимальность - высокая. Если мы ищем ближе к полюсам? Область поиска, ограниченная предельными широтами и долготами, по форме близка к трапеции, и чем ближе к полюсу, тем больше отношение ее верхнего и нижнего основания (ну то есть растяяяянутая такая выходит), что перестает быть эффективным.
Если наш любимый круг захватывает и полюс, область поиска ваще хитрая получаетя.
Короче, я согласен, что этим кое-то ограничить можно. Но в разных случаях - с разной эффктивностью, которая, не уверен, что всегда оправдана.

. А если

Там проапдейтил в пункте 2. Пока держу как базовый :)

ymep.livejournal.com

я бы сделал таким образом:
у тебя есть координаты точки MyLon, MyLat и радиус поиска R
1. Сначала ограничить зону поиска квадратом со стороной 2z и центром в MyLon, MyLat, для этого найти два угла квадрата lon1, lat1 и lon2, lat2 и теперь рассматривать только точки внутри этого квадрата.
формулы для расчета углов квадрата найдешь здесь: http://www.movable-type.co.uk/scripts/latlong.html в разделе "Destination point given distance and bearing from start point",
lon1, lat1 - bearing 45 deg, distance R*SQRT(2)
lon2, lat2 - bearing 225 deg, distance R*SQRT(2)

надеюсь "ларьков" в заданной округе уже же не сотни, теперь можешь по своему первому варианту искать, опять же воспользуйся формулами и скриптами с того сайта :)

надеюсь помог

для областей близких к полюсам(градусов от 75), где область "похожа на трапецию" - для ограничения делай самую меньшую сторону трапеции = 2R
Если так сильно надо искать такие точки в районе полюсов - реально проще для полюсов отдельный алгоритм придумать, чем городить сложный, но универсальный

единственно, если тебе ларьки надо искать в радиусе то 100 м то 5000 км.. тогда всяко сложнее. но не совсем понятен смысл задачи тогда :)

тока прочитал. Спасибо :)