Определить точки пересечения между N сферами - PullRequest
Новая
       67

Определить точки пересечения между N сферами

0 голосов
/ 24 июня 2011

Просто хотел узнать, каков наилучший подход (с точки зрения скорости и точности) для определения точек пересечения на N сферах (здесь было задано две сферы здесь );хотел знать, что будет лучшим языком для этого.Более подробное объяснение того, что я хочу сделать, это здесь .

Ответы [ 2 ]

2 голосов
/ 24 июня 2011

Насколько я могу судить, вы запрашиваете локусы пересечения каждой пары из N трехмерных сфер.Считая симметрию, существует N * (N-1) / 2 пары.

Итак, возьмем каждую пару.Если расстояние между центрами больше, чем сумма их радиусов, пересечения нет.(Правка: или, как указывает @Ben, если расстояние меньше, чем разница радиусов, пересечения также нет.)

Если оно равно, пересечение представляет собой одну точку, которую легко найти наотрезок между центрами.Если оно меньше, локус - это круг, а не точка.

Чтобы найти центр этого круга и его радиус, вам понадобится срезать плоскость через две сферы.Это сводит проблему к поиску пересечения двух окружностей.Для этого вам нужен закон косинусов .

Разработано: Посмотрите на эту диаграмму Википедии. a и b - радиусы двух сфер, а c - расстояние между центрами.Используйте второе-последнее уравнение и решите для cos (alpha) .Из этого вы можете легко получить грех (альфа) * ​​1022 *.Тогда b sin (alpha) - радиус круга, а b cos (alpha) - расстояние до его центра.(Примечание: это не вызывает никаких тригонометрических функций, только sqrt .)

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

Кроме того, я не совсем уверен, что вы хотите.

1 голос
/ 24 июня 2011

Если я правильно понял, вы хотите, чтобы все пересечения, по крайней мере, двух сфер из группы из N сфер, верно?

Если это так, то это на самом деле непростая проблема для высокопроизводительных вычислений, по крайней меренет, если вам нужно точное решение.Эта проблема также решается при расчете «приведенной поверхности» молекул:

http://www.ncbi.nlm.nih.gov/pubmed/8906967

Существует несколько публикаций о том, как эффективно рассчитать эти точки и окружности, но это не легкозадача.Я считаю, что была публикация для расчета этих значений с помощью CUDA, но я не помню деталей.Google (Scholar) должен быть в состоянии помочь вам в этом направлении.

Однако, в зависимости от того, чего вы хотите достичь, могут быть более простые решения.Итак, может быть, вы могли бы детализировать свой вопрос?

...