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

[B@R5uk]

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

Еще рекомендую посмотреть "разделяй и властвуй". Кажется, его адаптировать проще.

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

В случае, когда точка пересечения лежит внутри треугольника, то всё понятно: выбирается та половинка, которая пересекает сторону. А что делать в случае, когда вершина Вороного лежит вне треугольника? И как это вообще можно отследить?

[slavav]

Не надо расстояний. Выбирайте то пересечение для которого внутренность круга свободна от других точек.

[B@R5uk]

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

внутренность круга свободна от других точек

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

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

[slavav]

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

Зачем вам проверять что центр описанной окружности внутри треугольника? На плоскости это не так.

Правильный критерий - проверять пустоту внутренности круга.

[B@R5uk]

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

которые сходятся в центре пустой окружности.

Совершенно вас не понимаю. Они все шесть сходятся в одной точке!

[slavav]

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

[B@R5uk]

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

Если у вас вообще только три точки, то вы имеете сразу две вершины диаграммы.

Вот! Именно про этот случай я и спрашиваю: как из шести рёбер графа правильно выбрать три?

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

[slavav]

Я не уверен что вы и я используем одно и то же определение диаграммы Вороного.
Я использую определение через ближайшие точки или через максимальную пустую окружность.
Диаграмма Вороного - это функция определённая на сфере. Пусть $S$ множество точек на сфере для которого определяется диаграмма. Тогда диаграмма по точке $q$ сферы возвращает подмножество $S$ состоящее из наиболее близких точек:
$Vor_S(q) = \{p|p \in S, dist(q, p) = dist(q, S)\}$, где $dist(q, S) = \min\limits_{p \in S} dist(q, p)$.
Тогда вершина диаграммы для точек $p_1, p_2, p_3$ это $\{q | Vor_S(q) = \{p_1, p_2, p_3\}\}$. На плоскости вершина - пустое или одноточечное множество. На сфере вершина может состоять из пары точек, но это вырожденный случай.
Ребро определяется аналогично. С таким определением ребра ясно как выбрать нужный участок полного круга. Пусть даны точки $p_1, p_2, p_3$. Полный круг для точек $p_1, p_2$: $\{q|dist(q, p_1) = dist(q, p_2)\}$. Для любой точки круга если $dist(q, p_1) < dist(q, p_3)$, то это точка на ребре, иначе нет. На каждом из полукругов достаточно проверить одну точку.

-- 02.01.2018, 15:51 --

Вы правильно подметили про треугольники. Есть такая микролемма: если треугольник остроугольный, то он содержит вершину диаграммы. Но это тупик. Вы дальше продвинетесь если будете работать только с расстояниями. Функции $dist$ и $Vor_S$ позволяют получить больше результатов в более общей форме.

[B@R5uk]

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

Я использую определение через ближайшие точки или через максимальную пустую окружность.

Диаграмма Вороного — это же не только вершины, но и рёбра их соединяющие, а в случае плоскости она включает в себя ещё и бесконечные лучи. Или я не прав?

-- 02.01.2018, 17:59 --

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

Я не уверен что вы и я используем одно и то же определение диаграммы Вороного.

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

-- 02.01.2018, 18:04 --

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

Для любой точки круга если $dist(q, p_1) < dist(q, p_3)$, то это точка на ребре, иначе нет. На каждом из полукругов достаточно проверить одну точку.

Вот это интересная идея. Спасибо!

[slavav]

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

Но если задача стоит, например, нарисовать диаграмму Вороного?

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

-- 02.01.2018, 19:45 --

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

Диаграмма Вороного — это же не только вершины, но и рёбра их соединяющие, а в случае плоскости она включает в себя ещё и бесконечные лучи. Или я не прав?

Вы правы. Функция Вороного возвращает не одну ближайшую точку, а все ближайшие точки. Например, ребро $e_{ij} = \{q | Vor_S(q) = \{p_i, p_j\}\}$. Отсюда следует что ребро это пустое множество или прямая или открытый интервал или открытый луч (это все открытые выпуклые подмножества прямой).

[B@R5uk]

Наконец то всё заработало для трёх точек:


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

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

-- 03.01.2018, 14:59 --

Я тут, кстати, заметил одно забавное свойство, которое отличает сферический треугольник от плоского. На плоскости любое сечение треугольника, параллельное одной из сторон всегда короче этой стороны. Сферический же треугольник может оказаться "шире" той стороны, на которой он "стоит". В связи с этим возникает вот какой вопрос. На плоскости две самые удалённые точки любого треугольника — это всегда одна из пар его вершин. Выполняется ли это правило для сферического треугольника?

Пример "жирного" сферического треугольника:

[slavav]

Я бы начал с построения одной ячейки Вороного. Её можно представить как пересечение полусфер.

-- 03.01.2018, 16:02 --

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

[B@R5uk]

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

Я бы начал с построения одной ячейки Вороного.

Не понял: какой именно ячейки? Их же несколько новых появится при добавлении точки.

Я тут сейчас пытаюсь вникнуть в один вопрос: при слиянии двух диаграмм Вороного будут ли нужны координаты сайтов? Или можно будет обойтись без них? Потому что при добавлении только одного сайта координаты соседних точно понадобятся для расчётов новых вершин диаграммы. То есть получается, что диаграмма Вороного строится совместно и нераздельно с триангуляцией Делоне, верно?

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

Выполняется ли это правило для сферического треугольника?

Не выполняется. Контрпримером будет любой равносторонний треугольник с углами, большими прямого угла. У него расстояние от любой вершины до центра противоположной стороны будет больше его стороны. Поскольку верхняя граница на сумму углов сферического треугольника равна $3\pi$, треугольник с такими углами всегда найдётся.

[slavav]

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

Не понял: какой именно ячейки?

Я предлагаю построить одну ячейку (грань диаграммы Вороного) вокруг одной точки. Если вы построите все такие многоугольники - диаграмма готова.

[B@R5uk]

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

Если вы построите все такие многоугольники - диаграмма готова.

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

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