In 3D cartesian space, I have a sphere at XYZ of a radius of 240 (main sphere), within that sphere are many other spheres of radius 100 (other objects). I need to be able to find points along the boundary of the border sphere, that are not intersected by ANY of the other objects inside it.
For simplicity, we can say the main sphere is at 0 0 0 with a radius of 240, and there are ~33 objects inside, each with a radius of 100 at different coordinates.
Mostly writing in Lua, but C/C++ is fine as well. Any help is appreciated, even just pointing me in the right direction on how to solve it mathematically.
Edit: Using the links and info provided by David Eisenstat below, this is the code I am using. It /seems/ to work, but have not had a chance to fully test it.
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
end
function 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()
Probably the simplest approach is to generate points at random on the boundary of the main sphere and test them for intersections with the excluded balls. Proximity structures (e.g., kd-trees) would help the intersection tests asymptotically but hardly seem worth it in prospect for 33 objects. Computing a Voronoi diagram also could be a solution, but a Voronoi diagram of circularly bounded regions on a sphere would be an unusual setting and likely require a fair amount of new, intricate code.