0

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()
Mike Taylor
  • 13
  • 3

2 Answers2

0

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.

Community
  • 1
  • 1
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • See http://stackoverflow.com/questions/545870/algorithm-to-compute-a-voronoi-diagram-on-a-sphere. – lhf Aug 21 '14 at 19:07
  • So using your idea, and the links provided, I wrote code to generate (up to) 1000 random points along the surface of the main sphere, and then check the distance between each point and each object, if any objects are within the range (100), it skips that point and tries a new one. Will that work? – Mike Taylor Aug 22 '14 at 01:13
  • After picking a random point and finding an intersection one option would be to find the circle marking the boundary of the intersection and pick as the next random point somewhere just outside that boundary. I don't know if this is a better strategy - so I might move to just outside the boundary with probability one half and pick an entirely random point as before with probability one half. – mcdowella Aug 22 '14 at 04:55
0

  1. create map of main sphere surface

    • for example:
    • const int na=128;
    • const int nb=256;
    • int map[na][nb];
    • so map[a][b] is surface area around a (latitude), b (longitude)

  2. test all of your small spheres if they intersect main sphere

    • if main sphere is at (0,0,0) wtih radius R
    • then sphere at P (x,y,z) with radius r
    • intersect main sphere if
    • if ((|P|<=R+r)&&(|P|>=R-r))
    • in that case compute latitude ,longitude from P (see spherical coordinate system)
    • remap it to a,b from radians to na,nb sizes
    • and mark map[a][b] (plus its surrounding up to radius r) as intersected

  3. after all spheres are tested you have map of non intersecting areas on surface

Spektre
  • 49,595
  • 11
  • 110
  • 380