Сторона сферического многоугольника = сечение сферы плоскостью проходящей через центр этой сферы.

То есть вместо двумерной геометрии на сфере можно рассматривать трехмерную геометрию с плоскостями в обычном пространстве. Точка внутри сферического многоугольника = точка внутри многогранного угла в трёхмерном пространстве.

Собственно вершины многоугольника на сфере можно принять за (1,0,0), (0,1,0) и (0,0,1) в пространстве и тогда новые координаты проверяемой точки в этой системе координат определяют «квадрант» в который эта точка попадет. (Это трёхмерная версия обоснования тех формул «для треугольника»)

Или есть что-то, умеющее работать с географическими координатами?

В целом в аналитической геометрии весь трюк состоит в том что нужно не искать что-то для работы с твоими координатами, а найти систему координат в которой будет удобно и легко работать и туда быстренько трансформироваться с сохранением ключевых свойств.

А если потребуется, в самом конце можно обратное преобразование координат применить

Первые когомологии сферы с выколотой точкой равны нулю.

Поэтому любая точка всегда лежит внутри/вне любой замкнутой кривой. Задача фундаментально некорректна.

Быстро же Альфа геометрию забыла.=)

ТС: задачу надо чем-то дополнить. Что значит «внутри его границ»?))

многоугольник и замкнутая кривая - это разные вещи

Да ладно, не стесняйся, все свои.=)

Поздно, спать пора, а универ был давно.

Вангую, что ТСу тут никто и никогда не поможет.

Ну да, автор хочет по 1-циклу на сфере найти единственную 2-цепь, границей которой он является. Такая 2-цепь существует, т.к. H_1(S^2)=0, но заведомо неединственна, т.к. вторые (например, клеточные, но не важно) гомологии — уже ненулевые.

То, что H_2(S^2)!=0, напрямую связано с тем, что, как замечает анон, H^1(S^2\{pt})=0. Поэтому бесполезно вычслять индекс: т.к. все 1-формы когомологически нулевые, то с каким бы 1-циклом мы их не спаривали, в результате будет нуль.

Остались грамотные люди. ЛОР — торт!

Кому передавть пальму перевенства планируете, грамотные люди? Где ваша смена? Есть она? Потому что если её нет, то грамотные ли вы люди?

Что сходу я могу предложить со своими остатками знаний в линейной алгебре:

Вопрос 3: Как нужно обрабатывать точки X=0 Y=±90?

Уроки по тригонометрии в моей средней средней школе позволяют легко перевести это представление в систему трёхмерных декартовых координат.

Требуется узнать, лежит ли точка внутри его границ.

Если я правильно понял задачу, то это возможно только если точка лежит в плоскости треугольника (от 4-угольника можно любой взять). Для этого достаточно чтобы смешанное произведение 2х векторов из этого треугольника и вектора от точки на сфере до треугольника было равно нулю. Иными словами эти 3 вектора должны быть компланарны.

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

Для меня с выпуклым 4-угольником посложнее - с ним вполне работает тот же метод описания контура 4-угольника векторами. Но тут у меня сложность в алгоритме построения такой последовательности векторов. Поэтому с ходу мне остаётся предложить только разбить 4-угольник на любые 2 треугольника. Если точка в пределах контура одного из треугольников - она в пределах контура 4-угольника. Выяснение лежит ли точка в пределах треугольника я расписал в предыдущем абзаце.

Есть ли готовая библиотека для Питона, чтобы это считать?

Тут простенькая цепочка логических рассуждений и нужно сбацать парочку операций с матрицами и их построений. В питоне должны быть библиотеки для операций с матрицами.

Есть точка на сфере, заданная угловыми координатами 0 <= X < 360 и -90 <= Y <= +90. Есть треугольник или выпуклый четырёхугольник без самопересечений в тех же координатах.

в тех же координатах

Но похоже практически все мои рассуждения идут коту под хвост если говорится о «треугольниках» и «четырёхугольниках» натянутых на поверхность сферы.

и убедиться, что у всех совпадает знак?

Да. В переводе на русский это звучит так: ты обходишь все грани в одном направлении и смотришь с какой стороны от отрезка лежит точка. Например если обходишь против часовой то точка должна быть всегда слева.

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

Задача фундаментально некорректна.

Что не нравится?

ТС: задачу надо чем-то дополнить. Что значит «внутри его границ»?))

Что множество незамкнутое. Искомая точка не лежит на границе. Все 3 векторных/псевдоскалярных произведения не нуль.

Но похоже практически все мои рассуждения идут коту под хвост если говорится о «треугольниках» и «четырёхугольниках» натянутых на поверхность сферы.

Именно.

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

Спасибо.

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

Вспоминай. Здесь он есть? http://bookash.pro/ru/t/Геометрическое моделирование/

Или этот? http://znanium.com/catalog/product/520536

Этот? https://www.labirint.ru/books/182036/

Этот? http://biblioclub.ru/index.php?page=book&id=257197

Этот? http://www.kodges.ru/komp/design/357727-geometricheskoe-modelirovanie-2016-go...

Точка внутри сферического многоугольника = точка внутри многогранного угла в трёхмерном пространстве.

Как учесть цикличность 1-й координаты? Отрезок (1;1)-(359;2) должен пересекать 0-й меридиан, а не оборачиваться вокруг большей части шара.

Без этого неясно, с которой стороны плоскостей должна оказаться точка.

Если допустим все три точки «треугольника» находятся на экваторе. Как я понимаю этот треугольник натягиваясь на сферу формирует полусферу. Любая точка не на экваторе будет в контуре такой полусферы или вне её?

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

Если допустим все три точки «треугольника» находятся на экваторе.

Не находятся. Треугольники заведомо невырожденные.

Как я понимаю этот треугольник натягиваясь на сферу формирует полусферу. Любая точка не на экваторе будет в контуре такой полусферы или вне её?

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

Дополню стартовый пост.

Если допустим все три точки «треугольника» находятся на экваторе.

Не находятся. Треугольники заведомо невырожденные.

Как я понимаю этот треугольник натягиваясь на сферу формирует полусферу. Любая точка не на экваторе будет в контуре такой полусферы или вне её?

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

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

Её нет. Единственный критерий — из 2 линий соединяющих 2 вершины выбирать меньшую, и из 2 фигур ограниченных многоугольником — тоже меньшую.

Выбрать меньшую всегда можно однозначно, все разности координат меньше 90 градусов.

Следовательно, надо ещё сформулировать правило, как проводить линии. Простые случаи — по меридианам и по параллелям, но как описать общий?

Дополню стартовый пост, когда сформулирую чётче.

Задача, блин.

Пусть точка A - северный полюс, точка B - южный полюс, а точка C в метре от южного. Ты внутри треугольника или снаружи?

EDIT: опоздал.

В этом моя логика описанная в этом посте работает. Пропускается проверка условия компланарности т.к. не имеет смысла и в векторных операциях нужно вместо первоначальной точки на сфере рассматривать её проекцию на плоскость треугольника. Проекцию с точки зрения из центра сферы.

В этом случае треугольник стягивается в прямую от полюса к полюсу. Остаётся вопрос считается точка которая лежит на стороне треугольника включённой в контур треугольника.

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

Остаётся вопрос считается точка которая лежит на стороне треугольника включённой в контур треугольника.

Для простоты — контур не включаем.

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

Все треугольники маленькие, поэтому при неоднозначности следует брать меньшую из площадей.

Если треугольники маленькие, то я бы перевел задачу в phi-theta, сдвинул бы углы так, чтобы разрыв 0-2pi не попадал в треугольник и решал бы в 2D.

вместо первоначальной точки на сфере рассматривать её проекцию на плоскость треугольника. Проекцию с точки зрения из центра сферы.

Навскидку эта точка находится через систему уравнений комланарности векторов треугольника и вектора от точки треугольника до искомой проекции, а также уравнения пропорциональности векторов от центра сферы до первоначальной точки и проекции. Это легко реализуется после перевода координат в декартовую систему, радиус сферы непринципиален и можно принять за единицу. После этого можно перейти к двухмерным координатам в плоскости треугольника, но необязательно.

В конце учёт переменной как треугольник натягивается на глобус - банальная логика легко находит результат.

Для простоты — контур не включаем.

Я бы не сказал - в моём решении и случае с 4-угольником это неплохо так усложняет дело. Иначе же если векторные произведения при обходе контура знак относительной пропорциональности не меняют и при этом среди произведений есть нуль, то рассматриваемая точка включена в контур.

Исключительные случае когда нулей несколько - это треугольник преображается в полусферу и когда в «отрезок». В первом случае задача решается через логику. Во втором случае включение точки в контур уже дело усложняет.

По вопросу 1: формулы подходят, только если спроецируешь свою сферу на плоскость в равноугольной проекции.

По вопросу 2: перед вычислениями просто сдвинь координаты так, чтобы ни одна сторона многоугольника не пересекала проблемный меридиан.

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

А как с полюсами?

Плохо.

Для простоты — контур не включаем.

Я бы не сказал - в моём решении и случае с 4-угольником это неплохо так усложняет дело.

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

В общем так - если контур включаем и центр сферы в плоскости треугольника, то попахивает исключительным случаем. Если при этом рассматриваемая точка (пусть будет точка X) вне этой плоскости то однозначно она вне контура. Иначе - исключительный случай и если центр сферы в пределах контура треугольника то треугольник преображается в полусферу и тут рулит банальная логика. Если центр сферы вне контура треугольника, то треугольник преображается в отрезок и, здесь сложнее, навскидку я бы перебрал все пары векторов из центра сферы до пары точек треугольника и выбрал бы пару с самым малым скалярным произведением - пусть эти вектора будут v1 и v2, vx - вектор от центра сферы до точки X. Если векторные произведения [v1 vx] и [v1 v2] пропорциональны с отрицательным знаком, то точка X вне контура; если пропорциональны положительно, тогда точка Х в контуре если скалярное произведение (v1 v2) меньше или равно (v1 vx).

Без этого неясно, с которой стороны плоскостей должна оказаться точка.

У тебя не только сами плоскости есть, но и три конкретные точки на них - вершины треугольника.

Проверяемая точка должна находиться по ту же сторону от плоскости проходящей через две вершины что и третья вершина.

Приплетать когомологии, гомологии, одномерные и двумерные, чтобы сказать что замкнутая непересекающаяся ломаная на сфере задает два многоугольника, а не один... анонимусы такие анонимусы.

Не боитесь попасть в «петлю»? Доказывая некий факт с помощью целой пачки теорем, которые были доказаны с помощью этого же самого факта?

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

Вообще-то треугольник в любом случае делит сферу на два подмножества, одно «внутри» другое «снаружи». Так вот чтобы в принципе говорить о «внутри» и «снаружи» нужно сначала дать непротиворечивое определение, а оно всегда будет содержать такую переменную неявно.

Проверяемая точка должна находиться по ту же сторону от плоскости проходящей через две вершины что и третья вершина.

Логично. Спасибо. А как его узнать? Должен совпасть знак смешанного произведения с 2 векторами в плоскости?

Но выше выяснился недочёт в постановке задачи. Если у 2 вершин общая координата X, сторона многоугольника лежит в плоскости, проходящей через ось глобуса. Если у 2 вершин общая координата Y, сторона лежит в плоскости перпендикулярной оси и через центр сферы не проходящей (если Y не 0). Как провести плоскость в общем случае, в пределе сводящемся к этим двум? Как это принято делать?

Вообще-то треугольник в любом случае делит сферу на два подмножества, одно «внутри» другое «снаружи». Так вот чтобы в принципе говорить о «внутри» и «снаружи» нужно сначала дать непротиворечивое определение, а оно всегда будет содержать такую переменную неявно.

Ну да. Надо было сразу сказать, что треугольник с меньшей площадью.

gdal, geographiclib

Спасибо, смотрю.

По вопросу 2: перед вычислениями просто сдвинь координаты так, чтобы ни одна сторона многоугольника не пересекала проблемный меридиан.

Каким образом? Прибавить ко всем X какое-то число и взять остаток от деления на 360? А как вывести критерий, когда и сколько прибавлять? Загнать все X в (0; 180)?

И есть идеи, что делать с полюсами?

Можно сделать стереографическую проекцию сферы с выколотой точкой на плоскость — имея сферические координаты, легко найти плоские условия на многоугольник, далее задача сводится к обычной задачи принадлежности точки выпуклому подмножеству плоскости.

И есть идеи, что делать с полюсами?

Запретить. Угол между радиус векторами на две точки на сфере д.б. строго меньше 180град. Если равен 180, то не определена сторона треугольника (дуга большого круга или плоскость, проходящая через эти 2 точки и центр сферы(точки на одной прямой не фиксируют плоскость))

Про кратчайшую дугу между 2 точками сферы: https://en.wikipedia.org/wiki/Slerp

Можно сделать стереографическую проекцию сферы с выколотой точкой на плоскость

Тогда нужно рассмотреть особые случаи — проверка принадлежности полюсов к многоугольникам, многоугольник содержащий полюс и многоугольник с вершиной-полюсом. Все остальные вопросы решили выше, вроде.

что делать с полюсами?

Запретить.

Невозможно.

Угол между радиус векторами на две точки на сфере д.б. строго меньше 180град.

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

https://en.wikipedia.org/wiki/Slerp

Спасибо, но выше выяснилось, что стороны многоугольников могут не быть кратчайшими расстояниями.

так задача плоская?

или нет? Сфера, но у каждой точки по две координаты? Нужно уж определиться.

в плоском случае чуть-чуть легче, никакие библиотеки не нужны. 1. ВАЖНО: координаты на круге в сферических координатах называются \rho и \phi (еще может быть \theta если всё-таки 3Д). Из них элементарно считаются декартовы x, y, (и возможно z).

2. Чтобы выяснить, лежит ли точка (x,y) внутри треугольника, заданного вершинами 1, 2, 3, нужно сравнить сумму площади 3х треугольников (по две вершини и исходная точка (x,y)) с площадью исходного треугольника. Если больше - то вне; если равна - то внутри.

4. Для выпуклого четырехугольника алгоритм тот же (только нужно 4 треугольника). Для не выпуклого еще проверить кой-чего

ФСЁ

если же не плоская и исходные x,y - это сферические координаты, то сначала нужно объяснить что значит «точка лежит внутри его границ»

выше выяснилось, что стороны многоугольников могут не быть кратчайшими расстояниями.

Как так? Как же тогда определяется «прямая, проходящая через две точки» на сфере?

Если у 2 вершин общая координата Y, сторона лежит в плоскости перпендикулярной оси и через центр сферы не проходящей (если Y не 0).

Нет. Прямая на сфере это всегда «большой круг», то есть сечение сферы плоскостью проходящей через центр сферы. И абсолютно всё равно какие там координаты, через две точки на сфере плюс её центр можно построить плоскость и именно сечение сферы этой конкретной плоскостью - это сторона многоугольника.

Первый курс или второй?

Многоугольник на сфере не определяется набором вершин.