Попадает ли точка в треугольник на сфере

[snake32]

Доброго времени! Собственно сабж. Имеется три точки треугольника на сфере и точка на сфере. Определить попадает ли точка внутрь сферического треугольника.
Все точки заданы в сферических координатах долгота,широта $(\text{lon},\text{lat})$
Спасибо.

[ewert]

Формальный ответ: попадает (на сфере и с одной, и с другой стороны -- треугольник).

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

(ибо сферический случай к нему с определёнными оговорками сводится)

[worm2]

Возможно, тема "Уравнения больших и малых кругов на сфере" поможет (малые круги нам без надобности, только большие). Но не ждите коротких формул.

[snake32]

Цитата:

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

Таких решений полно в интернете. И все они сводятся к проверки суммы углов то есть:
Если точка $P$ попадает внутрь треугольника $ABC$, то сумма углов $\angle APB + \angle APC + \angle BPC = 180$. Так как сумма углов плоского треугольника всегда $= 180$.
Однако у сферического треугольника сумма углов больше $180$ отсюда эту формулу я не могу использовать.... или могу?
Допустим я вычислю сумму углов треугольника. Можно ли будет эту цифру сравнивать по аналогии с плоским?

Цитата:

Возможно, тема "Уравнения больших и малых кругов на сфере" поможет

Не совсем понял как это относится к моей задаче...

[TOTAL]

snake32 в сообщении #637582 писал(а):

Все точки заданы в сферических координатах долгота,широта (lon,lat)

Для каждой точки по сферическим координатам найдите вектор, идущий из центра сферы в точку.Вычислите определитель матрицы, строки которой являются компонентами векторов - вершин тр-ка. Затем замените первую (вторую, третью) строку на компоненты вектора - контрольной точки.

Чтобы контрольная точка находилась внутри тр-ка, все 4 определителя должны быть одного знака.

[CptPwnage]

Мне кажется будет лучше так проверять: точка внутри тогда и только тогда когда сумма площадей трех маленьких треугольников равна площади большого.

[snake32]

TOTAL
Пока остановился на вашем варианте.
Можете в двух словах объяснить геометрический смысл детерминанта матрицы из вершин треугольника?

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

Осталось посмотреть какой вариант будет эффективнее. Спасибо.

ЗЫ Если есть ещё варинты буду рад выслушать.

[ewert]

snake32 в сообщении #637710 писал(а):

Можете в двух словах объяснить геометрический смысл детерминанта матрицы из вершин треугольника?

Это ориентированный объём параллелепипеда, построенного на соответствующих векторах, выходящих из центра сферы. Равенство знаков означает, что все четыре тройки векторов ориентированы одинаково: либо все правые, либо все левые.

[snake32]

Цитата:

Это ориентированный объём параллелепипеда, построенного на соответствующих векторах, выходящих из центра сферы

Может тогда пирамиды?

Через детерминант вроде работает:

function TGeoTriangle.IsInside( const pt:TGeoPoint ):Boolean;
  var m,t:TMat3; v:TVec3; i:integer; isNeg:Boolean;
begin
  m.rows[0] := points[0];
  m.rows[1] := points[1];
  m.rows[2] := points[2];
  v := pt;
  Result := true;
  isNeg := m.det < 0;
  i:=0;
    while (i<3) do
    begin
      t := m;
      t.rows[i] := v;
      if(( t.det>=0 )and isNeg )or(( not isNeg )and( t.det<0 ))then
        exit( false );
      Inc( i );
    end;
end;

-- Вт окт 30, 2012 17:36:30 --

Для полного счастья мне не хватает ф-ии вычисления угла: то есть имеется всё те же $3$ точки $A,B,C$ в сферических координатах $(\text{lon},\text{lat})$
Нужен угол $\angle ABC$, например.

[TOTAL]

snake32 в сообщении #637782 писал(а):

Нужен угол ABC, например.

Это угол межде векторами $\vec a = \vec A - \vec B (\vec A \cdot \vec B)$ и $\vec c =\vec C - \vec B (\vec C \cdot \vec B)$.

Здесь $\vec A, \vec B, \vec C $ - единичные векторы из центра сферы в соотв. точки, $(\vec A \cdot \vec B)$ - скалярное произведение.

Векторы $\vec a, \vec c$ норимируете, затем находите их скалярное произведение, т.е. узнаете косинус угла между ними.

------------------------------------------------------------------------------

      if(( t.det>=0 )and isNeg )or(( not isNeg )and( t.det<0 ))then

Почему вот эту не записать как

      if( t.det*SignD < 0 )then

где в SignD занесен знак основного определителя?

[snake32]

Цитата:

Почему вот эту не записать как

Да...согласен, так лучше будет - меньше условий в цикле.

function TGeoTriangle.IsInside( const pt:TGeoPoint ):Boolean;
  var m,t:TMat3; v:TVec3; i:integer; signD:single;
begin
  Result := true;

  m.Row[0] := Point[0];
  m.Row[1] := Point[1];
  m.Row[2] := Point[2];
  v := pt;

  signD := m.det;
  i:=0;
  repeat
    t := m;
    t.Row[i] := v;
    if( t.det*signD < 0 )then
      exit( false );
    Inc( i );
  until i>2;
end;

А вот что получилось с вычислением угла(не проверял ещё):

function TGeoPoint.Angle( const A,B:TGeoPoint ):single;
  var vA,vB,vSelf:TVec3;
begin
  vA := A; vB := B; vSelf := self;
  vA := vA - vSelf * ( vA and vSelf ); vA.Normalize;
  vB := vB - vSelf * ( vB and vSelf ); vB.Normalize;
  Result := arccos( vA and vB );
end;

Огромное спасибо, TOTAL!!
ЗЫ: vA and vB - перегрузка оператора - скалярное произведение
ЗЗЫ: Вот это я понимаю форум! И формулы подсказали и программировать научили.

[TOTAL]

snake32 в сообщении #637877 писал(а):

  signD := m.det;
     if( t.det*signD < 0 )then

Так опасно, надо именно знак присваивать!
(из-за угрозы получить ноль от перемножения маленьких чисел)

[ewert]

TOTAL в сообщении #637881 писал(а):

(из-за угрозы получить ноль от перемножения маленьких чисел)

Нет такой угрозы. Мы ж их не вычитаем.

snake32 в сообщении #637782 писал(а):

Может тогда пирамиды?

Нет.

[snake32]

Не хотелось лепить if но на всякий случай сделал так:(может можно обойтись без ifa?)

if( m.det < 0 )then signD := -1.0
                 else signD :=  1.0;

Цитата:

Нет.

Тогда совсем не понятно, как имея всего 4 точки(3 треугольника и центр сферы)в 3д пространстве можно построить параллелепипед который имеет обычно 8 вершин

[TOTAL]

snake32 в сообщении #638136 писал(а):

Не хотелось лепить if но на всякий случай сделал так:(может можно обойтись без ifa?)

if( m.det < 0 )then signD := -1.0
                 else signD :=  1.0;

Цитата:

Нет.

Тогда совсем не понятно, как имея всего 4 точки(3 треугольника и центр сферы)в 3д пространстве можно построить параллелепипед который имеет обычно 8 вершин

Если нет встроенной функции типа signD:=Sign(m.det), то лучше, как сказал ewert, не заморачиваться и оставить сам определитель, так как фактически в проверке условия a*b < 0 компьютер проверяет только знаки сомножителей. На моем компьютере точность проверки уменьшается, только если сначала присвоить c=a*b, а затем проверить c< 0. Так что "опасность" сильно преувеличена, извиняюсь.

По трем ребрам (векторам), выходящим из одной вершины параллелепипеда, этот пипед восстанавливается однозначно.