Алгоритм поиска точек вдоль сферы, которые не пересекаются с другими сферами с определенным радиусом

В трехмерном декартовом пространстве у меня есть сфера в 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()

0

Решение

Вероятно, самый простой подход заключается в генерировать случайные точки на границе главной сферы а также проверить их на пересечение с исключенными шарами. Структуры близости (например, kd-деревья) могут помочь в асимптотическом тестировании пересечений, но вряд ли оно того стоит в перспективе для 33 объектов. Вычисление Диаграмма Вороного также может быть решением, но диаграмма Вороного с кругово-ограниченными областями на сфере была бы необычным параметром и, вероятно, потребовала бы значительного количества нового, сложного кода.

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 из радианов в n, nb размеров
    • и пометить карту [a] [b] (плюс ее окружение до радиуса r) как пересеченную
  3. после того, как все сферы проверены, у вас есть карта непересекающихся областей на поверхности

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector