Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

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

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

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

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

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

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

Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества - C++
Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества, то есть выпуклый многоугольник с вершинами в некоторых...

Дано множество точек на плоскости, заданных полярными координатами. Получить декартовы координаты этих точек - C++
Получилось сделать для координаты одной точки, а как сделать для множества точек, через цикл или массив? #include <stdio.h> #include...

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

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

Множество точек в пространстве - C++
Множество точек в пространстве задано своими целочисленными координатами.Опред.совподает ли хотя бы одна из точек с началом координат. ...

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

Добавлено через 1 минуту
в конце смотрим на минимальный радиус - если там DBL_MAX - нет решения. иначе мы нашли минимум. при желании при обновлении минимума можно запоминать точку от которой мы строим.
0
Igor3D
929 / 527 / 59
Регистрация: 01.10.2012
Сообщений: 2,602
14.01.2013, 17:36 #3
Самое простое построить kd-tree и найти 3 ближайших для каждой точки (подсекая радиус)
0
vxg
Модератор
3181 / 1984 / 226
Регистрация: 13.01.2012
Сообщений: 7,670
14.01.2013, 17:45 #4
Цитата Сообщение от Igor3D Посмотреть сообщение
Самое простое
напоминает фразу моей жены перед днем рождения "не будем заморачиваться со столом... пожарим слона". а на пальцах?
0
Igor3D
929 / 527 / 59
Регистрация: 01.10.2012
Сообщений: 2,602
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
Модератор
3181 / 1984 / 226
Регистрация: 13.01.2012
Сообщений: 7,670
14.01.2013, 18:17 #6
Цитата Сообщение от Igor3D Посмотреть сообщение
Это дорогостоящая операция
не спорю. однако представить ваше решение на основе "известной вещи" упорядоченной "определенным образом" мне не позволил мой уровень образования. не хочу кидаться какашками, но автору этот метод вообще мозг разорвет.
0
Igor3D
929 / 527 / 59
Регистрация: 01.10.2012
Сообщений: 2,602
14.01.2013, 18:33 #7
Цитата Сообщение от vxg Посмотреть сообщение
не спорю. однако представить ваше решение на основе "известной вещи" упорядоченной "определенным образом" мне не позволил мой уровень образования. не хочу кидаться какашками, но автору этот метод вообще мозг разорвет.
Никто не мешает гуглу открыть и набрать kd-tree. Собственно образование к этому и сводится. Я вообще учил транзисторы (давно)
0
vxg
Модератор
3181 / 1984 / 226
Регистрация: 13.01.2012
Сообщений: 7,670
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
Привет! Вот еще темы с ответами:

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

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

задано множество n точек на плоскости своими координатами. - C++
задано множество n точек на плоскости своими координатами. найти и вывести на экран все точки, симметричные относительно координатных осей...

На плоскости задано множество N (1<N≤20) материальных точек - C++
Если честно я как то не могу полностью понять суть задачи, помогите желательно кодом мне срочно надо Заранее спасибо) На плоскости...


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

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

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