Сферическая планиметрия (сферометрия?)

[slavav]

Я следую такому правилу: не думать об эффективности пока не построен простейший корректный алгоритм. С этой точки зрения строить ячейки - кратчайший путь к рабочему варианту.

[B@R5uk]

B@R5uk в сообщении #1280098 писал(а):

Лучшее, что я смог придумать — это объединить их в одну, используя арктангенс двух аргументов:

$\[x={{\arctg}_{2}}\left( 2y\sqrt{1-{{y}^{2}}},1-2{{y}^{2}} \right)\]$

Получился тот ещё крокодил.

Придумал очень красивое и, возможно, даже более точное вычисление расстояния на сфере. Для этого всё так же используется арктангенс двух аргументов, поскольку расстояние на сфере — это угол между радиус-векторами точек, для которых оно измеряется. Причём косинус этого угла входит в скалярное, а синус — в векторное произведения этих векторов. Отсюда простая и прозрачная формула:

$$\alpha ={{\arctg}_{2}}\left( \left| \left[ \overrightarrow{{{r}_{1}}},\overrightarrow{{{r}_{2}}} \right] \right|,\left( \overrightarrow{{{r}_{1}}},\overrightarrow{{{r}_{2}}} \right) \right)$$

[B@R5uk]

А верно ли, то у ячейки вороного не больше шести соседей?

[slavav]

1. В среднем у ячейки Вороного не больше шести соседей.
2. Не сложно сделать диаграмму с $N$ точками в которой будет ячейка с $N - 1$ соседом.

[B@R5uk]

slavav в сообщении #1281305 писал(а):

В среднем у ячейки Вороного не больше шести соседей.

Понятно, спасибо. А то я помню, что читал что-то такое, но важную подробность не запомнил.

-- 04.01.2018, 23:22 --

slavav в сообщении #1281305 писал(а):

в которой будет ячейка с $N - 1$ соседом.

Правильный $N-1$-угольник с сайтом в центре?

[slavav]

Да.

[B@R5uk]

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

[slavav]

Да.

[B@R5uk]

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

[slavav]

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

[B@R5uk]

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

[slavav]

Да, такую теорему можно доказать.
На плоскости удаляемый кусок не обязан быть связным. Для сферы можно доказать что удаляемый кусок всегда связен.
Имеется ввиду линейная связность для объединения удаляемых вершин и кусков рёбер.

На плоскости удаляемый кусок может не содержать вершин вообще. На сфере всегда удаляется хотя бы одна вершина (если вершины есть). От этой вершины можно поиском по графу построить удаляемый кусок.

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

[B@R5uk]

slavav в сообщении #1281672 писал(а):

На плоскости удаляемый кусок не обязан быть связным.

О! Как так? Можно какой-нибудь наглядный пример?

B@R5uk в сообщении #1281487 писал(а):

Коли это так, то процесс поиска новых вершин диаграммы заметно упрощается

Оказывается, не всё так просто. На сфере у любой окружности два центра и два радиуса, поэтому для каждой тройки вершин всегда есть две потенциальные вершины диаграммы. Я то думал, что достаточно брать ближайшую, причём единственный случай, когда это не работает, — диаграмма из трёх вершин, образующих тупоугольный треугольник. А на самом деле, эта ситуация с выбором из ближней и дальней точки сплошь и рядом, причём в пользу дальней точки голос отдаётся так же часто, как в пользу ближней (если вообще не чаще). Вот, думаю теперь: как этот выбор наиболее грамотно оформить?

[B@R5uk]

Итак, возникла следующая задача. На сфере имеются три точки, например, A, B и C, лежащие на одной сферической прямой (большой окружности). Необходимо определить, лежит ли точка C внутри отрезка AB. Помогите, пожалуйста, понять, как решать такую задачу.

Её плоский аналог решается легко. Берём те соответствующие координаты (X или Y) точек A и B, разность которых больше, затем проверяем, выполняется ли хотя бы одна из систем неравенств $X_A < X_C < X_B$ или $X_B < X_C < X_A$ для выбранной координаты. Если да, то точка лежит внутри отрезка, если нет, то, соответственно, не лежит. Выбирать большую координату необходимо потому, точки могут лежать на вертикальной или горизонтальной прямой и координаты будут одинаковы. Можно не выбирать координату, а проверить четыре системы неравенств: $X_A < X_C < X_B$, $X_B < X_C < X_A$, $Y_A < Y_C < Y_B$ и $Y_B < Y_C < Y_A$ и выдать положительный ответ в случае выполнения хотя бы одной из них.

Однако, такой подход не действует на сфере. Там нет такого естественного упорядочивания координат, какой есть на плоскости. Поэтому сравнивать координаты не выйдет. Можно было бы воспользоваться проверкой расстояний. То есть считать, что точка C лежит вне отрезка AB, если $\left|AC\right| + \left|BC\right| > \left|AB\right|$. Однако, если точка C лежит внутри отрезка AB, то по идее должно выполнятся равенство $\left|AC\right| + \left|BC\right| = \left|AB\right|$, которое является единственной альтернативой предыдущему неравенству. Но поскольку координаты представляются в компьютере числами с конечной точностью, то не только возможно ложное срабатывание, когда вместо "равно" будет "больше", но и вообще можно получить невозможное: неравенство $\left|AC\right| + \left|BC\right| < \left|AB\right|$ будет выполнено. По этой причине подход через расстояния тоже не работает.

Как быть?

[slavav]

B@R5uk в сообщении #1281736 писал(а):

slavav в сообщении #1281672 писал(а):

На плоскости удаляемый кусок не обязан быть связным.

О! Как так? Можно какой-нибудь наглядный пример?

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

-- 06.01.2018, 19:58 --

B@R5uk в сообщении #1281773 писал(а):

Итак, возникла следующая задача. На сфере имеются три точки, например, A, B и C, лежащие на одной сферической прямой (большой окружности). Необходимо определить, лежит ли точка C внутри отрезка AB. Помогите, пожалуйста, понять, как решать такую задачу.

Спроектировать на плоскость (на окружность) и решить задачу там.
А зачем вам решать такую задачу?