Проецирование графа на сферу

[MGM]

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

[Geen]

А что значит "спроецировать"?

[svv]

Выберите одну вершину $V$, поместите её на северный полюс. Каждая из остальных вершин размещается на тем более южной параллели, чем больше расстояние от неё до $V$.

[slavav]

Выберем на графе простой цикл. Разрежем граф на две половинки. Вершины из цикла отобразим на экватор, сохраняя порядок.

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

[Geen]

Ну вы сейчас говорите про общее отображение...
А задача с "проекцией" может не иметь решения вовсе.

Поэтому хотелось бы услышать ТС.

[MGM]

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

Выберем на графе простой цикл. Разрежем граф на две половинки. Вершины из цикла отобразим на экватор, сохраняя порядок.

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

Звучит заманчиво. Хотя я уже пытался делать что-то подобное. На графе тела человека. Но от полюса. Не совсем удачно. Проблема возникает на условном "поясе" при движении по "ногам". "Пояс" это замкнутый путь (или цикл). Однако на "ногах" циклы несвязаны друг с другом.
Даже если предположить, что имеенно эту проблемную часть я решу, нет уверенности, что сферическое многообразие не имеет более сложных топологических конструкций.

Допустим дерево. По идее надо идти от листьев к стволу. Но понять это для графа общего вида достаточно трудно.

[slavav]

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

[MGM]

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

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

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

-- Вс июн 13, 2021 13:49:24 --

Geen в сообщении #1522234 писал(а):

А что значит "спроецировать"?

Виноват, отобразить. Диплом у меня датирован концом прошлого века, так что моя терминология может сильно хромать.

[slavav]

"вложение планарного графа" означает что он будет вложен без самопересечений.