В трехмерном пространстве даны две окружности. Для каждой из окружностей даны: тройка координат центра; единичный вектор нормали к плоскости, в которой лежит окружность; и радиус. Если кому-то нравится, он может сразу умножить вектор нормали на радиус и считатть, что окружность задается двумя векторами. Требуется, для общего случая, найти координаты пары ближайших точек, лежащих на разных окружностях.
Если это упростит решение, случаи, обладающие любым видом симметрии, когда таких пар точек больше одной, можно выбросить из рассмотрения.
Для случаев, имеющих более одного локального минимума, достатчно найти только один, дающий наименьшее расстояние.
Задача имеет прикладное значение (в области collision detection), поэтому вполне приемлемо, если решение будет получено в виде одного или нескольких трансцендентных уравнений одной переменной. (Которые потом можно будет решить численными методами и забить в таблицу).
Можно перейти от декартовой системы координат к любой удобной (сферической, цилиндрической и даже собственно придуманной специально для этой задачи).
Над этой задачей я бился уже почти лет двадцать назад, но так она мне и не далась. Удалось решить похожую задачу для окружности и прямой. Вот я и подумал: а чем черт не шутит, а вдруг, кто-нибудь решит.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
R>В трехмерном пространстве даны две окружности. Для каждой из окружностей даны: тройка координат центра; единичный вектор нормали к плоскости, в которой лежит окружность; и радиус. Если кому-то нравится, он может сразу умножить вектор нормали на радиус и считатть, что окружность задается двумя векторами. Требуется, для общего случая, найти координаты пары ближайших точек, лежащих на разных окружностях.
R>Если это упростит решение, случаи, обладающие любым видом симметрии, когда таких пар точек больше одной, можно выбросить из рассмотрения.
R>Задача имеет прикладное значение (в области collision detection), поэтому вполне приемлемо, если решение будет получено в виде одного или нескольких трансцендентных уравнений одной переменной. (Которые потом можно будет решить численными методами и забить в таблицу).
R>Можно перейти от декартовой системы координат к любой удобной (сферической, цилиндрической и даже собственно придуманной специально для этой задачи).
R>Над этой задачей я бился уже почти лет двадцать назад, но так она мне и не далась. Удалось решить похожую задачу для окружности и прямой. Вот я и подумал: а чем черт не шутит, а вдруг, кто-нибудь решит.
Пояснили бы на простом примере какие пары точек вам нужны. Достаточно только одну такую минимальную пару найти или все возможные?
P.S. На случай, если аналитического решение не дается есть такой чит: бросаем на окружности электрические заряды, которые притягиваются/отталкиваются друг к другу и итеративно двигаем их, моделируя их скольжение по окружностям под действиям сил притяжения-отталкивания.
Здравствуйте, apachik, Вы писали:
A>Пояснили бы на простом примере какие пары точек вам нужны. Достаточно только одну такую минимальную пару найти или все возможные?
Так пояснил же
Если это упростит решение, случаи, обладающие любым видом симметрии, когда таких пар точек больше одной, можно выбросить из рассмотрения.
A>P.S. На случай, если аналитического решение не дается есть такой чит: бросаем на окружности электрические заряды, которые притягиваются/отталкиваются друг к другу и итеративно двигаем их, моделируя их скольжение по окружностям под действиям сил притяжения-отталкивания.
До этого я и сам додумался
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
R>Требуется, для общего случая, найти координаты пары ближайших точек, лежащих на разных окружностях. R>Задача имеет прикладное значение (в области collision detection), поэтому вполне приемлемо, если решение будет получено в виде одного или нескольких трансцендентных уравнений одной переменной.
Если бы тебе нужна была не теория, а практический результат, то я бы посоветовал взять библиотеку OpenCASCADE, создать две окружности и дать задачу найти ближайшие точки. Проще всего написать код на C++, тем более к библиотеке прилагаются примеры на подобные темы. Если же нужна теория, то после того как сделаешь это, зайди внутрь кода библиотеки, который вызывал при решении практической задачи и посмотри как там всё устроено. А устроено там всё совсем не просто, если не сказать наоборот. Жизнь потратишь, чтобы это всё изучить.
Здравствуйте, velkin, Вы писали:
V>Если бы тебе нужна была не теория, а практический результат, то я бы посоветовал взять библиотеку OpenCASCADE, создать две окружности и дать задачу найти ближайшие точки. Проще всего написать код на C++, тем более к библиотеке прилагаются примеры на подобные темы. Если же нужна теория, то после того как сделаешь это, зайди внутрь кода библиотеки, который вызывал при решении практической задачи и посмотри как там всё устроено. А устроено там всё совсем не просто, если не сказать наоборот. Жизнь потратишь, чтобы это всё изучить.
Ну, практический результат мне нужен был двадцать лет назад. Сейчас меня это больше интересует именно как этюд. Но за совет спасибо, загляну, как только появится больше свободного времени.
--
Не можешь достичь желаемого — пожелай достигнутого.
прикольная задачка. Пока получилось выписать расстояние от точки до окружности. И в принципе понятно теперь как решить итеративно. Типа бинарным поиском нужно точки по участкам второй окружности, где функция расстояния будет вести себя выпукло.
Здравствуйте, rg45, Вы писали:
R>Можно перейти от декартовой системы координат к любой удобной (сферической, цилиндрической и даже собственно придуманной специально для этой задачи).
R>Над этой задачей я бился уже почти лет двадцать назад, но так она мне и не далась. Удалось решить похожую задачу для окружности и прямой. Вот я и подумал: а чем черт не шутит, а вдруг, кто-нибудь решит.
Там получается сложное уравнение 4+ степени, для практических нужд аналитически не решить, только приближениями.
Здравствуйте, apachik, Вы писали:
A>прикольная задачка. Пока получилось выписать расстояние от точки до окружности. И в принципе понятно теперь как решить итеративно. Типа бинарным поиском нужно точки по участкам второй окружности, где функция расстояния будет вести себя выпукло.
Вот примерно так я и постутил тогда. Но тут есть засада — локальных минимумов может быть больше одного (и даже больше двух) и возникает проблема правильного выбора начального приближения.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, Nikе, Вы писали:
N>Там получается сложное уравнение 4+ степени, для практических нужд аналитически не решить, только приближениями.
Так и есть. Но для родственной задачи окружность-прямая тоже получалось уравнение, не имеющее аналитического решения (не помню уже степень — третья или четвертаю). И вот, с переходом в цилиндрические координаты, задачу удалось свести к трансцендентному уравнения с синусом в одной из частей. Так может, и здесь удастся получить что-то подобное?
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
R>Здравствуйте, apachik, Вы писали:
A>>прикольная задачка. Пока получилось выписать расстояние от точки до окружности. И в принципе понятно теперь как решить итеративно. Типа бинарным поиском нужно точки по участкам второй окружности, где функция расстояния будет вести себя выпукло.
R>Вот примерно так я и постутил тогда. Но тут есть засада — локальных минимумов может быть больше одного (и даже больше двух) и возникает проблема правильного выбора начального приближения.
видимо, потому что минимумов может быть четыре, то и уравнение четвертой степени получится, как ни крути. Хотя так как там есть симметричные, то есть шансы на уравнение всего лишь второй степени...
Здравствуйте, rg45, Вы писали:
R>Вот примерно так я и постутил тогда. Но тут есть засада — локальных минимумов может быть больше одного (и даже больше двух) и возникает проблема правильного выбора начального приближения.
Нейронка простая
Здравствуйте, apachik, Вы писали:
A>видимо, потому что минимумов может быть четыре, то и уравнение четвертой степени получится, как ни крути. Хотя так как там есть симметричные, то есть шансы на уравнение всего лишь второй степени...
Для оценки степени многочлена нужно учитывать количество всех экстремумов, а не только минимумов А есть еще такое западло, как точки перегиба, которые порой легко принять за экстремум (например, y = x3 при x = 0). А еще седловые точки. В общем, веселуха.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, apachik, Вы писали:
A>я понял. отличный гроб для acm-контеста получился. Проблема в том, что жюри надо таки написать работающее решение и тесты )))
Ну, не будем торопиться.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
R>В трехмерном пространстве даны две окружности. Для каждой из окружностей даны: тройка координат центра; единичный вектор нормали к плоскости, в которой лежит окружность; и радиус. Если кому-то нравится, он может сразу умножить вектор нормали на радиус и считатть, что окружность задается двумя векторами. Требуется, для общего случая, найти координаты пары ближайших точек, лежащих на разных окружностях.
Здравствуйте, Nikе, Вы писали:
N>Здравствуйте, rg45, Вы писали:
R>>Вот примерно так я и постутил тогда. Но тут есть засада — локальных минимумов может быть больше одного (и даже больше двух) и возникает проблема правильного выбора начального приближения. N>Нейронка простая
В нейронках проблема локальных минимумов не стоит, т.к. там высокая размерность и локальные минимумы оборачиваются седловыми точками, а тут размерность 3...
Здравствуйте, rg45, Вы писали: R>В трехмерном пространстве даны две окружности. Для каждой из окружностей даны: тройка координат центра; единичный вектор нормали к плоскости, в которой лежит окружность; и радиус. Если кому-то нравится, он может сразу умножить вектор нормали на радиус и считать, что окружность задается двумя векторами. Требуется, для общего случая, найти координаты пары ближайших точек, лежащих на разных окружностях. R>Если это упростит решение, случаи, обладающие любым видом симметрии, когда таких пар точек больше одной, можно выбросить из рассмотрения. R>Для случаев, имеющих более одного локального минимума, достатчно найти только один, дающий наименьшее расстояние. R>Задача имеет прикладное значение (в области collision detection), поэтому вполне приемлемо, если решение будет получено в виде одного или нескольких трансцендентных уравнений одной переменной. (Которые потом можно будет решить численными методами и забить в таблицу). R>Можно перейти от декартовой системы координат к любой удобной (сферической, цилиндрической и даже собственно придуманной специально для этой задачи). R>Над этой задачей я бился уже почти лет двадцать назад, но так она мне и не далась. Удалось решить похожую задачу для окружности и прямой. Вот я и подумал: а чем черт не шутит, а вдруг, кто-нибудь решит.
Спасибо, красивая задачка, хотя и несложная. Размял чуть-чуть мозги.
Нахождения точек экстремума здесь сводится к нахождению точек пересечения окружности и кривой 4 порядка на плоскости.
Что в свою очередь сводится к решению алгебраического уравнения 8-й степени (с помощью рациональной параметризации окружности).
детали
(Вырожденные случаи опускаем -- они тривиальны).
1) Во-первых, пусть у нас есть окружность C и точка A. Как найти экстремальную (т.е. наиболее близкую или наиболее далёкую) точку на окружности относительно A?
Очень просто, надо провести плоскость через A и ось окружности. Она пересечёт окружность в двух экстремальных точках.
Иными словами, если экстремальна точка B, то прямая (AB) лежит в одной плоскости с осью окружности, и тем самым её пересекает
(возможно, в бесконечности).
2) Пусть теперь у нас две окружности. Если A и B -- экстремальные точки, то прямая (AB) должна пересекать обе оси окружностей. Точки пересечения с осями назовём X и Y.
А теперь делаем следующее. Отпустим точку A гулять по плоскости окружности. Тогда точке A будет соответствовать единственная пара (X,Y).
На языке алгебраической геометрии получится бирациональное соответствие между плоскостью и произведением пары прямых.
Есть точно такое же второе соответствие между B (пробегающая плоскость второй окружности) и (X,Y).
Комбинируя эти отображения, получим бирациональное соответствие между плоскостями окружностей.
Путем несложных геометрических рассуждений находим, что это классическое квадратичное преобразование.
Задаётся оно тройками точек в обоих плоскостях.
Тройки это такие.
Пусть центры окружностей O1 и O2, оси окружностей l1 и l2, плоскости окружностей <b>P1</b> и <b>P2</b>.
Тогда у нас возникают ещё четыре вспомогательные точки.
M1 -- точка пересечения l2 и <b>P1</b>.
M2 -- точка пересечения l1 и <b>P2</b>.
L1 -- точка пересечения (O2,M2) и <b>P1</b>.
L2 -- точка пересечения (O1,M1) и <b>P2</b>.
Заметим, что L1 и L2 лежат на пересечении плоскостей <b>P1</b> и <b>P2</b>.
Квадратичное преобразование задаётся тройками (O1,M1,L1) и (O2,M2,L2).
При этом (O1,M1) стягивается в L2, (O1,L1) в O2, (M1,L1) в M2.
И в обратную сторону, (O2,M2) стягивается в L1, (O2,L2) в O1, (M2,L2) в M1.
Теперь надо перебросить вторую окружность с помощью этого преобразования в первую плоскость и пересечь получившуюся кривую с первой окружностью.
Выписывание всех необходимых формул оставляю читателям в качестве упражнения в чистописании.
Здравствуйте, ylem, Вы писали:
Y>Я, видимо, наивняк, поэтому если это возможно в краткой форме и на пальцах, похажите, пожалуйста, где ошибаюсь? Y>То, что вроде бы кажется решением: Y>Строим направления из центров друг на друга. Проецируем их на соотв. плосокости окружностей. В этих направлениях-прокциях от соотв. центров берем точки на окружностях. Y>Почему не оно?
Ну вот, частный случай на рисунке ниже. Требуется найти пару точек A и B, тогда как твой метод даст пару A и X.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
R>Для оценки степени многочлена нужно учитывать количество всех экстремумов, а не только минимумов А есть еще такое западло, как точки перегиба, которые порой легко принять за экстремум (например, y = x3 при x = 0). А еще седловые точки. В общем, веселуха.
А если разбить на монотонные участки или на участки с одним минимумом, а потом просто взять в кач-ве ответа минимум из набора минимумов?
Например, центры окружностей можно соединить прямой, построить плоскости в центрах окружностей нормальные к этой прямой. Плоскости окружностей пересекают построенные нормальные плоскости, деля окружности на две части, имея при этом максимумы удаления от построенных плоскостей в 90 градусов. Т.е. можно разделить каждую такую окружность на 4 части, затем найти минимумы в попарных диапазонах четвертей окружностей, всего будет 16 попарных комбинаций, т.е. 16 найденных минимумов. Это для общего случая.
Для частных случаев:
— если фигуры-окружности пересекаются, то искомые точки лежат на линии пересечения (для установления факта коллизии их уже искать не нужно, насколько я понял, в любом случае там 2+2 точки, 4 возможных пары, из которых взять минимальную).
— если плоскости окружностей параллельны, то минимальное расстояние равно расстоянию м/у их центрами.
upd:
— если плоскость окружности совпадает с построенной дополнительной плоскостью, то делить её на диапазоны не надо.
А есть еще такое западло, как точки перегиба, которые порой легко принять за экстремум (например, y = x3 при x = 0). А еще седловые точки. В общем, веселуха.
