(no subject)
Apr. 30th, 2010 03:49 pm![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
skvoznik.livejournal.com posting in ![[community profile]](https://www.dreamwidth.org/img/silk/identity/community.png){kind=small}
useful_faqПриветы! У меня задача по геодезии и вычислительной геометрии. В гугле искал, но все вокруг да около, ответа так и не нашел - надеюсь на вашу помощь.
На планете Земля имеется множество точек, заданных геодезическими координатам - широтой 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 лежат за пределами квадрата. А тут... хер его знает, как %)
Спасибо!
зы: кстати, не нашел формулу окружности, проведенной на сфере ни в декартовых, ни в полярных координатах :(
На планете Земля имеется множество точек, заданных геодезическими координатам - широтой 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 лежат за пределами квадрата. А тут... хер его знает, как %)
Спасибо!
зы: кстати, не нашел формулу окружности, проведенной на сфере ни в декартовых, ни в полярных координатах :(
no subject
Date: 2010-04-30 09:59 pm (UTC)