0

在 3D 笛卡尔空间中，我在 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
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()
4

2 回答 2

0

可能最简单的方法是在主球的边界上随机生成点，并测试它们是否与排除的球相交。邻近结构（例如，kd-trees）将有助于渐近地进行交叉测试，但在 33 个对象的前景中似乎不值得。计算Voronoi 图也可能是一种解决方案，但球体上圆形有界区域的 Voronoi 图将是一个不寻常的设置，可能需要大量新的、复杂的代码。

于 2014-08-21T18:08:22.050 回答
0

  1. 创建主球面贴图

    • 例如：
    • const int na=128;
    • const int nb=256;
    • int map[na][nb];
    • 所以 map[a][b] 是 a（纬度）、b（经度）周围的表面积

  2. 测试所有小球体是否与主球体相交

    • 如果主球体在(0,0,0)半径R
    • 然后P (x,y,z)以半径为球体r
    • 相交主球如果
    • if ((|P|<=R+r)&&(|P|>=R-r))
    • 在这种情况下，从 P 计算纬度、经度（参见球坐标系）
    • 将其重新映射到 a,b 从弧度到 na,nb 大小
    • 并将 map[a][b] （加上它的周围直到半径 r）标记为相交

  3. 在所有球体都经过测试后，您在表面上有了非相交区域的地图

于 2014-08-21T18:20:11.947 回答