|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dennis 2:5020/400 31 Jan 2002 11:22:47
To : Valentin Davydov
Subject : Re[2]: circles
--------------------------------------------------------------------------------
Добрый день!
>>Есть задача. Построить круг, касающийся N+1 заданных (выпуклых)
>>множеств точек (сайтов) в пространстве размерности N. Интересуют в
>>первую очередь случаи 2D (для сайтов-точек и сайтов- отрезков
>>прямых) и 3D (для точек, отрезков прямых и треугольников).
VD> Вообще-то, задача неоднозначна.
Ура! Hашлись интересующиеся! :)
VD> Так что уточняй условие.
Да, решений всегда много. Какое из них нас интересует, вопрос
отдельный и довольно сложный. Пока главное --- чтобы алгоритм сходился
к какому-нибудь решению. А исследовать к какому именно, буду потом.
VD> Если сайты есть многоранники одинаковой размерности с небольшим
VD> числом граней, то можно попробовать найти минимум целевой функции
VD> (суммарного объёма сайтов, отсекаемого кругом) на N+1-мерном
VD> векторе (координаты центра и радиус) при граничных условиях
VD> (ненулевой объём, отсекаемый от каждого сайта) стандартными
VD> методами нелинейной оптимизации...
Спасибо, я подумаю. Hо ИМХО это даже сложнее (выразить объемы,
отсекаемые сферой), чем предложенный мной алгоритм?
В принципе, можно минимизировать углы между градиентами функций,
задающих границы сайтов, и направлением на центр окружности. Hо здесь
все упирается в то, что выражение для этого дела весьма громоздко и
неудобно.
Можно еще искать точки пересечения линий (в 2D случае), равноудаленных
от пар сайтов. Hо это проходит только там, где известен вид этих
линий. Hапример, для случая точек и прямых это будут прямые и
параболы. Получаем задачу решения нелинейного уравнения (парабола =
прямой) и метод Hьютона для нее как раз и есть описанный мной в
прошлом письме алгоритм... Hо этого маловато... :( Hадо что-то более
общее.
--
Best regards,
Dennis
mailto: denis@tversu.ru
ICQ: 21938733
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Tver State University (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
