Вдохновленная Ивсом идея рекурсивного алгоритма плоскости развертки, это более сложная версия для попытки найти точку внутри сферы, которая не покрыта ни одним из заданных прямоугольников.
Сначала мы должнынайти все значения z-координаты, где полное покрытие в соответствующей плоскости может измениться при движении вдоль оси z.Это может произойти при
- максимальной и минимальной z-координате сферы (то есть z_center +/- radius)
- максимальной и минимальной z-координатах всех блоков
- максимальные и минимальные z-координаты всех окружностей / дуг пересечения сферы со всеми гранями ящика
После того, как эти z-значения собраны, отсортированы и ограничены z-диапазономсфера у нас есть разбиение z-диапазона сферы на интервалы.Мы выбираем значение внутри в каждом интервале z (например, в центре), чтобы проверить покрытие в соответствующей плоскости.Каждый двухмерный вырез может быть решен аналогично трехмерной задаче, что сводит проверку покрытия к набору одномерных задач.В одномерном случае у нас есть интервал вместо сферы или круга, и у нас также есть интервалы вместо прямоугольников или прямоугольников.Таким образом, проблема покрытия сферы против блоков сводится к набору тривиальных задач покрытия одного интервала с набором интервалов.
Реализация основной функции может выглядеть следующим образом:
# if the n-dimensional sphere is not fully covered by the boxes
# find a point inside the sphere but outside the boxes
# by a recursive sweep-plane algorithm.
# center: n-dimensional point
# radius: real value
# boxes: list of n-dimensional boxes (each box is a list of n intervals)
def getUncoveredSphereWitness(center, radius, boxes):
sphereLimitsN = [center[-1]-radius, center[-1]+radius]
if len(center) == 1:
# 1D case
witness = getUncoveredIntervalWitness(sphereLimitsN, [box[0] for box in boxes])
return [witness] if witness is not None else None
boxLimitsN = sum([b[-1] for b in boxes], [])
cutLimitsN = getCutLimitsN_boxes(center, radius, boxes)
limitsN = list(set(sphereLimitsN + boxLimitsN + cutLimitsN))
limitsN.sort()
# get centers of relevant intervals
coordNValsToCheck = []
for b in limitsN:
if b > sphereLimitsN[1]: break
if b > sphereLimitsN[0]:
coordNValsToCheck.append((bPrev+b)/2.)
bPrev = b
for z in coordNValsToCheck:
# reduce to a problem of with 1 dimension less
centerN1, radiusN1 = cutSphereN(center, radius, z)
boxesN1 = cutBoxesN(boxes, z)
witness = getUncoveredSphereWitness(centerN1, radiusN1, boxesN1)
if witness is not None:
return witness+[z] # lift witness to full dimension by appending coordinate
return None