Внутренние точки контура на криволинейной поверхности

[disednet]

Есть задача:
Дана полигональная сфера, где четко определена связь полигонов(общие вершины), сфера с одной стороны деформирована (вдавлена). Так же дан контур, спроецированный на поверхность деформированной сферы, как показано на рисунке, координаты его проекций на каждый полигон известны. И имеются 2 произвольные точки, например, $\mathrm{A}$, $\mathrm{B}$(показаны на рисунке). Требуется определить лежат ли эти точки внутри заданного контура.



Как я начал ее решать. Для определения находится ли точка внутри контура использовал классический алгоритм Задача о принадлежности точки многоугольнику (учёт числа пересечений). Для этого соответственно производил переход из $\mathbb{R}^3$ в $\mathbb{R}^2$ пространство, т.е. сделал развертку исходной фигуры на плоскость. При этом положение каждого полигона в $\mathbb{R}^2$ определяется только правилами построения развертки и, в общем случае, не обязательно делать классическую развертку, а можно просто "разбить" сферу, т.е. считать, что каждый полигон находится в произвольном месте плоскости(единственное условие, что "нормали смотрят вверх", т.е. лицевые стороны полигонов смотрят на нас). Так на рисунке ниже приведена схема 2-х смежных полигонов, серой линией показаны связи по общим точкам, красной показано, что линия замкнутого контура переходит с одного полигона на другой. Сначала я строю отрезок из точки $\mathrm{A_1}$ в произвольном направлении, получаем отрезок $\mathrm{A_1C_1}$ в системе координат, построенной на базисе $\{x,y\}$. Определяю пересечение отрезка $\mathrm{A_1C_1}$ с $L_1$. Далее надо оценить этот же отрезок относительно второго полигона (на рисунке "2") и его сегмента $L_2$. Просто оценить не выйдет, т.к. в текущей момент имеется разрыв контура на сегменты $L_1$ и $L_2$.
Я делаю так:
- считаю, что базис первого полигона и второго построенные по смежной стороне $c_1^1c_2^1$($c^2_1c^2_2$) одинаковы, а система координат имеет ноль в точке $c_1^1$($c_1^2$), загвоздка только в том, что полигоны разбросаны на плоскости (но связи остались и мы можем найти смежные полигоны для данного);
- определяю координаты $\mathrm{A_1C_1}$ в СК, построенной на базисе $\{x_1,y_1\}$ (начинаю как и говорил с первого полигона)
- поскольку, считаю, что системы координат, построенные на базисах $\{x_1,y_1\}$ и $\{x_2,y_2\}$ "совпадают" (т.к. полигоны смежные изначально по $c_1c_2$), т.е. можем полученные координаты отрезка $\mathrm{A_1C_1}$ для СК на базисе $\{x_1,y_1\}$ считать равными координатам в СК на $\{x_2,y_2\}$, а потом найдя матрицу перехода из из базиса $\{x,y\}$ в $\{x_2,y_2\}$ получить координаты $\mathrm{A_2C_2}$.
- далее просто оцениваем пересечения $\mathrm{A_2C_2}$ и $L_2$
- делаю аналогично для всех полигонов



Вопросы:
1. может есть другой способ решения подобной задачи (возможно, выше я написал , мягко говоря, не лучшее решение), буду благодарен за указание верного направления в решение подобной задачи
2. если взять спущенный футбольный мяч (с вмятиной как на представленной модели), сшитый из пентагонов (есть информация о связи смежных пентагонов), его разворачиваем в $\mathbb{R}^2$, т.е. "расшиваем" где надо. Далее в $\mathbb{R}^2$ ставим точку внутри одного из пентагонов и из нее пускаем луч в произвольном направлении, когда луч пересекает границу исходного пентагона, он должен переходить в другой (как если бы мы пускали луч по поверхности сферы) и возвращаемся в исходную точку, естественно, он проходит и по "впуклости" мяча надо. Как используя $\mathbb{R}^2$ СК и информацию по связи смежных пентагонов построить такой луч, проходящий через множество пентагонов.

[Lia]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Математика (общие вопросы)»

[slavav]

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

-- 18.01.2018, 01:25 --

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

[SomePupil]

disednet в сообщении #1284691 писал(а):

Так же дан контур, спроецированный на поверхность деформированной сферы, как показано на рисунке, координаты его проекций на каждый полигон известны.

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

Потому что в этом случае дело сводится к нахождению корня функции расстояния между проекциями и заданными точками.

P. S. Если серьезно, как именно заданы полигоны и контур?

[disednet]

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

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

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

-- 18.01.2018, 09:35 --

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

Как вы задаёте точки $A$ и $B$?

Координаты в $\mathbb{R}^3$, т.е. эти точки находятся на поверхности сферы (это могут быть и узловые точки полигональной сетки)

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

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

Вот в этом то и вся загвоздка, потому как я пробую определять положение точки только внутри замкнутого контура в $\mathbb{R}^2$, а один полигон содержит лишь один сегмент контура (в общем случае не больше одного). Я могу конечно определить находится ли $A$ слева или справа от заданного сегмента, в данном контуре, что конечно не достаточно для определения находится ли точка внутри контура.

-- 18.01.2018, 09:40 --

SomePupil в сообщении #1285286 писал(а):

P. S. Если серьезно, как именно заданы полигоны и контур?

Ответил в предыдущем посте.
Не очень понял с корнем расстояния между точками и проекцией контура, имеется в виду, что такое решение возможно, если все задано в виде функций?

[slavav]

Ага, есть контур "нарисованный" на отдельных полигонах. Этого не достаточно: представьте немятую сферу и контур проходящий вблизи экватора. Что считать его внутренностью? Какое полушарие? Выбрать, видимо, нельзя. Надо явно задать какую-нибудь точку на сфере ($I$), про которую будет известно что она внутри контура. Этого достаточно.
Понадобится знание взаимного расположения полигонов: для любого полигона должна быть возможность перечислить его соседей через общие рёбра.
Все полигоны через которые проходит контур красим в серый цвет.
Полигон содержащий точку $I$ красим в белый, всех его ещё не крашенных соседей тоже в белый и так далее. В конце концов мы закрасим белым все полигоны внутри контура.
Те полигоны, который ещё не покрашены красим чёрным - они снаружи от контура.
Теперь займёмся серыми полигонами.
Пусть точка $A$ попала в серый полигон. Если у него есть белый полигон-сосед, то проводим отрезок от $A$ до любой точки на их общей стороне. Считаем чётность числа пересечений контура с отрезком. По нему определяем принадлежность $A$. То же делаем если есть чёрный полигон-сосед.
Если полигоны мелкие а контур не делает резких поворотов, то такой алгоритм всегда определит принадлежность точки $A$.

[disednet]

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

Этого не достаточно: представьте немятую сферу и контур проходящий вблизи экватора. Что считать его внутренностью?

Если контур проходит по экватору, то мы можем с равной долей вероятности считать любое из полушарий внутренней частью. Но как правило, в решаемой задаче такого не случается. Собственное, мне по задаче и надо найти такую $I$ (вариантов ее начального задания нет), а далее я просто использую метод закраски (очень похожий на то, что вы описали) для определения всех внутренних и внешних точек; после закраски я просто считаю каких полигонов\точек меньше, поскольку, они то и будут внутренними.

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

Пусть точка $A$ попала в серый полигон. Если у него есть белый полигон-сосед, то проводим отрезок от $A$ до любой точки на их общей стороне. Считаем чётность числа пересечений контура с отрезком. По нему определяем принадлежность $A$. То же делаем если есть чёрный полигон-сосед.

Такой подход сработает если все сегменты контура и построенный отрезок будут лежать в одной плоскости, но у нас исходная сетка в $\mathbb{R}^3$, и часть сегментов просто не будет пересечено заданным отрезком. Собственно, в первом посте я и описал подобную ситуацию и как я вынужден перейти в $\mathbb{R}^2$, с сохранением связей полигонов. Мой подход работает, но мне не дает покоя мысль, что я слишком сложно решил данную задачу. Но как говорится, я могу и сильно ошибаться.

[slavav]

Построение для точки $A$ в сером полигоне делается внутри этого полигона. Вы сказали что внутри полигона всё плоское: и сегмент контура и отрезок и сам полигон. Теперь вы говорите что это не так?

[disednet]

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

Вы сказали что внутри полигона всё плоское: и сегмент контура и отрезок и сам полигон. Теперь вы говорите что это не так?

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

-- 18.01.2018, 16:43 --

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

Построение для точки $A$ в сером полигоне делается внутри этого полигона

Но тогда мы оценим пересечение построенного на $A$ отрезка только для сегмента контура, расположенного только в данном полигоне, а как быть с остальными?

[slavav]

С остальными? Вы ставите меня в тупик.
Есть точка в сером полигоне. Вы установили что отрезок от неё до ребра смежного с белым полигоном пересекается с контуром ноль раз. Тогда сама точка внутри. Это рассуждение ясно?
Или вы установили что отрезок от точки до белого ребра пересекается с контуром чётное число раз. Тогда сама точка внутри. Это рассуждение ясно?
Никакие части контура вне этого полигона не рассматриваются.

Я подразумеваю что верна такая лемма:
Лемма: пусть $I$ внутри контура, пусть отрезок $[I, A]$ не пересекается с контуром, тогда $A$ внутри контура.
Вы согласны что эта лемма верна?
Та же лемма останется верной если "не пересекается" заменить на "пересекается чётное число раз".

[disednet]

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

Есть точка в сером полигоне. Вы установили что отрезок от неё до ребра смежного с белым полигоном пересекается с контуром ноль раз. Тогда сама точка внутри. Это рассуждение ясно?
Или вы установили что отрезок от точки до белого ребра пересекается с контуром чётное число раз. Тогда сама точка внутри. Это рассуждение ясно?
Никакие части контура вне этого полигона не рассматриваются.

Да тут все понятно.

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

Я подразумеваю что верна такая лемма:
Лемма: пусть $I$ внутри контура, пусть отрезок $[I, A]$ не пересекается с контуром, тогда $A$ внутри контура.
Вы согласны что эта лемма верна?
Та же лемма останется верной если "не пересекается" заменить на "пересекается чётное число раз".

Согласен.
Но осталось главное - нет изначальной точки $I$, что не дает возможность проверить лемму, а стало быть нету и изначальной закраски, что делает невозможным тест с отрезком контура в сером полигоне. Собственно, как я писал, суть задачи и заключается в поиске точки $I$ (в первом посте я обозначил точки $A$, $B$ как кандидаты в $I$). А уже когда я найду такую точку, то тогда я смогу и сделать закраску. Для поиска подобной точки я беру 4 точки полигона содержащего сегмент контура и произвожу анализ каждой из них в $\mathbb{R}^2$, подробно я описал в первом посте.

[slavav]

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

[Dmitriy40]

Скажу может уже высказанную идею, но всё же.
Постулат: обе проверяемые точки находятся в полигонах, которые не содержат контура. Если он не выполняется - делим соответствующий полигон на части до выполнения постулата. Если полигон на каком-то шаге оказался меньше атома (или любого другого порога) - считаем точку лежащей на контуре и вопрос бессмысленным.
Далее пускаем обычную волну из первой точки в соседние полигоны. При этом возможны следующие случаи:
1) волна наткнулась на вторую точку - задача решена, обе точки с одной стороны контура (или обе внутри, или обе снаружи);
2) волна наткнулась на контур (полигон с контуром) - останавливаем волну в эту сторону;
3) не осталось свободных от волны полигонов - задача решена, точки по разную сторону контура.
Требуемая память $O(\sqrt{n})$, $n$ общее количество полигонов (достаточно хранить лишь фронт волны, а это в некотором смысле окружность, длина которой именно как корень из покрываемой площади). Сложность в худшем случае кажется $O(n)$ т.к. может потребоваться перебор (почти) всех полигонов.
Фактически это аналог закраски полигонов внутри контура и проверки цветов полигонов с точками.
Математики кроме понятия связности (соседства) полигонов не требуется, делить полигоны для выполнения постулата можно любым наитупейшим образом.

[disednet]

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

Dmitriy40
Да , этот подход уже описан slavav. И по условию задачи мне не надо определять, что точки с одной стороны или с разных, нужно просто сказать с какой стороны заданная точка, а в задаче точек может быть ${1..n}$.