Определение того, окружена ли сфера полностью другими сферами, расположенными вокруг нее
Задача:Имея список сфер, найти все пустые пространства, которые полностью окружены сферами.
Фрагмент:Это задача, над которой я работаю, пытаясь определить полости, расположенные в белке. Мне дан список атомов, из которых состоит белок ((x,y,z )координаты и радиус ). Затем я запускаю свой алгоритм, чтобы найти все пустые пространства, лежащие в пределах границ белка, проверяя, можно ли разместить зонд (заданного радиуса )в определенном месте, не сталкиваясь с другими сферами. Есть два типа пустых пространств, пустоты и полости. Пустые пространства - это пространства, которые могут вести к белку или снаружи от него. Полости — это пустые пространства, полностью закрытые атомами белка. Вот изображение образца «белка», с которым мы работаем.
Его можно посмотреть в трех измерениях здесь .
Рядом с центром белка находится полость, туннель, проходящий через белок, который вы видите, можно считать пустым пространством, поскольку он не полностью окружен атомами.
Пример:Дан список из 26 атомов, эти атомы равномерно распределены от (0,0,0 )до (1,1,1 )в 3 -измерениях. сетка. Каждый атом имеет радиус 0,25 и расположен на 0, 0,5 или 1 на любой оси. В точке (0,5, 0,5, 0,5 )атома нет. Если бы мы нарисовали трехмерную фигуру этих атомов, это была бы кубическая форма с отсутствующим центром. Полость будет обозначена как (0,5,0,5,0,5 )с радиусом 0,25. Можно предположить, что эта полость со всех сторон окружена белками.
Пример изображения:
Обратите внимание, что приведенное выше является только двумерным представлением куба и белка. На самом деле это 3D.
Как можно определить пустоты и полости для гораздо большей группы атомов неправильной формы?
Я думал о реализации рекурсивного алгоритма, который проверяет каждое направление, чтобы увидеть, может ли он достичь максимальной и минимальной границ графа, но я не уверен, что это правильный способ сделать это.
Дополнительно:Существует ли другой алгоритм, который сказал бы, что полость в примере на самом деле является пустым пространством, потому что есть очень маленькие «пути», ведущие к внешней стороне белка? Полость должна быть полностью окружена атомами, чтобы существовать. Любые пустые пространства, которые имеют путь (в любом направлении, не обязательно прямой )наружу от белка, не будут считаться полостями.