Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Zod
0 / 0 / 0
Регистрация: 19.11.2012
Сообщений: 5
#1

Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества - C++

14.01.2013, 16:42. Просмотров 1372. Ответов 7
Метки нет (Все метки)

Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества.

Если не программу, то подскажите примерный алгоритм работы.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.01.2013, 16:42
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества (C++):

Множество попарно различных плоскостей в трехмерном пространстве задано перечислением троек точек, через которые проходит каждая из плоскостей. Вы* бр
В геометрии не силен!!:cry: Множество попарно различных плоскостей в...

Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества
Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества,...

Дано множество точек на плоскости, заданных полярными координатами. Получить декартовы координаты этих точек
Получилось сделать для координаты одной точки, а как сделать для множества...

Имеется массив элементов-точек в трехмерном пространстве
Имеется массив элементов-точек в трехмерном пространстве: struct Point3D ...

найти две наиболее удаленных друг от друга точки (множество точек задано на плоскости)
Помогите, пожалуйста, написать программу на С++, используя структуру point для...

Определить, сколько точек пересечения имеют прямая и окружность и найти координаты этих точек
Привет. Тут такое дело. В общем я неплохо знаю сам язык, но вот задачку решить...

7
vxg
Модератор
3231 / 2034 / 319
Регистрация: 13.01.2012
Сообщений: 7,885
14.01.2013, 17:24 #2
перебираем все точки. для каждой из них:
- составляем список длиной n содержащий точки расположенные в порядке возрастания расстояния от них до нашей точки
- если среди не вошедших в список точек есть такие расстояние от которых до нашей точки равно расстоянию от нашей точки до последней точки списка - наша точка не может быть искомой так как нет сферы с началом в этой точке и содержащей РОВНО n точек
- иначе - расстояние от нашей точки до последней точки списка - искомый радиус
- сравниваем его с минимальным (пусть в начале минимальный радиус равен DBL_MAX) и если он меньше обновляем минимальный радиус

Добавлено через 1 минуту
в конце смотрим на минимальный радиус - если там DBL_MAX - нет решения. иначе мы нашли минимум. при желании при обновлении минимума можно запоминать точку от которой мы строим.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
14.01.2013, 17:36 #3
Самое простое построить kd-tree и найти 3 ближайших для каждой точки (подсекая радиус)
0
vxg
Модератор
3231 / 2034 / 319
Регистрация: 13.01.2012
Сообщений: 7,885
14.01.2013, 17:45 #4
Цитата Сообщение от Igor3D Посмотреть сообщение
Самое простое
напоминает фразу моей жены перед днем рождения "не будем заморачиваться со столом... пожарим слона". а на пальцах?
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
14.01.2013, 18:13 #5
Цитата Сообщение от vxg Посмотреть сообщение
напоминает фразу моей жены перед днем рождения "не будем заморачиваться со столом... пожарим слона". а на пальцах?
kd-tree - вещь известная и как раз предназначенная для нахождения n ближайших соседей. Если кратко: массив упорядочивается определенным образом. В элементах записаны индексы осей деления. Поиск начинается с первого. Напр в нем ось X. Тогда все точки [0..n/2] имеют a[i].x <= a[0].x а все точки [n/2..n] больший. Если расстояние по X уже превышает радиус поиска, то одну половинку можно отбросить. Оставшиеся опять делятся и.т.д

А попытки велосипедить здесь не очень к месту
Цитата Сообщение от vxg Посмотреть сообщение
перебираем все точки. для каждой из них:
- составляем список длиной n содержащий точки расположенные в порядке возрастания расстояния от них до нашей точки
Это дорогостоящая операция и если делать это для каждой точки все умрет по скорости уже на 2-5K точек
0
vxg
Модератор
3231 / 2034 / 319
Регистрация: 13.01.2012
Сообщений: 7,885
14.01.2013, 18:17 #6
Цитата Сообщение от Igor3D Посмотреть сообщение
Это дорогостоящая операция
не спорю. однако представить ваше решение на основе "известной вещи" упорядоченной "определенным образом" мне не позволил мой уровень образования. не хочу кидаться какашками, но автору этот метод вообще мозг разорвет.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
14.01.2013, 18:33 #7
Цитата Сообщение от vxg Посмотреть сообщение
не спорю. однако представить ваше решение на основе "известной вещи" упорядоченной "определенным образом" мне не позволил мой уровень образования. не хочу кидаться какашками, но автору этот метод вообще мозг разорвет.
Никто не мешает гуглу открыть и набрать kd-tree. Собственно образование к этому и сводится. Я вообще учил транзисторы (давно)
0
vxg
Модератор
3231 / 2034 / 319
Регистрация: 13.01.2012
Сообщений: 7,885
14.01.2013, 19:00 #8
набрал и че-то не пошло. то ли вики статью писал чудик то ли я дебил. будем надеяться что те кому оно нужно внимательно прослушали лекции.
0
14.01.2013, 19:00
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.01.2013, 19:00
Привет! Вот еще темы с решениями:

Множество точек в пространстве
Множество точек в пространстве задано своими целочисленными...

Из множества точек на плоскости найти точки, образующие параллелограмм с наибольшим количеством точек внутри
&quot;Даны N точек на плоскости. Найти среди них точки являющиеся вершинами фигуры,...

На плоскости задано множество точек. Выбрать три различные точки так, чтобы проходящая через них окружность делила это множество на группы
На плоскости задано множество точек. Выбрать три различные точки так, чтобы...

задано множество n точек на плоскости своими координатами.
задано множество n точек на плоскости своими координатами. найти и вывести на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru