Комментарий к задачке nabbla1
Очень длинный комментарий к задачке https://nabbla1.livejournal.com/513667.html
Пояснение.
Комментарий получился настолько длинным, что пришлось размещать в своем журнале. Как отдельный текст, комментарий не имеет смысла. Рекомендую заглянуть в исходное обсуждение https://nabbla1.livejournal.com/513667.html
Переформулируем исходную задачу.
Есть обруч из невесомой проволоки. Центр обозначим O. На обруче закреплено N массивных бусинок, все бусинки имеют одинаковую массу.
У этой конструкции есть центр масс (ЦМ).
Нас интересует следующая задачка.
Случай, когда ЦМ совпал с центром обруча, рассматривать не будем - не повезло, облом, черт с ним.
Во всех остальных случаях мы хотим провести радиус из O в направлении ЦМ. То есть, нас не волнует расстояние между O и ЦМ, нам интересно только направление.
Предлагается следующий алгоритм.
Разрезаем обруч в произвольном месте и распрямляем проволочку. Находим центр масс прямой конструкции (ЦМп), отмечаем его на проволочке. Опять все сворачиваем в исходный вид.
Вопрос - совпадут ли направления от центра обруча на ЦМ и на отметку ЦМп?
Иными словами - может ли алгоритм принести пользу?
N=1
Совпадут
N=2
Почти облом
Случай, когда бусинки строго на разных концах диаметра не рассматриваем.
В другом случае, у бусинок есть кратчайшее расстояние по дуге между ними (кусок проволоки L1) и более длинное расстояние между ними (кусок проволоки L2)
В зависимости от того, резали L2 или L1, алгоритм будет (соответственно) выдавать либо направление на ЦМ, либо направление, строго противоположное ЦМ .
N=3 и более.
В общем случае - совсем облом.
Контрпример.
N=3. Две бусинки "сдвоенные", почти в одной точке. Одна бусинка в диаметрально противоположной точке.
Очевидно, что направление на ЦМ - направление на сдвоенные бусинки.
Если резать проволоку прямо между сдвоенными бусинками, алгоритм как-то (с точностью до 180 градусов) сработает. Однако, шансов, что так удачно разрежем, мало.
Более вероятный случай, что разрежем проволоку где-то сбоку (то есть, между одиночной и сдвоенными бусинками). Тогда алгоритм выдаст поворот от ЦМ на 1/6 окружности.
Тем не менее, есть случай, когда от алгоритма будет польза и при N=3 и более.
Будем называть углы малыми, если синус угла приблизительно равен углу (в радианах).
Для обсуждаемой у nabbla1 задачки оценим, что все углы меньше 30 градусов можно считать малыми.
Утверждается, что есть некое удачное расположение бусинок, когда алгоритм хорошо работает.
Назовем такое расположение "компактным кластером". Это - когда все бусинки расположились внутри "малого угла". Ну , то есть. Вырезали из картона сектор с углом 30 градусов, удалось найти такое положение сектора, что сектор все бусинки закрыл - отлично, бусинки лежат "компактно"!
Тогда, если разрезать проволоку за пределами "кластера" бусинок, наш алгоритм с хорошей точностью сработает. А вот внутри кластера резать проволоку нельзя.
Теперь вернемся к задачке в формулировке nabbla1 - поставим в точку O теодолит с отсчетом углов 0 ... 360.
Пример 1
Бусинка с направлением на 40 градусов
Бусинка с направлением на 50 градусов
Бусинка с направлением на 69 градусов
Алгоритм сработает. Между направлениями на 40 градусов и на 69 градусов расхождение менее 30 градусов.
Пример 2
Бусинка с направлением на 40 градусов
Бусинка с направлением на 50 градусов
Бусинка с направлением на 168 градусов
Облом. Алгоритм неприменим - кластер бусинок занимает слишком большой угол.
Пример 3.
Бусинка с направлением на 5 градусов
Бусинка с направлением на 24 градусов
Бусинка с направлением на 355 градусов
В моей формулировке - промахнулись с местом разрезания проволоки. Нужно не внутри кластера резать, а снаружи.
В формулировке nabbla1 - неправильно теодолит установили. Нужно повернуть теодолит, чтобы 0 градусов по теодолиту был в другом направлении. Свести "пример 3" к "примеру 1". После этого все получится.
***********************************************************************************************
Update 14.09.2023 21:00 Moscow time.
Опять длинный комментарий - размещаю как "Update".
У Вас не определено, что такое центр группы из нескольких точек.
Рассмотрим случай 3 точек.
Есть такая штука, как энциклопедия центров треугольника.
Там есть точка пресечения медиан, биссектрис, центры описанной и вписанной окружности и так далее.
Википедия пишет, что по состоянию на 2022 год энциклопедия содержит более 52 тысяч (!!!) различных центров.
https://ru.wikipedia.org/wiki/%D0%AD%D0%BD%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F_%D1%86%D0%B5%D0%BD%D1%82%D1%80%D0%BE%D0%B2_%D1%82%D1%80%D0%B5%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D0%B0
Вы вычисляете какой-то свой центр, я вычисляю свой центр.
Пусть в Вашем алгоритме допустимый диапазон поворотов -180...+180 градусов.
Ваш алгоритм определен следующим образом.
Направление на точки alpha, beta, gamma.
Направление на центр группы точек обозначается как phi.
Функция диапазон(величины) означает загнать величину под скобками в диапазон -180...+180 методом прибавления или вычитания 360.
phi = диапазон(alpha + 1/3*диапазон(beta-alpha) + 1/3*диапазон(gamma-alpha))
Рассмотрим набор точек (все в градусах) (-3,+3,180)
Направление на "мой" центр этой конструкции 0 (направление на центр масс).
Направление на Ваш центр этой конструкции -60.
phi = -3 + 1/3*(3+3) + 1/3*(180+3-360)
Переставим эти точки как (+3,-3, 180)
Мой центр не меняется.
Направление на Ваш центр становится +60.
phi = +3 + 1/3*(-3-3) + 1/3*(180-3)
Переставим эти точки как (180, +3,-3)
Мой центр не меняется.
Направление на Ваш центр становится 180.
phi = 180 + 1/3*(3-180) + 1/3*(-3-180+360)
*****************************************************************************************************
Update 14.09.2023 22:00 Moscow time.
Предложенный Вами алгоритм ("загнать разность углов между первой точкой и какой-то другой в диапазон -180...+180") формулируется в моих терминах следующим образом: "разрежем проволочное кольцо в точке, диаметрально противоположной бусинке №1".
Ваш алгоритм идеально работает для системы из 2 бусинок. Как я писал выше, если L1 - кусок проволоки по кратчайшему расстоянию между бусинками, а L2 - более длинный кусок проволоки, то, для правильного результата, нужно резать именно L2 в любом месте. По Вашему алгоритму именно L2 и будет разрезан.
Пояснение.
Комментарий получился настолько длинным, что пришлось размещать в своем журнале. Как отдельный текст, комментарий не имеет смысла. Рекомендую заглянуть в исходное обсуждение https://nabbla1.livejournal.com/513667.html
Переформулируем исходную задачу.
Есть обруч из невесомой проволоки. Центр обозначим O. На обруче закреплено N массивных бусинок, все бусинки имеют одинаковую массу.
У этой конструкции есть центр масс (ЦМ).
Нас интересует следующая задачка.
Случай, когда ЦМ совпал с центром обруча, рассматривать не будем - не повезло, облом, черт с ним.
Во всех остальных случаях мы хотим провести радиус из O в направлении ЦМ. То есть, нас не волнует расстояние между O и ЦМ, нам интересно только направление.
Предлагается следующий алгоритм.
Разрезаем обруч в произвольном месте и распрямляем проволочку. Находим центр масс прямой конструкции (ЦМп), отмечаем его на проволочке. Опять все сворачиваем в исходный вид.
Вопрос - совпадут ли направления от центра обруча на ЦМ и на отметку ЦМп?
Иными словами - может ли алгоритм принести пользу?
N=1
Совпадут
N=2
Почти облом
Случай, когда бусинки строго на разных концах диаметра не рассматриваем.
В другом случае, у бусинок есть кратчайшее расстояние по дуге между ними (кусок проволоки L1) и более длинное расстояние между ними (кусок проволоки L2)
В зависимости от того, резали L2 или L1, алгоритм будет (соответственно) выдавать либо направление на ЦМ, либо направление, строго противоположное ЦМ .
N=3 и более.
В общем случае - совсем облом.
Контрпример.
N=3. Две бусинки "сдвоенные", почти в одной точке. Одна бусинка в диаметрально противоположной точке.
Очевидно, что направление на ЦМ - направление на сдвоенные бусинки.
Если резать проволоку прямо между сдвоенными бусинками, алгоритм как-то (с точностью до 180 градусов) сработает. Однако, шансов, что так удачно разрежем, мало.
Более вероятный случай, что разрежем проволоку где-то сбоку (то есть, между одиночной и сдвоенными бусинками). Тогда алгоритм выдаст поворот от ЦМ на 1/6 окружности.
Тем не менее, есть случай, когда от алгоритма будет польза и при N=3 и более.
Будем называть углы малыми, если синус угла приблизительно равен углу (в радианах).
Для обсуждаемой у nabbla1 задачки оценим, что все углы меньше 30 градусов можно считать малыми.
Утверждается, что есть некое удачное расположение бусинок, когда алгоритм хорошо работает.
Назовем такое расположение "компактным кластером". Это - когда все бусинки расположились внутри "малого угла". Ну , то есть. Вырезали из картона сектор с углом 30 градусов, удалось найти такое положение сектора, что сектор все бусинки закрыл - отлично, бусинки лежат "компактно"!
Тогда, если разрезать проволоку за пределами "кластера" бусинок, наш алгоритм с хорошей точностью сработает. А вот внутри кластера резать проволоку нельзя.
Теперь вернемся к задачке в формулировке nabbla1 - поставим в точку O теодолит с отсчетом углов 0 ... 360.
Пример 1
Бусинка с направлением на 40 градусов
Бусинка с направлением на 50 градусов
Бусинка с направлением на 69 градусов
Алгоритм сработает. Между направлениями на 40 градусов и на 69 градусов расхождение менее 30 градусов.
Пример 2
Бусинка с направлением на 40 градусов
Бусинка с направлением на 50 градусов
Бусинка с направлением на 168 градусов
Облом. Алгоритм неприменим - кластер бусинок занимает слишком большой угол.
Пример 3.
Бусинка с направлением на 5 градусов
Бусинка с направлением на 24 градусов
Бусинка с направлением на 355 градусов
В моей формулировке - промахнулись с местом разрезания проволоки. Нужно не внутри кластера резать, а снаружи.
В формулировке nabbla1 - неправильно теодолит установили. Нужно повернуть теодолит, чтобы 0 градусов по теодолиту был в другом направлении. Свести "пример 3" к "примеру 1". После этого все получится.
***********************************************************************************************
Update 14.09.2023 21:00 Moscow time.
Опять длинный комментарий - размещаю как "Update".
У Вас не определено, что такое центр группы из нескольких точек.
Рассмотрим случай 3 точек.
Есть такая штука, как энциклопедия центров треугольника.
Там есть точка пресечения медиан, биссектрис, центры описанной и вписанной окружности и так далее.
Википедия пишет, что по состоянию на 2022 год энциклопедия содержит более 52 тысяч (!!!) различных центров.
https://ru.wikipedia.org/wiki/%D0%AD%D0%BD%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%BF%D0%B5%D0%B4%D0%B8%D1%8F_%D1%86%D0%B5%D0%BD%D1%82%D1%80%D0%BE%D0%B2_%D1%82%D1%80%D0%B5%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D0%B0
Вы вычисляете какой-то свой центр, я вычисляю свой центр.
Пусть в Вашем алгоритме допустимый диапазон поворотов -180...+180 градусов.
Ваш алгоритм определен следующим образом.
Направление на точки alpha, beta, gamma.
Направление на центр группы точек обозначается как phi.
Функция диапазон(величины) означает загнать величину под скобками в диапазон -180...+180 методом прибавления или вычитания 360.
phi = диапазон(alpha + 1/3*диапазон(beta-alpha) + 1/3*диапазон(gamma-alpha))
Рассмотрим набор точек (все в градусах) (-3,+3,180)
Направление на "мой" центр этой конструкции 0 (направление на центр масс).
Направление на Ваш центр этой конструкции -60.
phi = -3 + 1/3*(3+3) + 1/3*(180+3-360)
Переставим эти точки как (+3,-3, 180)
Мой центр не меняется.
Направление на Ваш центр становится +60.
phi = +3 + 1/3*(-3-3) + 1/3*(180-3)
Переставим эти точки как (180, +3,-3)
Мой центр не меняется.
Направление на Ваш центр становится 180.
phi = 180 + 1/3*(3-180) + 1/3*(-3-180+360)
*****************************************************************************************************
Update 14.09.2023 22:00 Moscow time.
Предложенный Вами алгоритм ("загнать разность углов между первой точкой и какой-то другой в диапазон -180...+180") формулируется в моих терминах следующим образом: "разрежем проволочное кольцо в точке, диаметрально противоположной бусинке №1".
Ваш алгоритм идеально работает для системы из 2 бусинок. Как я писал выше, если L1 - кусок проволоки по кратчайшему расстоянию между бусинками, а L2 - более длинный кусок проволоки, то, для правильного результата, нужно резать именно L2 в любом месте. По Вашему алгоритму именно L2 и будет разрезан.