Когда свободно движущаяся сфера может вырваться из «клетки», определяемой набором непроходимых координат?

Question

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

Пожалуйста, представьте, что я беру свободно движущийся шар в 3-м пространстве и создаю вокруг него «клетку», определяя набор непроходимых координат Sc (т. Е. Указывает в 3-м пространстве, что ни одна часть рассеивающего шара не может перекрытия). Эти точки находятся в объеме, V (клетка), некоторой большей сферы, где V (клетка) >> V (шар).

При условии набора непроходимых координат Sc, есть ли вычислительно эффективный и / или хороший способ определить, сможет ли шар когда-либо покинуть клетку?

Пожалуйста, смотрите мой предыдущий пост на MathOverflow - https://mathoverflow.net/questions/21911/when-can-a-freely-moving-sphere-escape-from-a-cage-defined-by-a-set-of-impassib

Answer 1

Скажем, у шара есть радиус R . Как отметили ваши друзья из MathOverflow, проблема эквивалентна замене непроходимых точек шариками радиуса R , а шарика - точкой P . Поэтому вопрос в том, находится ли P в камере, закрытой шариками.

Чтобы ответить на этот вопрос, вам нужно вычислить объединение шаров, а затем взять поверхность S этого объединения. Если P находится внутри какого-либо из компонентов S , он будет пойман в ловушку, в противном случае он может сбежать.

Хорошо зарекомендовавшие себя алгоритмы для вычисления объединения шаров, датируемые по крайней мере этой статьей EdelsBrunner . В понимании и реализации этого алгоритма есть немного кривой обучения, но, к счастью, он реализован в библиотеке CGAL .

Как только CGAL рассчитает скин, вы можете посмотреть на подключенные компоненты скина (все из которых должны быть закрытыми сетками) и проверить, находится ли P внутри какой-либо из них (если вам нужна помощь с что, кричи).

Поскольку тесселяционная оболочка является приближением к фактическим сферическим поверхностям, вы можете спросить, есть ли проблемы с точностью. Я ожидал бы, что грани сетки будут на самом деле внутри оригинальных шаров, и, предполагая, что P изначально был вне всех шаров, я думаю, что проверка, находится ли P внутри какого-либо из компонентов скина даст вам точные результаты.