Search code examples
c++algorithmluacartesian-coordinates

Algorithm to find points along a sphere that do not intersect with other spheres with a specific radius


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()

Solution

  • 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.