Пересечение растущих сфер - PullRequest
Новая
       21

Пересечение растущих сфер

0 голосов
/ 03 ноября 2011

Я пытаюсь решить эту проблему, когда даны 4 сферы с их центрами и начальными радиусами:

Bi = (Ci, Wi), где Ci = (xi, yi, zi) - центрсферы и Wi - ее начальный радиус.

Радиус шариков непрерывно увеличивается вместе параметром, скажем, a.То есть, когда «а» увеличивается от 0 до бесконечности, радиус сфер в любой момент времени равен Wi + a.Теперь сферы: Bi = (Ci, Wi + a).Задача состоит в том, чтобы найти минимум «а», для которого (отредактированные) тома четырех сфер пересекаются вместе.

Возможно ли эффективно решить эту проблему вместо того, чтобы писать утомительные математические уравнения для всех сфер и решать дляа '?

Ответы [ 2 ]

4 голосов
/ 03 ноября 2011

Сферные пересечения, к счастью, являются самыми простыми из всех типов трехмерных пересечений. Если сумма радиусов двух сфер больше расстояния между их центральными точками, то их объемы пересекаются.

Таким образом, самый простой способ решить эту проблему - найти наибольшее расстояние между любыми парами сфер (найти расстояние между центрами, затем вычесть их начальные радиусы). Учитывая это расстояние, разделите на 2, и вы получите значение a, при котором соприкасаются все сферы. Если оно больше этого значения, все они будут перекрываться.

Теперь, на самом деле, это не совсем ответ на вашу проблему, а именно: «Какое значение мне нужно для того, чтобы все сферы образовали единый связный объем». В конце концов, если я поставлю сферы в ряд, каждая из них должна только коснуться своего ближайшего соседа, чтобы сформировался согласованный объем. Таким образом, вам все еще нужно решить часть проблемы со связным графом, но, надеюсь, этого достаточно, чтобы начать работу.

1 голос
/ 03 ноября 2011

Для четырех сфер L, M, N, O - с начальным радиусом rL, rM, rN, rO и центрами cL, cM, cN, cO и общим дополнительным радиусом "a".

L пересекает M, когда 

Distance(cL, cM) <= rL + rM + 2a

При наличии четырех сфер возможны следующие ограничения. 

  //at least one of
Distance(cL, cM) <= rL + rM + 2a
Distance(cL, cN) <= rL + rN + 2a
Distance(cL, cO) <= rL + rO + 2a
  //and at least one of
Distance(cM, cL) <= rM + rL + 2a
Distance(cM, cN) <= rM + rN + 2a
Distance(cM, cO) <= rM + rO + 2a
  //and at least one of
Distance(cN, cL) <= rN + rL + 2a
Distance(cN, cM) <= rN + rM + 2a
Distance(cN, cO) <= rN + rO + 2a
  //and at least one of
Distance(cO, cL) <= rO + rL + 2a
Distance(cO, cM) <= rO + rM + 2a
Distance(cO, cN) <= rO + rN + 2a

Но это «написание утомительных математических уравнений для всех сфер».

Вот короткая (n ^ 2) реализация в c # с Linq. 

decimal aResult =
(
  from left in spheres
  from right in spheres
  let dist = Distance(left.Center, right.Center)
  let aRaw = (dist - left.startRadius - right.startRadius)/2
  let a = aRaw < 0 ? 0 : aRaw   //spheres might start out touching!
  group a by left into g
  select g.Min()  //the smallest extra radius for each group
).Max();
//the largest extra radius that makes at least one equation true for each group.
// any smaller, and there exists a disconnected sphere with no true equation.

Должна быть возможность сократить совпадения, используя предварительные вычисления, чтобы разбить n ^ 2.

Аналогично 2D-случаю, когда 3 окружности могут пересекаться между двумя другими без общей области, пересекаемой всеми 3 окружностями.

О, это другая проблема. Хм.

Предположим, у вас есть три апельсина, расположенных в виде треугольника, лежащих на поверхности земли. Каждая сфера касается остальных трех, но между всеми четырьмя сферами нет общей точки.

Вы хотите наименьшее «а», чтобы существовала общая точка (x, y, z). 

 //all must be true
(x - cL)^2 + (y - yL)^2 + (z - zL)^2 <= (a + rL)^2
(x - cM)^2 + (y - yM)^2 + (z - zM)^2 <= (a + rM)^2
(x - cN)^2 + (y - yN)^2 + (z - zN)^2 <= (a + rN)^2
(x - cO)^2 + (y - yO)^2 + (z - zO)^2 <= (a + rO)^2
...