1 Ответ от kobra

(6 ответов, оставленных в Problems)

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

Перейти к разделу: Problems

2 Ответ от kobra

(6 ответов, оставленных в Problems)

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

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

Перейти к разделу: Problems

3 Ответ от kobra

(6 ответов, оставленных в Problems)

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

Перейти к разделу: Problems

4 Тема от kobra

(6 ответов, оставленных в Problems)

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

Перейти к разделу: Problems