В трехмерном декартовом пространстве у меня есть сфера в XYZ радиуса 240 (основная сфера), внутри этой сферы много других сфер радиуса 100 (другие объекты). Мне нужно уметь находить точки вдоль границы пограничной сферы, которые не пересекаются ЛЮБЫМИ другими объектами внутри нее.
Для простоты можно сказать, что основная сфера находится в 0 0 0 с радиусом 240, и внутри находится ~ 33 объекта, каждый из которых имеет радиус 100 в разных координатах.
В основном пишу на Lua, но C / C ++ тоже подойдет.
Мы ценим любую помощь, даже просто указывающую мне правильное направление математического решения.
Редактировать: используя ссылки и информацию, предоставленную David Eisenstat ниже, это код, который я использую.
Это / кажется / работает, но не было возможности полностью протестировать его.
function randomSpherePoint(x, y, z, r)
local acos, sin, cos = math.acos, math.sin, math.cos
local u, v = math.random(), math.random()
local theta = 2 * PI * u
local phi = acos(2 * v - 1)
local px = x + (r * sin(phi) * cos(theta))
local py = y + (r * sin(phi) * sin(theta))
local pz = z + (r * cos(phi))
return px, py, pz
endfunction fun_bordercheck()
local results = { }
local bx, by, bz, radius = -9197.944, 0, 0, 240 -- Border location and radius
for i = 1, 1000 do -- 1000 random points
local px, py, pz = randomSpherePoint(bx, by, bz, radius)
local n = 0
while (n < #space_objs) do
n = n + 1
if (xyz2range(space_objs[n].x, space_objs[n].y, space_objs[n].z, px, py, pz) <=100) then
break -- It hits, no point in checking any other objects. Skip to next random point
end
if (n == #space_objs) then -- We reached the end of the list. If we got this far, this is a possible location. Store it
results[#results+1] = { x = px, y = py, z = pz }
end
end -- while()
end -- for()
if (#results < 1) then
print("No points found.")
return
end
print(string.format("BorderCheck(): Found %d results.", #results))
for i = 1, #results do
Note(string.format("Point %d: %.3f %.3f %.3f", i, results[i].x, results[i].y, results[i].z))
end
end -- function()
Вероятно, самый простой подход заключается в генерировать случайные точки на границе главной сферы а также проверить их на пересечение с исключенными шарами. Структуры близости (например, kd-деревья) могут помочь в асимптотическом тестировании пересечений, но вряд ли оно того стоит в перспективе для 33 объектов. Вычисление Диаграмма Вороного также может быть решением, но диаграмма Вороного с кругово-ограниченными областями на сфере была бы необычным параметром и, вероятно, потребовала бы значительного количества нового, сложного кода.
создать карту поверхности главной сферы
const int na=128;
const int nb=256;
int map[na][nb];
проверить все ваши маленькие сферы, если они пересекаются с основной сферой
(0,0,0)
с радиусом R
P (x,y,z)
с радиусом r
if ((|P|<=R+r)&&(|P|>=R-r))
после того, как все сферы проверены, у вас есть карта непересекающихся областей на поверхности