Дан угол, под которым луч выходит из начала координат (от -180 до 180) и угол на который он поворачивается (от -360 до 360). Требуется определить, пересечет ли он третий луч, угол которого также задан.
Есть ли какой-то простой алгоритм? Или нужно писать кучу if-ов учитывая пересечение первым лучом нуля, 180 или -180 градусов?
Здравствуйте, 777777w, Вы писали:
7>Дан угол, под которым луч выходит из начала координат (от -180 до 180) и угол на который он поворачивается (от -360 до 360). Требуется определить, пересечет ли он третий луч, угол которого также задан.
Третий? А где второй?
7>Есть ли какой-то простой алгоритм? Или нужно писать кучу if-ов учитывая пересечение первым лучом нуля, 180 или -180 градусов?
Здравствуйте, Dorofey, Вы писали:
7>>Дан угол, под которым луч выходит из начала координат (от -180 до 180) и угол на который он поворачивается (от -360 до 360). Требуется определить, пересечет ли он третий луч, угол которого также задан.
D>Третий? А где второй?
Второй это положение первого после поворота.
7>>Есть ли какой-то простой алгоритм? Или нужно писать кучу if-ов учитывая пересечение первым лучом нуля, 180 или -180 градусов?
D>Бррр, какие кучу if-ов? Ты хочешь написать 360 if-ов? Вау, индиан стайл солюшн
Чтобы было понятно — конкретный пример. Первый луч +10 градусов, поворачивается на -340 градусов. Пересечет ли он луч -20 градусов? +170? +20? Напиши выражение возвращающее bool.
Здравствуйте, 777777w, Вы писали:
7>Есть ли какой-то простой алгоритм? Или нужно писать кучу if-ов учитывая пересечение первым лучом нуля, 180 или -180 градусов?
Строим уравнения прямых, на которых лежат лучи. Ищем точку пересечения и проверяем, что она лежит в границах луча.
Если луч 1 повёрнут на угол alpha радиан, то уравнение его прямой будет:
-x*sin(alpha) + y*cos(alpha) = 0
Здравствуйте, Cyberax, Вы писали:
7>>Есть ли какой-то простой алгоритм? Или нужно писать кучу if-ов учитывая пересечение первым лучом нуля, 180 или -180 градусов? C>Строим уравнения прямых, на которых лежат лучи. Ищем точку пересечения и проверяем, что она лежит в границах луча.
Точка пересечения лучей всегда будет в начале координат независимо от углов.
Здравствуйте, 777777w, Вы писали:
7>Чтобы было понятно — конкретный пример. Первый луч +10 градусов, поворачивается на -340 градусов. Пересечет ли он луч -20 градусов? +170? +20? Напиши выражение возвращающее bool.
if (testAngle > startAngle &&
testAngle < (startAngle+rotateAngle))
Здравствуйте, 777777w, Вы писали:
7>>>Есть ли какой-то простой алгоритм? Или нужно писать кучу if-ов учитывая пересечение первым лучом нуля, 180 или -180 градусов? C>>Строим уравнения прямых, на которых лежат лучи. Ищем точку пересечения и проверяем, что она лежит в границах луча. 7>Точка пересечения лучей всегда будет в начале координат независимо от углов.
Можно детально задачу с рисунком?
Здравствуйте, 777777w, Вы писали:
7>Дан угол, под которым луч выходит из начала координат (от -180 до 180) и угол на который он поворачивается (от -360 до 360). Требуется определить, пересечет ли он третий луч, угол которого также задан.
7>Есть ли какой-то простой алгоритм? Или нужно писать кучу if-ов учитывая пересечение первым лучом нуля, 180 или -180 градусов?
Луч заметает некий интервал углов на окружности. Приводим этот интервал к полностью неотрицательному, добавляя при необходимости 2Pi или 4Pi так, чтобы левая точка интервала (неважно, начало это, или конец) стала неотрицательной, и лежала в диапазоне [0, 2Pi). Потом третью точку тоже делаем неотрицательной, и проверяем, что или она (X) или (X+2Pi) лежит внутри интервала
Здравствуйте, MBo, Вы писали:
MBo>Луч заметает некий интервал углов на окружности. Приводим этот интервал к полностью неотрицательному, добавляя при необходимости 2Pi или 4Pi так, чтобы левая точка интервала (неважно, начало это, или конец) стала неотрицательной, и лежала в диапазоне [0, 2Pi). Потом третью точку тоже делаем неотрицательной, и проверяем, что или она (X) или (X+2Pi) лежит внутри интервала
Добавлю, стоит еще разворачивать дугу, чтобы направление всегда было CW или CCW (смотря что выбрано за положительное направление).
Тогда пасьянс сходится.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Добавлю, стоит еще разворачивать дугу, чтобы направление всегда было CW или CCW (смотря что выбрано за положительное направление).
Собственно, интервал (отрезок) ненаправленный, поэтому ориентация уже волновать не будет.
Здравствуйте, MBo, Вы писали:
MBo>Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>>Добавлю, стоит еще разворачивать дугу, чтобы направление всегда было CW или CCW (смотря что выбрано за положительное направление).
MBo>Собственно, интервал (отрезок) ненаправленный, поэтому ориентация уже волновать не будет.
Нашел контрпример, когда алгоритм не сработает.
Поискал у себя в закромах.
В общем достаточно посчитать векторное произведение векторов SD и SE.
D — точка пересечения луча и окружности,
S — начало дуги, E — конец дуги.
Знак произведения показывает, попадает луч в дугу или нет.
В этом случае направление дуги не важно.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Нашел контрпример, когда алгоритм не сработает.
А я пока не нашел...
SVZ>Поискал у себя в закромах. SVZ>В общем достаточно посчитать векторное произведение векторов SD и SE. SVZ> SVZ>Знак произведения показывает, попадает луч в дугу или нет. SVZ>В этом случае направление дуги не важно.
То есть как не важно? А если дуга рисуется от S к E против часовой стрелки? Тогда произведение останется прежним, но точка D попадает на дугу!
Задача выглядит так: попадает ли угловая координата НаправлениеЛуча2 в интервал [НачалоЛуча1, НачалоЛуча1 + ПоворотЛуча1].
Поскольку у нас есть зацикливание, то
— либо придётся распознать, что интервал вышел за область значений [-180,+180] — и тогда рассмотреть уже два интервала [-180,конец] и [начало,+180]
— либо размножить проверяемую точку — и проверить вхождение луч2, луч2-360, луч2+360 в интервал [начало,конец]
— либо размножить интервал — и проверить вхождение луч2 в [начало,конец], [начало-360,конец-360], [начало+360,конец+360]
Понятно, что проверять надо не три, а только два варианта — в зависимости от того, куда сместился оригинальный интервал.
Ну а если коротко, то
bool belongs(int a, int b, int c) // a <- [b,b+c]
{
assert(a >= -180 && a <= 180);
assert(b >= -180 && b <= 180);
assert(c >= -360 && c <= 360);
// быстрые проверкиif(c == 0) return a==b;
if(c == -360 || c == 360) return true;
int x, y; // [b,b+c] = [x,y]if(c < 0) { x=b+c; y=b; } else { x=b; y=b+c; } // упорядочиваем границы интервалаif(a < x) a += 360; // даём шанс - перемещаем точку вправо на полный циклreturn a>=x && a<=y;
}
Здравствуйте, 777777w, Вы писали:
7>Дан угол, под которым луч выходит из начала координат (от -180 до 180) и угол на который он поворачивается (от -360 до 360). 7>Есть ли какой-то простой алгоритм? Или нужно писать кучу if-ов учитывая пересечение первым лучом нуля, 180 или -180 градусов?
Если тебе важно не писать много условий, то можно обойтись одним:
угол t находится внутри сектора [s; s + a] только если cos(s – t + a/2) ≥ cos(a/2).
Очевидно, все случаи с периодичностью тут уже учтены внутри косинуса. Разумеется двукратное вычисление косинуса и является главным недостатком такого решения.
Здравствуйте, 777777w, Вы писали:
7>Дан угол, под которым луч выходит из начала координат (от -180 до 180) и угол на который он поворачивается (от -360 до 360). Требуется определить, пересечет ли он третий луч, угол которого также задан.
7>Есть ли какой-то простой алгоритм? Или нужно писать кучу if-ов учитывая пересечение первым лучом нуля, 180 или -180 градусов?
Вычислить угол между 1-м и 3-м лучём в направлении вращения 1-го луча.
Сравнить вычисленный угол с углом поворота.
Здравствуйте, 777777w, Вы писали:
7>Чтобы было понятно — конкретный пример. Первый луч +10 градусов, поворачивается на -340 градусов. Пересечет ли он луч -20 градусов? +170? +20? Напиши выражение возвращающее bool.
Что значит пересечет? Если все лучи исходят из начала координат, казалось бы, все они в начале координат и пересекаются между собой. Поэтому выражение будет состоять из одного слова, true
W>угол t находится внутри сектора [s; s + a] только если cos(s – t + a/2) ≥ cos(a/2). W>Разумеется двукратное вычисление косинуса и является главным недостатком такого решения.
Впрочем, от косинуса требуется лишь сравнение на больше–меньше, а не точное значение. Так что можно его заменить на похожую функцию, скажем на модуль и остаток от деления:
|180° – (|s – t + a/2| mod 360°)| ≥ 180° – |a/2|
Не то чтобы запись получилась короче, но зато никакой тригонометрии.
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, 777777w, Вы писали:
7>>Дан угол, под которым луч выходит из начала координат (от -180 до 180) и угол на который он поворачивается (от -360 до 360). 7>>Есть ли какой-то простой алгоритм? Или нужно писать кучу if-ов учитывая пересечение первым лучом нуля, 180 или -180 градусов?
W>Если тебе важно не писать много условий, то можно обойтись одним: W>угол t находится внутри сектора [s; s + a] только если cos(s – t + a/2) ≥ cos(a/2). W>Очевидно, все случаи с периодичностью тут уже учтены внутри косинуса.
Мне это совершенно не очевидно. Нельзя ли привести математическое доказательство?
W>Разумеется двукратное вычисление косинуса и является главным недостатком такого решения.
На дворе 21 век, поэтому вычисление косинуса не является препятствием. Гораздо более серьезным недостатком является то, что ни один придуманный мной тестовый пример не подтверждает работоспособность этого алгоритма.
Здравствуйте, 777777w, Вы писали:
7>Дан угол, под которым луч выходит из начала координат (от -180 до 180) и угол на который он поворачивается (от -360 до 360). Требуется определить, пересечет ли он третий луч, угол которого также задан.
7>Есть ли какой-то простой алгоритм? Или нужно писать кучу if-ов учитывая пересечение первым лучом нуля, 180 или -180 градусов?
Протестированное решение
a — угол первого луча
delta — угол поворота первого луча
b — угол луча, для которого требуется определить пересечет ли его первый луч при повороте
Алгоритм работает для любых a, delta, b (не только в диапазоне из задачи)
Решение: Изменяем систему координат таким образом, чтобы первый луч был равен нулю, а второй луч задан положительным углом (т.е. по часовой стрелке). Далее нам останется рассмотреть два варианта — либо угол поворота также положительный (по часовой стрелке), либо отрицательный (против часовой)
def cover(a, delta, b):
# Шаг первый - поворачиваем систему координат на угол a
b -= a
a -= a
# Шаг второй - если необходимо переворачиваем (отражаем) систему координатif b < 0:
b = -b
delta = -delta
# Привели систему к виду:assert a == 0
assert b >= 0
# Корректируем b, если он очень большой
b = b % 360
# Сравниваем нашу delta c углом b (b > 0)if delta >= 0: # delta и b идут в одном направлении (по часовой)return delta >= b
else: # delta < 0, т.е. против часовойreturn -delta >= 360 - b
Б> # Сравниваем нашу delta c углом b (b > 0)
Б> if delta >= 0: # delta и b идут в одном направлении (по часовой)
Б> return delta >= b
Б> else: # delta < 0, т.е. против часовой
Б> return -delta >= 360 - b
Б>
Перепутал здесь "по часовой" и "против часовой", но это только в комментариях. На код не влияет
Здравствуйте, 777777w, Вы писали:
W>>угол t находится внутри сектора [s; s + a] только если cos(s – t + a/2) ≥ cos(a/2). W>>Очевидно, все случаи с периодичностью тут уже учтены внутри косинуса. 7>Мне это совершенно не очевидно.
Косинус — функция периодическая. 7>Нельзя ли привести математическое доказательство?
Идея такая:
Проверим, что угол 0 лежит внутри сектора, заметаемый вектором с началом в угле s при повороте на угол a. Возьмём биссектрису этого сектора, у неё будет угол (s+a/2). Любое направление, что находится внутри сектора, имеет угол между ним и биссектрисой меньше |a/2|. Всё что находится вне сектора имеет угол с биссектрисой больше |a/2|.
Берёшь пару единичных векторов U(cos(s+a/2), sin(s+a/2)) и V(1, 0) — один из них соответствует биссектрисе, второй — цели проверки. Скалярное произведение U·V = |U|·|V|·cos(i) = cos(i), где i — это искомый угол. Если он больше |a/2|, то вхождения нет, если меньше — есть. Но в если записать скалярное произведение покоординатно, то U·V = cos(s+a/2). Таким образом нужно просто решить, что же больше: cos(s+a/2) или cos(a/2).
Случай с произвольной целью t сводится просто к повороту всей конструкции на угол (-t). В этом случае a, разумеется, не меняется, а начало сектора переходит в (s – t). То есть сравнивать на больше–меньше придётся cos(s – t + a/2) и cos(a/2).
W>>Разумеется двукратное вычисление косинуса и является главным недостатком такого решения.
7>На дворе 21 век, поэтому вычисление косинуса не является препятствием. Гораздо более серьезным недостатком является то, что ни один придуманный мной тестовый пример не подтверждает работоспособность этого алгоритма.
То есть? Ты придумал миллиард примеров и на них всех формула дала верный ответ, но тебе нужно более полное доказательство?
Или ты нашел пример, где формула даёт неверный ответ? В таком случае, возможно, ты зря говоришь о том, что «вычисление косинуса не является препятствием» — вдруг ты в своём калькуляторе радианы с градусами перепутал при вычислениях, например.
Здравствуйте, watchmaker, Вы писали:
7>>Нельзя ли привести математическое доказательство? W>Идея такая: W>Проверим, что угол 0 лежит внутри сектора, заметаемый вектором с началом в угле s при повороте на угол a. Возьмём биссектрису этого сектора, у неё будет угол (s+a/2). Любое направление, что находится внутри сектора, имеет угол между ним и биссектрисой меньше |a/2|. Всё что находится вне сектора имеет угол с биссектрисой больше |a/2|.
Кажется дошло... Действительно должно работать, сейчас попробую.
Перекуём баги на фичи!
