Имеются два треугольника. Требуется определить факт их пересечения. Треугольники заданы широтой и долготой.
Можно использовать алгоритмы из 2D геометрии. Одно НО - если хоть одна из фигу содержит в себе полюс, то алгоритмы 2D не подходят.
Вроде на форуме присутствуют люди, которые пишут скрипты для заливки данных в OSM и иногда в таких сообщениях упоминаются операции над полигонами.
Может они уже решали такую проблему и могут подсказать хотя бы куда копать?
P.S. Смотрел в сторону сферической геометрии треугольников, но там таких алгоритмов нет.
А так на первый взгляд всё так же, как и для обычных треугольников, только вместо отрезков - ортодромии
Из-за нелинейности вроде никаких эффектов не возникает
А где внутренность у треугольника на сфере? Пока он маленький, вроде интуитивно понятно, а когда он вырастет? Например одна точка в австралии, одна в США, а третья в Москве. Это уже совсем не похоже на треугольник.
А теперь еще веселее. Возьмем три точки, расположенные на экваторе. Такой треугольник существует? Где у него внутренность, а где наружная строна. А если он не существует (точки на одной линии), то возьмем точки, расположенные на окружности, расположенной под углом 30 градусов к экватору. Они уже могут не оказаться на одной “прямой”.
А если треугольники неболшьшие, то я бы вращал сферу так, чтобы полюс никогда не попадал внутрь треугольника.
Alexey Guseynov привел пример правильный. Точнее тот, что дает кривой результат. Т.е. если взять треугольник, точки которого расположены на одной широте, то на 2D карте это будет выглядеть как обычная прямая. И при таком раскладе обычные методы из 2D геометрии не применимы.
С вращением понятно, но при этом вращать нужно оба треугольника и при вращении может получится, что второй треугольник сместился на полюс.
В общем - ответ ясен. Если никто не знает, то спец-методов нет. Буду использовать свои придумки.
Нет. Не секрет. Делаю (или по крайней мере пытаюсь сделать) 3D карту на основе OSM данных.
Треугольник - это тайл поверхности. Второй треугольник - это пирамида(frustum) камеры, спроецированной на поверхность планеты. Данный алгоритм требуется для определения: видим ли данный тайл на экране и нужно ли его выводить или стоит скрыть для. Т.е. отсечение невидимых тайлов.
Ну тогда ортодромии действительно не нужны
Но не нужно и пересечение треугольников, список тайлов лучше по-другому получать.
Кстати, а зачем они треугольные??
Поделить сферу на прямоугольники весьма проблематично, поэтому треугольные.
А зачем получать список тайлов? Вершины тайла уже изместны, их получать не нужно. Нужно определить: попадает ли тайл в камеру.
Проблема трапеций в том, что одна сторона её больше, другая меньше + на полюсах трапеция вырождается в треугольник. Т.е. получается, что нужно будет отслеживать: трапеция на полюсе или нет. Изначально я тоже начал с трапеций, но после долгих раздумий и анализа пришел к выводу, что тайл в виде треугольника - более оптимально.
А что значит к прямоугольным координатам? Не совсеи понял.
А зачем ‘обслуживать’ полюса? Сделайте проверку и ‘не пускайте’ туда пользователя
А посмотреть потом можно будет?
UPD: надо хакнуть GE, что бы ходил за тайлами к нам и посмотреть, что получится.
(Скрестить sas и ge, это будет песня).
