трехмерное пространство, найти радиус |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
трехмерное пространство, найти радиус |
bairt |
23.04.2006 12:07
Сообщение
#1
|
Группа: Пользователи Сообщений: 5 Пол: Мужской Репутация: 0 |
В трехмерном пространстве задано N шаров. Найти шар минимального радиуса, охватывающий все заданные
|
Altair |
23.04.2006 12:25
Сообщение
#2
|
Ищущий истину Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: 45 |
Есть задача решенная - найти окружность, в которую вместяться все точки на плоскости.
Расширяем задачу на 3d , получаем найти шар.... И потом добавляем к точкам уловие того, что они имеют размер. Таким образом задача решается. -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
volvo |
23.04.2006 12:26
Сообщение
#3
|
Гость |
<...>
|
Lapp |
23.04.2006 12:45
Сообщение
#4
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
volvo, давай рассмотрим частный стучай.
Две сферы, одна с центром в точке (-1,-1,-1), а другая в (1,1,1). Радиусы обеих сфер нулевые. Твой алгоритм даст диаметр, равный 2. На самом же деле он равен Sqrt(3). Сообщение отредактировано: lapp - 23.04.2006 12:46 -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
volvo |
23.04.2006 12:55
Сообщение
#5
|
Гость |
Ну, во-первых, не Sqrt(3), а 2*Sqrt(3)
Если уже взялся что-то опровергать, то делай это ПРАВИЛЬНО. |
Lapp |
23.04.2006 12:59
Сообщение
#6
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Ну, во-первых, не Sqrt(3), а 2*Sqrt(3) Если уже взялся что-то опровергать, то делай это ПРАВИЛЬНО. Извиняюсь. Ошибся. 2*Sqrt(3). И вовсе незачем кричать. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
klem4 |
23.04.2006 18:25
Сообщение
#7
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
А есть данные для теста ? А то вот накатал кое что а проверить не могу ;)
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
klem4 |
23.04.2006 19:36
Сообщение
#8
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
В общем вот что пока есть.На соклько я вижу отличается от того что предложил вольво, но возможно тоже имеет место быть ... и всетаки было-бы не плохо увидеть тестовый пример
{$N+} гыя вообще не то что надо решил ))) Volvo, ага тока щас понял ) Еще ведь долго думал как это может быть минимальная среди имеющихся, которая охватыет все остальные :D -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
volvo |
23.04.2006 19:41
Сообщение
#9
|
Гость |
klem4, ты, если я не ошибаюсь, решаешь несколько другую задачу? Ты пытаешься найти сферу из тех, что заданы?
|
klem4 |
23.04.2006 20:02
Сообщение
#10
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Вот такой вариант ... но опятьже нужен тестовые данные ... Вариант годится для случая елси центр хотябы одной сферы не совпадает с центрами остальных, в противном случае берем просто наибольший радиус + 1 ...
{$N+} К сожалению решение не верное =( -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Бравый генерал |
23.04.2006 23:20
Сообщение
#11
|
Новичок Группа: Пользователи Сообщений: 39 Пол: Мужской Реальное имя: Василий Репутация: -2 |
klem4, как видно из твоего кода, ты находил две сферы, которые расположены дальше всего друг от друга. Да, такой вариант неверен. Я сегодня долго думал над этой интересной задачкой и для наглядности сначала делал с окружностями, типа в 2D Так вот в таком варианте как у тебя бывают случаи (окружности задаются случайно), что какая-то окружность может даже ЦЕЛИКОМ выйти за "охватывающую" окружность. Ну, например, чтобы найти окружность, охватывающую множество точек, нужно найти две максимально удаленные точки M и N, найти еще одну точку, максимально удаленную от отрезка MN, и построить по этим трем точкам окружность. Наша же задача сводится к задаче "найти окружность, охватывающую множество окружностей" (2D перевести в 3D не представится сложным). Так вот вопрос: как найти точки A, B и C на прилагаемом мной рисунке?
Эскизы прикрепленных изображений |
volvo |
23.04.2006 23:25
Сообщение
#12
|
Гость |
<...>
|
Lapp |
24.04.2006 14:41
Сообщение
#13
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Наша же задача сводится к задаче "найти окружность, охватывающую множество окружностей" (2D перевести в 3D не представится сложным). Так вот вопрос: как найти точки A, B и C на прилагаемом мной рисунке? Генерал, мне кажется, что ты ошибаешься с утверждением "перевести в 3D не представится сложным". Нахождение окружности, касающейся трех заданных, называется "задачей Апполония". Решение ее не очень простое, но существует. Но я не уверен, что оно есть для 3D. В 3D три заданных окружности превращаются в четыре заданных сферы.. Но дело даже не в этом. Боюсь, что даже найдя "сферу Апполония" (экстраполяция моя), задачу мы не решим.. P.S. А куда исчезли мои предыдущие посты из этой темы?.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
GoodWind |
24.04.2006 14:58
Сообщение
#14
|
Автооответчик Группа: Модераторы Сообщений: 1 188 Пол: Мужской Реальное имя: Александр Репутация: 16 |
Цитата P.S. А куда исчезли мои предыдущие посты из этой темы?.. почему-то скрыты... Я тоже не понял почему. Если я что-то не так понял, модераторы поправлят снова. Пока посты все опубликовал. Altair Сообщение отредактировано: Altair - 24.04.2006 21:06 -------------------- Неадекватная чушь может быть адекватным ответом на неадекватный вопрос. Понятно или разжевать?
|
klem4 |
25.04.2006 15:41
Сообщение
#15
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Я скрыл решение просто по тому что оно не верное, точнее не то я решал что нужно (в общем смысла в них не было), может и не стоило скрывать ...
Вот поправил ф-ю, теперь больше похоже на правду ... ждем тестовые данные ... function GetRadius(s : TSArr) : word; -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
bairt |
25.04.2006 18:16
Сообщение
#16
|
Группа: Пользователи Сообщений: 5 Пол: Мужской Репутация: 0 |
а ты можешь выложить результат?
|
klem4 |
25.04.2006 19:36
Сообщение
#17
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Цитата а ты можешь выложить результат? Извини, не понял тебя ... -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
bairt |
25.04.2006 21:37
Сообщение
#18
|
Группа: Пользователи Сообщений: 5 Пол: Мужской Репутация: 0 |
я про данные она правильно работает? и ты можешь прислать решение я сравню его со своим...
|
klem4 |
26.04.2006 7:02
Сообщение
#19
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Я же писал, у меня нету нормальных тестовых данных, сочинать их у меня нет ни малейшего желания, если у тебя они есть выложи их, кстате что тебе мешает самому проверить правильность моей программы ? Я не понимаю.
Сообщение отредактировано: klem4 - 26.04.2006 7:03 -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Lapp |
26.04.2006 7:16
Сообщение
#20
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Я скрыл решение просто по тому что оно не верное, точнее не то я решал что нужно (в общем смысла в них не было), может и не стоило скрывать ... Вот поправил ф-ю, теперь больше похоже на правду ... ждем тестовые данные ... klem4, ты не обратил внимания на пост Бравого генерала, а он дело говорил. Вот простой пример, опровергающий твое решение. Код Сфера 1: x=-10 y=0 z=0 r=1 Сфера 2: x=10 y=0 z=0 r=1 Сфера 3: x=0 y=12 z=0 r=1 Твоя прога найдет 1 и 2 сферы, как наиболее удаленные, и проведет сферу радиусом 11 из начала координат. Сфера 3 в нее не попадет. чтобы найти окружность, охватывающую множество точек, нужно найти две максимально удаленные точки M и N, найти еще одну точку, максимально удаленную от отрезка MN, и построить по этим трем точкам окружность. Бравый генерал, я сначала пропустил это, а сейчас перечитал и увидел: твое утверждение неверно. Вот опровергающий пример. Код Точка 1 x=-100 y=0 Точка 2 x=100 y=0 Точка 3 x=0 y=150 Точка 4 x=95 y=-6 Точки 1 и 2 максимально удалены. Т 3 отстоит на максимальное растояние от отрезка 1-2. Окружность, проведенная через 1-2-3 оставит Т 4 снаружи.. (Извиняюсь за некрасивые числа - подбирал в уме) Забегая вперед, скажу, что я, кажется, решил эту задачу.. Как только будет время - напишу сюда решение. Но только в общем виде, без программного кода.. PS мужики (и дамы тоже!), давайте не прятать ничего и не скрывать. Дискуссия есть дискуссия. Возможны ошибки, возможны неверные рассуждения, неверные понимания - что ж с того? Но среди всего этого рождается Истина! -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 20.04.2024 14:10 |