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

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

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

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

Если не программу, то подскажите примерный алгоритм работы.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.01.2013, 16:42
Ответы с готовыми решениями:

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

Задано множество точек m в трехмерном пространстве.
Задано множество точек m в трехмерном пространстве. Найти такую из них, что шар заданного радиуса с...

В трехмерном пространстве задано множество материальных точек.
1)В трехмерном пространстве задано множество материальных точек.Каждая из точек с максимальной...

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

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

Добавлено через 1 минуту
в конце смотрим на минимальный радиус - если там DBL_MAX - нет решения. иначе мы нашли минимум. при желании при обновлении минимума можно запоминать точку от которой мы строим.
0
1236 / 603 / 74
Регистрация: 01.10.2012
Сообщений: 2,870
14.01.2013, 17:36 3
Самое простое построить kd-tree и найти 3 ближайших для каждой точки (подсекая радиус)
0
Модератор
3332 / 2116 / 343
Регистрация: 13.01.2012
Сообщений: 8,245
14.01.2013, 17:45 4
Цитата Сообщение от Igor3D Посмотреть сообщение
Самое простое
напоминает фразу моей жены перед днем рождения "не будем заморачиваться со столом... пожарим слона". а на пальцах?
0
1236 / 603 / 74
Регистрация: 01.10.2012
Сообщений: 2,870
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
Модератор
3332 / 2116 / 343
Регистрация: 13.01.2012
Сообщений: 8,245
14.01.2013, 18:17 6
Цитата Сообщение от Igor3D Посмотреть сообщение
Это дорогостоящая операция
не спорю. однако представить ваше решение на основе "известной вещи" упорядоченной "определенным образом" мне не позволил мой уровень образования. не хочу кидаться какашками, но автору этот метод вообще мозг разорвет.
0
1236 / 603 / 74
Регистрация: 01.10.2012
Сообщений: 2,870
14.01.2013, 18:33 7
Цитата Сообщение от vxg Посмотреть сообщение
не спорю. однако представить ваше решение на основе "известной вещи" упорядоченной "определенным образом" мне не позволил мой уровень образования. не хочу кидаться какашками, но автору этот метод вообще мозг разорвет.
Никто не мешает гуглу открыть и набрать kd-tree. Собственно образование к этому и сводится. Я вообще учил транзисторы (давно)
0
Модератор
3332 / 2116 / 343
Регистрация: 13.01.2012
Сообщений: 8,245
14.01.2013, 19:00 8
набрал и че-то не пошло. то ли вики статью писал чудик то ли я дебил. будем надеяться что те кому оно нужно внимательно прослушали лекции.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.01.2013, 19:00

Дано множество A из N точек на плоскости. Найти точку (вывести её номер и значение) среди всех точек этого множества
Дано множество A из N точек на плоскости. Найти точку (вывести её номер и значение) среди всех...

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

Множество точек касания шаров в пространстве
Точки А и В фиксированы на плоскости. Два шара, SA и SB касаются плоскости в точках А и В...

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


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

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

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