Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 29.04.2010, 00:42
Новичок

Отправить личное сообщение для skvoznik Посмотреть профиль Найти все сообщения от skvoznik
 
Регистрация: 29.04.2010
Сообщений: 1

Принадлежность точки кругу радиуса R на поверхности сферы
Добрый день! Прошу прощения за дилетантскую формулировку.
На поверхности эллипсоида (Земли) есть множество точек. Требуется определить их приналежность кругу радиуса R на поверхности эллипсоида. Центр круга задан. Если проще - определить, какие, например, населенные пункты есть в заданном радиусе от наблюдателя.
Самое простое - перебирать расстояния от заданной точки до всех имеющихся, но это медленно (точек может быть десятки тысяч).
Следующим шагом я подумал, что область поиска можно сначала ограничить широтой и долготой (трапеция), но не всегда это оптимально.
Посоветуете, как оптимизировать? Операции типа синуса и т.п. - тяжеловесны для компутера. Может, есть другие варианты?
Спасибо!
  #2  
Старый 29.04.2010, 02:02
гость

 
Сообщений: n/a

зы: нутром чую, что землю можно аппроксимировать до шара, и решить задачув порялрной системе координат...
  #3  
Старый 29.04.2010, 03:15
гость

 
Сообщений: n/a

перейти в трехмерное пространство (вычислить 3D координаты точек), там аппроксимировать круг параллеллипипедом, и сделать запрос к структуре данных, эффективно умеющей искать подмножество точек в заданных параллелипипедах. kD-дерево или октодерево. Затем отсеять лишние (тут уже придется считать честные расстояния по WGS'у, с синусами и проч.)
  #4  
Старый 29.04.2010, 18:38
гость

 
Сообщений: n/a

Спасибо за ответ. А вот пришла еще одна мысль: попадание точки в круг можно еще проверять по угловому расстоянию от центра круга. Т.е. угол между вектором к центру круга и вектором к искомой точке не должен быть больше, чем угол между вектором к центру круга и к точки на окружности. Этим задача не облегчается?
Skvoznik
  #5  
Старый 29.04.2010, 18:47
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Если запросов (т.е. точек-центров кругов) будет много, то, конечно, стоит построить какую-либо пространственную индексацию, чтобы не перебирать все точки набора.
  #6  
Старый 12.05.2010, 01:10
studentman.ru

 
Сообщений: n/a

метод Крамера
Окружность это полигон.
Далее используйте метод Крамера
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Кривый Безье 3-го порядка,поиск радиуса кривизны! Polza Вычислительная геометрия 41 30.05.2010 08:24
Разбиение сферы на треугольники Anonymous Вычислительная геометрия 11 04.01.2010 23:41
Расстояние от точки до поверхности Безье iiii01 Вычислительная геометрия 6 17.03.2009 23:13
Конус - принадлежность точки geoinform Вычислительная геометрия 11 20.09.2008 12:38
Принадлежность точки выпуклой оболочки 3d vladScr Вычислительная геометрия 6 15.05.2008 13:17