Форум программистов, компьютерный форум CyberForum.ru

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

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

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

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

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

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

C++ Множество точек.Найти множество треугльники
найти две наиболее удаленных друг от друга точки (множество точек задано на плоскости) C++
C++ задано множество n точек на плоскости своими координатами.
C++ Множество точек в пространстве
C++ Дана точка A и множество B из N точек. Найти номер точки из множества B, наиболее удаленной от точки A
C++ Множество попарно различных плоскостей в трехмерном пространстве задано перечислением троек точек, через которые проходит каждая из плоскостей. Вы* бр
C++ Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vxg
Модератор
 Аватар для vxg
2857 / 1790 / 181
Регистрация: 13.01.2012
Сообщений: 6,745
14.01.2013, 17:24     Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества #2
перебираем все точки. для каждой из них:
- составляем список длиной n содержащий точки расположенные в порядке возрастания расстояния от них до нашей точки
- если среди не вошедших в список точек есть такие расстояние от которых до нашей точки равно расстоянию от нашей точки до последней точки списка - наша точка не может быть искомой так как нет сферы с началом в этой точке и содержащей РОВНО n точек
- иначе - расстояние от нашей точки до последней точки списка - искомый радиус
- сравниваем его с минимальным (пусть в начале минимальный радиус равен DBL_MAX) и если он меньше обновляем минимальный радиус

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

А попытки велосипедить здесь не очень к месту
Цитата Сообщение от vxg Посмотреть сообщение
перебираем все точки. для каждой из них:
- составляем список длиной n содержащий точки расположенные в порядке возрастания расстояния от них до нашей точки
Это дорогостоящая операция и если делать это для каждой точки все умрет по скорости уже на 2-5K точек
vxg
Модератор
 Аватар для vxg
2857 / 1790 / 181
Регистрация: 13.01.2012
Сообщений: 6,745
14.01.2013, 18:17     Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества #6
Цитата Сообщение от Igor3D Посмотреть сообщение
Это дорогостоящая операция
не спорю. однако представить ваше решение на основе "известной вещи" упорядоченной "определенным образом" мне не позволил мой уровень образования. не хочу кидаться какашками, но автору этот метод вообще мозг разорвет.
Igor3D
851 / 437 / 38
Регистрация: 01.10.2012
Сообщений: 2,208
14.01.2013, 18:33     Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества #7
Цитата Сообщение от vxg Посмотреть сообщение
не спорю. однако представить ваше решение на основе "известной вещи" упорядоченной "определенным образом" мне не позволил мой уровень образования. не хочу кидаться какашками, но автору этот метод вообще мозг разорвет.
Никто не мешает гуглу открыть и набрать kd-tree. Собственно образование к этому и сводится. Я вообще учил транзисторы (давно)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.01.2013, 19:00     Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества
Еще ссылки по теме:

C++ Заданы два множества точек на плоскости. Построить пересечение и разность этих множеств. Дописать программу
C++ На плоскости задано множество N (1<N≤20) материальных точек
Даны 3 точки в пространстве. Найдите периметр пространственного треугольника, составленного из этих точек C++
Выбрать из точек множества три таких, чтобы в получившийся треугольник влезо наибольшее количество точек C++

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

Или воспользуйтесь поиском по форуму:
vxg
Модератор
 Аватар для vxg
2857 / 1790 / 181
Регистрация: 13.01.2012
Сообщений: 6,745
14.01.2013, 19:00     Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества #8
набрал и че-то не пошло. то ли вики статью писал чудик то ли я дебил. будем надеяться что те кому оно нужно внимательно прослушали лекции.
Yandex
Объявления
14.01.2013, 19:00     Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества
Ответ Создать тему
Опции темы

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