1 Тема от kobra

  • kobra
  • Участник
  • Неактивен
  • Зарегистрирован: 2012-07-30
  • Сообщений: 4

Тема: Вычислительная геометрия: генерация сфер

Доброго времени суток.
Сейчас работаю над одной задачей.
В параллелепипеде нужно рэндомно сгенерировать сферы различного радиуса, чтоб они не пересекались и не находились одна в другой.
Как ни пробовал никак не удается оптимизировать лобовой алгоритм, тойсть последовательно генерируем каждую сферу и проверяем не пересекается ли она с другими, если пересекается то пропустить ее, иначе добавить к уже существующим. Работа продолжается пока не будет сгенерировано некий объём (например 60% от объёма параллелепипеда)
Можна ли придумать что нибудь лучше?

2 Ответ от aza_inf

  • aza_inf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-30
  • Сообщений: 78

Re: Вычислительная геометрия: генерация сфер

Можно сгенерировать рандомную точку (x0, y0, z0) внутри параллелепипеда. И взять минимальное расстояние от этой точки до шести граней параллелепипеда и отметить это как максимальный радиус. И теперь можно просто сгенерировать радиус меньший или равный найденного. А если есть и другие сферы, то их тоже надо учесть (как грани).

3 Ответ от kobra

  • kobra
  • Участник
  • Неактивен
  • Зарегистрирован: 2012-07-30
  • Сообщений: 4

Re: Вычислительная геометрия: генерация сфер

радиус - не проблема. У меня грубо говоря сфера не должна полностю лежать внутри параллелепипеда, только ее центр. Проблема в том что для того чтоб проверить не пересекаеться ли она с другими сферами, мне нужно O(N) операций, а значит в общем алгоритм будет работать O(N^2), и если у меня стоит задания сгенерировать 10^5 - 10^6 сфер то программа будет работать очень долго

4 Ответ от aza_inf

  • aza_inf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-30
  • Сообщений: 78

Re: Вычислительная геометрия: генерация сфер

А если сортировать и бинпоиском искать как-то... для рандомных радиусов меньше какого-то значения. Повторить несколько раз, пока  не получиться поставить сферу с центром в (x0, y0, z0). Или сделать просто 10 итераций. Вместо сортировки можно set<> использовать.

5 Ответ от kobra

  • kobra
  • Участник
  • Неактивен
  • Зарегистрирован: 2012-07-30
  • Сообщений: 4

Re: Вычислительная геометрия: генерация сфер

я пробовал так:
1. построил 3 multiset для каждой оси
2. Когда добавлял в множество новую сферу то в multiset бросал крайние точки сфери по каждой оси.
3. Когда искал пересечения новой сфери то искал в каждом из трех множеств, а потом искал пересечения трех множеств. В результате получал множество которое состоит из вохможних пересечений. А дальше пробегался по нему.

Но в даном случае мне не удалось учесть что делать если одна сфера лежить в другой.

6 Ответ от MBo

  • MBo
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-10-05
  • Сообщений: 52

Re: Вычислительная геометрия: генерация сфер

Посмотрите на kd-tree

7 Ответ от kobra

  • kobra
  • Участник
  • Неактивен
  • Зарегистрирован: 2012-07-30
  • Сообщений: 4

Re: Вычислительная геометрия: генерация сфер

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