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

[slavav]

B@R5uk, диаграмму Вороного на сфере можно строить напрямую: https://www.google.ru/search?q=voronoi+diagram+on+sphere&oq=voronoy+diagram+on+s&aqs=chrome.1.69i57j0l5.9643j0j7&sourceid=chrome&ie=UTF-8.
А можно заметить что сферическая диаграмма есть сужение трёхмерной (пространственной) диаграммы для тех же точек.

[arseniiv]

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

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

Даже не знаю, честно говоря (и вообще плохой советчик литературы, читаю в основном для себя). Ну вот в курсах линейной алгебры упомянутые здесь группы обычно рассматриваются — у Кострикина, например («Введение в алгебру», конкретно том 2 для линейной, но стоит убедиться, что изложенные в томе 1 основные штуки известны), но не имею понятия, насколько даже он подойдёт по критерию «без заумной математики». Вообще для обсуждаемой темы какие-то особые сведения о группах симметрий, вроде, и не нужны.

-- Сб дек 30, 2017 19:51:13 --

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

[B@R5uk]

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

[slavav]

Это точно не правда. Рассмотрите экватор и близкую точку. Рядом с точкой вы получите почти параболу (из-за предельного перехода к плоскости). А вдали она замкнётся.
Но это и не нужно. Алгоритм Форчуна не использует свойства парабол. Вам надо строить круговые события - это просто. И вам надо делать вставку новой "параболы" во фронт - тоже не сложно.
Еще рекомендую посмотреть "разделяй и властвуй". Кажется его адаптировать проще.

[grizzly]

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

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

Так будет только если заданная точка совпадает с центром заданной окружности.

[B@R5uk]

grizzly в сообщении #1280210 писал(а):

Так будет только если заданная точка совпадает с центром заданной окружности.

Разве? А по-моему если масштабировать плоскость с центром в заданной точке с коэффициентом 1/2, то исходная окружность как раз перейдёт в искомое ГМТ. И это снова будет окружность. Или я не прав?

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

Это точно не правда. Рассмотрите экватор и близкую точку. Рядом с точкой вы получите почти параболу (из-за предельного перехода к плоскости). А вдали она замкнётся.

Ну так всё правильно! На малом масштабе парабола и окружность/эллипс не отличимы же!

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

Но это и не нужно. Алгоритм Форчуна не использует свойства парабол. Вам надо строить круговые события...

Спасибо за уточнение! Значит сначала надо внимательно разораться с плоским алгоритмом. В статье на хабре как-то слишком бестолково, "не для чайников" написано.

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

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

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

[grizzly]

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

А по-моему если масштабировать плоскость с центром в заданной точке с коэффициентом 1/2, то исходная окружность как раз перейдёт в искомое ГМТ. Разве нет?

Не могу сказать. Я Вас не понимаю.

-- 30.12.2017, 23:30 --

B@R5uk
У Вас, наверное, заданная точка лежит внутри заданной окружности?

[B@R5uk]

grizzly в сообщении #1280241 писал(а):

Не могу сказать. Я Вас не понимаю.

Вот те раз! Преобразование подобия же.

grizzly в сообщении #1280241 писал(а):

У Вас, наверное, заданная точка лежит внутри заданной окружности?

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

[grizzly]

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

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

Чтобы понять это, нужно где-то применить преобразование подобия? К исходной или к исходной? Дайте какой-нибудь поясняющий рисунок, пожалуйста, или просто забудем.

[slavav]

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

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

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

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

. Разбейте сферу на две половинки. Для каждой половины понятие выпуклой оболочки хорошо определено.

[arseniiv]

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

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

А зачем для этого бесконечно удалённая точка?

[B@R5uk]

grizzly в сообщении #1280253 писал(а):

или просто забудем.

Лучше предложите свою версию ГМТ.

arseniiv в сообщении #1280268 писал(а):

А зачем для этого бесконечно удалённая точка?

Ну, мне для понимания что значит "снаружи" такая точка нужна.

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

Разбейте сферу на две половинки.

Лучше уж тогда полюс какой-нибудь выколоть, что ли. Зачем плодить сущности без необходимости? Я находил в интернетах статью, предлагающую разбить сферу на две части, каждую спроецировать на плоскость и тогда решать (если я правильно понял их подход к задаче). Мне два момента сразу не понравились: разбиение и проецирование. В смысле в подходе "разделяй и властвуй" разбиение — это хорошо, вместо O(n) выходит O(log n), а вот почему нельзя обойтись с целой сферой — не понятно.

[grizzly]

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

Лучше предложите свою версию ГМТ.

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

[slavav]

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

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

[B@R5uk]

grizzly в сообщении #1280279 писал(а):

другая часть -- незамкнутая, снаружи

Теперь я понял, в чём у меня проблема: я расстояние между точками ГМТ и окружностью не правильно измерял. Спасибо за разъяснение.

-- 31.12.2017, 02:26 --

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

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

Да-да. Вот этот переход от плоскости к сфере мне тоже был не очевиден. А вы можете дать ссылочку на более-менее подробное описание алгоритма со сферой, если такое есть?