Лежит ли одна фигура внутри другой?

[Hoborg]

Здравствуйте. Интересует вопрос, существуют ли какие-нибудь универсальные методы для ответа на вопрос из заголовка (лежит ли одна фигура внутри другой)? В идеале хотелось бы получить метод для анализа не только на плоскости, но и в пространстве произвольной размерности. А ещё можно не только для вещественных чисел, но и просто для множеств любой природы. Может кто-то подсказать, в какую сторону копать (или не копать, т. к. ответ окажется на поверхности)?

Что очевидного:
1) если внутренняя фигура - это просто точка, а внешняя задана уравнением, подставляем координаты точки в уравнение фигуры и вычисляем, являются ли они корнем;
2) если внутренняя фигура - это отрезок, а внешняя задана уравнением и выпукла, подставляем координаты концов отрезка в уравнение фигуры и вычисляем, являются ли они корнями.

[Алексей К.]

Hoborg в сообщении #755043 писал(а):

Что очевидного:
1) если внутренняя фигура - это просто точка, а внешняя задана уравнением, подставляем координаты точки в уравнение фигуры и вычисляем, являются ли они корнем;

Названное Вами "очевидным" по мне таковым не является. "Корни " --- это для того, чтобы узнать, на границе, или нет. А Вам надо внутри.
Возьмите "фигуры" $1-x^2-y^2=0$, или $y-\sin x=0$, наковыряйте от фонаря дюжину точек, и затестите своё утверждение. "Фигуру" придётся, похоже, как-то определить. Чо-то не припомню участия этого слова в серьёзных математических заявлениях.

[JMH]

Задача теоретическая или вычислительная?

[Евгений Машеров]

Смотря, как заданы фигуры.
Скажем, если можно выписать уравнения их границ в полярных координатах $\pho=pho(\varphi)$ и $\r=r(\varphi)$, причём начало координат лежит внутри предположительно "внутренней" фигуры $\pho=pho(\varphi)$, то задача сводится к проверке неравенства
$r > \pho $ для всех $\varphi$
И для декартовых можно, только помнить, что у фигур есть верхняя и нижняя границы, и проверять обе.
А если фигуры есть выпуклые многоугольники с заданными координатами вершин, то нужно проверить для вершин "внутренней" фигуры, принадлежат ли они внутренности "внешней", для чего посмотреть их расположение относительно "внешней".

[sergei1961]

Даже задача локализации точки относительно многоугольника (лежит ли точка с заданными координатами внутри, снаружи или на границе многоугольника с заданными вершинами) является нетривиальной. Кстати, один из неожиданных способов решения-это составить интеграл Коши $\int\limits_{granitsa}\frac{dz}{z-tochka}$ и вычислить его. Если он равен нулю, то снаружи, если $2\pi i$, то внутри, ну а на границе особый разговор...

[nnosipov]

Можно и без интегралов: выпустить из точки луч и подсчитать, сколько раз он пересечёт границу.

[sergei1961]

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

[nnosipov]

sergei1961 в сообщении #755183 писал(а):

Кроме того, наверное, указанный Вами метод предполагает выпуклость многоугольника, а бывают невыпуклые

Для невыпуклых тоже верно.

sergei1961 в сообщении #755183 писал(а):

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

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

[sergei1961]

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

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

[Hoborg]

Большое спасибо за развёрнутые и конструктивные сообщения.

Алексей К. в сообщении #755061 писал(а):

Названное Вами "очевидным" по мне таковым не является. "Корни " --- это для того, чтобы узнать, на границе, или нет. А Вам надо внутри.

Согласен, сел в лужу. Впрочем, когда я писал это, то имел в виду фигуры, задаваемые неравенствами. Например, $x^2 + y^2 \leqslant 4$. Подставив сюда координаты конкретной точки, выясняем, выполняется ли неравенство.

JMH в сообщении #755069 писал(а):

Задача теоретическая или вычислительная?

Теоретическая. Хотя, как я теперь вижу, и "вычислительно" тут всё не так радужно.

[ewert]

sergei1961 в сообщении #755169 писал(а):

Кстати, один из неожиданных способов решения-это составить интеграл Коши $\int\limits_{granitsa}\frac{dz}{z-tochka}$ и вычислить его.

А как Вы, собственно, собираетесь его вычислять?...

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

sergei1961 в сообщении #755192 писал(а):

Для областей с самопересечениями методы лучей не работают.

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

[sergei1961]

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